TreesTrees

B+ Tree Range Scan

A B-tree variant that stores all records in linked leaf nodes and uses internal nodes only as a routing index, giving fast point lookups and sequential range scans.

Learn B+ Tree →

Values | lo hi — Distinct integers to insert, a pipe, then the range bounds — e.g. "1,4,7,9,12,15,18,21 | 7 15"

Inserted so far

empty

1/28An empty B+ tree: one leaf. Two rules separate it from a B-tree — every value is stored in a leaf and nowhere else, and the leaves are linked left to right in sorted order.

Node being examinedDescent path / leaf chain followedOverflowing nodeLeft half after a splitRight half after a splitLeaf contributing to the resultLeaf read, nothing in range

PseudocodeLearn B+ Tree →

1insert(v):
2  descend to the leaf whose separator range contains v
3  insert v into that leaf, keeping its values sorted   # every value lives in a leaf
4  leaf overflow: split it and COPY the first key of the right half up
5  internal overflow: split it and MOVE the median key up
6rangeScan(lo, hi):
7  node = root; while node is internal: follow the separators down
8  read the leaf, keeping every value in [lo, hi]
9  follow leaf.next sideways along the chain
10  stop at the first value greater than hi

Variables

height1

leaves1

values0

Complexity

access O(log n)

search O(log n)

insert O(log n)

delete O(log n)

Speed