B-trees, B+ trees and disk I/O

B-trees reduce disk accesses through high branching: one page contains many keys and narrows the search substantially. Under minimum degree t, nonroot nodes hold t−1 to2t−1 keys and leaves share a depth.

B+ trees keep routing separators internally and records or references in leaves; linked leaves support range scans. Insertions split full pages and promote separators; deletions borrow or merge to maintain occupancy. Transactions, latches, recovery and WAL are additional database concerns.

Not every database or filesystem uses the same B+ tree. Engines choose LSM, hash, inverted or spatial structures for different purposes. Analyse block I/O rather than only CPU comparisons; larger keys can reduce fan-out.

Think about indexes in the disk model

A binary tree with O(log₂ n) height may still need many I/Os if nodes occupy separate blocks. B-tree nodes pack many keys and child pointers into a block. Fanout F yields roughly log_F n levels. Larger keys and pointers reduce F, so covering and composite index costs depend on record width as well as count.

B+ trees place records or record pointers at leaves; internal separators route searches. Leaf links support range scans: find the first leaf, then follow neighbouring leaves. Duplicate-key rules and separator maintenance vary by implementation.

Overflow triggers a leaf split, separator insertion into the parent and possibly root splitting. Deletion preserves minimum occupancy through borrowing or merging. Concurrent implementations need latching and recovery mechanisms. Isolation and durability come from the transaction/log system as well as the index structure.

Foundation: Estimate levels for a million records and fanout 100. Intermediate: Include output-block costs in a range scan. Advanced: Compare random and sequential insertion for splits, fill factor and write amplification; do not assume every database uses one index design.

from bisect import bisect_right
# Routing separators; records are not stored here.
separators = [20, 40]
assert bisect_right(separators, 19) == 0
assert bisect_right(separators, 20) == 1
assert bisect_right(separators, 41) == 2