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.

Delete: Borrow, Merge, and Underflow

Deletion is the mirror image of insertion. Inserting splits full nodes; deleting merges nodes that fall below the minimum occupancy ⌈m/2⌉−1. A node with too few keys is said to underflow.

1. Find the key. If it’s in a leaf, remove it directly. If it’s in an internal node, swap it with its inorder predecessor or successor (the max key in its left subtree / min key in its right subtree), then delete from that leaf — a standard BST-style delete.
2. Fix underflow in the leaf. If the leaf now has too few keys, try to borrow:
   • Left/right sibling has a spare key → rotate: pull the parent’s separator key down into the underfull node, push the sibling’s edge key up into the parent. The parent key count is unchanged; both children stay legal. This is the cheap, local fix.
   • Sibling also at minimum → merge: combine the underfull node + the separator key from the parent + the sibling into one node. This removes the separator, so the parent may now underflow — the fix propagates upward.
3. Propagate. Repeat the borrow-or-merge logic one level up until the parent is fine or the root is reached. If the root ends up empty, remove it and let its single child become the new root (the only way height shrinks).

        [ 30 ]                    delete 30 → borrow from right
       /      \        [30,55]    swaps with 55, then:
  [10,20]  [40,50,60]   ...          /     |     \
                                [10,20] [40]   [60]

In practice the rules reduce to: borrow if a sibling can spare a key, else merge — and merging is what occasionally makes the tree shallower. Both operations cost O(m) node work but preserve the two invariants that matter: every leaf at the same depth, and no node below minimum occupancy.

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 (the database workhorse)

The B+ Tree splits the two jobs a B-Tree node does — organizing keys and storing data. Internal nodes hold only keys (maximum fanout per page, hence minimum height); all data lives in the leaves, which are chained into a doubly-linked list for O(1)-sequential range scans.

       [20]            ← internal: keys only
      /    \
 [10]      [30]        ← internal: keys only
  |          |
 leaf[5,10] leaf[15,20,30]  ← data + next/prev links

Three consequences make B+ the default (MySQL InnoDB, PostgreSQL, SQLite):

• Range scans are pointer walks — WHERE id BETWEEN 10 AND 200 visits the leaf chain left-to-right with no backtracking up the tree. A classic B-Tree has no leaf chain; ranges bounce between levels.
• Smaller internal nodes — no payload bytes in upper levels means higher fanout per page, which means a shorter tree (fewer disk reads) for the same data.
• Predictable leaf size — a fixed page holds a fixed number of records, so data files stay uniform; clusters and secondary indexes both build cleanly.

The classic B-Tree’s internal-node data can mean one page read reaches the row (no extra leaf hop), but range performance and fanout make the B+ trade-off the winner for nearly all production stores. When someone says “B-Tree index,” they almost always mean a B+ Tree.

B* Tree & Other Variants

• B Tree* — splits fill two siblings instead of one, keeping minimum occupancy ~⅔ and height lower at the cost of more complex split logic. Seen in some filesystems and older IBM storage systems.
• LSM Tree — the write-optimized alternative (LevelDB, RocksDB, Cassandra): batched in-memory writes flushed as sorted runs, merging in the background. Better write throughput, worse point-read latency, and read-amplification from run-merging — the trade-of-the-day when writes dominate.

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.