B-Trees

A B-Tree of order m is a self-balancing search tree where each node holds many keys instead of one:

  • Each node stores at most m−1 keys and at most m children (keys sort within the node; children occupy the gaps).
  • Every node except the root holds at least ⌈m/2⌉−1 keys.
  • All leaves sit at the same depth.

A B-Tree of order 100 storing a billion keys has height ≈ 5. That depth is what makes B-Trees the default index structure for databases.

Insert: Split on the Way Down

Inserting x never makes a node overflow, because full nodes are split before descending into them:

  1. If the root is full, split it — the median key becomes a new root and the tree grows taller (the only way height increases).
  2. Descend, comparing against node keys to pick the correct child gap.
  3. Whenever the next child is full, split it: its median key moves up into the parent, and the remaining keys divide into two nodes.
  4. Insert x into the leaf in sorted position.
        [ 20 ]                 [ 20 ]
       /  |  \      insert     /  |  \
    [5,9] [25] [40]  30   → [5,9] [25]  [40,50]   ← split, 30 goes here
                                       /    |
                                    [30]  [50]

The split costs O(m) pointer surgery but keeps every leaf at the same depth — the tree stays perfectly balanced.

Why So Few Levels? Disk Blocks

A database reads/writes in fixed-size pages (e.g. 4–16 KB). One B-Tree node fits exactly one page, so a “visit a node” is a single disk I/O. With order ~100, visiting 5 nodes means 5 page reads for any of a billion keys — versus ~30 levels for a binary tree. Height ≈ log_m n is the whole point.

Variants You’ll Meet

  • B+ Tree — internal nodes hold only keys; all data sits in leaf nodes, linked in a chain for fast range scans. This is what MySQL InnoDB and PostgreSQL actually use.
  • B Tree* — sibling balancing, higher minimum occupancy.
  • LSM Tree — write-optimized alternative used by LevelDB, RocksDB, Cassandra.

Practice Trajectory

  1. Implement insert with split-on-the-way-down for order 4; verify all leaves end at the same depth.
  2. Add search, confirming it descends by key comparison in each node.
  3. Implement delete with borrow/merge (underflow handling — the hardest part).
  4. Add B+ tree leaves-with-links and do an ordered range scan.
  5. Solve: database-index and filesystem-directory problems, K-th smallest in a B-Tree.