B+Tree Indexing

Why this module exists

Indexes are the performance backbone of a database. The B+Tree is designed for disk pages: shallow height, ordered keys, and efficient range scans.

1) B+Tree invariants

• Internal nodes store separator keys and child pointers.
• All actual records live in leaf nodes.
• Leaves are linked for fast range scans.
• Keys in a node are sorted.

2) Splits and propagation

When a node overflows, it splits:

• Leaf split: divide keys, promote the first key of the right leaf.
• Internal split: promote the middle key and split children.

Splits can cascade up to the root, increasing tree height.

3) Search and range

Search follows separators to a leaf, then scans within leaf nodes. Range scans walk leaf links.

What you will build

• B+Tree search
• B+Tree insert with leaf and internal splits

Key takeaways

• The B+Tree is optimized for page-based storage.
• Splits preserve ordering and balance.
• Leaf links make range queries fast.