B+ Tree Internals: Leaf Linking & Range Scans
Unlike classic B-Trees, B+ Trees store all actual record values exclusively in leaf nodes. Internal nodes act purely as lightweight routing guides. Furthermore, leaf nodes form a doubly linked list, transforming SQL `WHERE key BETWEEN X AND Y` into instantaneous linear sequential reads 🔗📈.
class BPlusLeaf:
def __init__(self, keys, values):
self.keys = keys
self.values = values
self.next = None
def scan_range(start_leaf, low, high):
records = []
curr = start_leaf
while curr:
for k, v in zip(curr.keys, curr.values):
if k > high:
return records
if k >= low:
records.append((k, v))
curr = curr.next
return records
# Linked leaves:
leaf_a = BPlusLeaf([10, 20], ["User_10", "User_20"])
leaf_b = BPlusLeaf([30, 40], ["User_30", "User_40"])
leaf_a.next = leaf_b
print(f"Range 15..35: {scan_range(leaf_a, 15, 35)} 🚀")
# 55. B+ Tree Internals: Leaf Linking & Range Scans In a standard B-Tree, values are scattered across every level of the tree. Executing a range scan like `SELECT * FROM orders WHERE date BETWEEN '2026-01-01' AND '2026-01-31'` requires an in-order tree traversal, jumping up and down between parent and child disk pages repeatedly 🛑. ```python # Classic B-Tree Range Scan (Jerky & Slow): # Leaf -> Parent -> Other Child -> Parent -> Leaf (Heavy random I/O) # B+ Tree Range Scan (Contiguous & Fast): # Leaf 1 ---> Leaf 2 ---> Leaf 3 (Pure forward sequential I/O!) ``` ### The B+ Tree Structural Invariant 1. **Separation of Keys and Values**: Internal routing nodes only store keys and page pointers. Because no record payloads take up space in internal nodes, a 4KB block can fit hundreds of routing keys, giving an immense fan-out factor. 2. **All Data in Leaves**: Every actual table record or pointer to heap storage lives exclusively in the leaf layer at the bottom of the tree. 3. **Sequential Leaf Chain**: Every leaf node contains a `.next` (and often `.prev`) pointer to its sibling. Once you traverse from root to the first matching leaf, the remainder of the query is a lightning-fast linked list walk 🔗📈. --- ### Interactive Pop-Quiz 🧠#### Why are B+ Trees favored over standard B-Trees as primary index structures in relational databases like InnoDB and PostgreSQL? - [ ] Linked leaf nodes enable high-throughput range scans without climbing up and down parent tree nodes 🔗 - [ ] B+ Trees prevent transactions from deadlocking on write operations - [ ] B+ Trees run in Python bytecode rather than compiled C libraries - [ ] B+ Trees do not require binary comparison operators --- ### Practical Challenge 🎯 Implement `scan_leaves(start_node, min_k, max_k)` traversing `.next` links across `BPlusLeaf(keys, values)`. Connect Leaf 1 (`keys=[5, 10]`, `values=['v5', 'v10']`), Leaf 2 (`keys=[15, 20]`, `values=['v15', 'v20']`), and Leaf 3 (`keys=[25, 30]`, `values=['v25', 'v30']`). Query range `8` to `22`. Print the extracted `(key, value)` tuples. <details> <summary>Solution</summary> ```python class BPlusLeaf: def __init__(self, keys, values): self.keys = keys self.values = values self.next = None def scan_leaves(start_node, min_k, max_k): results = [] curr = start_node while curr: for k, v in zip(curr.keys, curr.values): if k > max_k: return results if k >= min_k: results.append((k, v)) curr = curr.next return results l1 = BPlusLeaf([5, 10], ['v5', 'v10']) l2 = BPlusLeaf([15, 20], ['v15', 'v20']) l3 = BPlusLeaf([25, 30], ['v25', 'v30']) l1.next = l2 l2.next = l3 res = scan_leaves(l1, 8, 22) assert res == [(10, 'v10'), (15, 'v15'), (20, 'v20')] print(res) ``` </details>