just a blog post for summarising my algorithm learning course.

Left-leaning Red-black BST

1. From main memory to disk

2-3 search trees and red-black BSTs both assume the whole structure lives in memory, where every comparison costs roughly the same. Once the symbol table is too big for memory - a database, a file system - a different cost dominates: reading a chunk of data off disk.

File system model:

• A page is a contiguous block of data (e.g. a file, or a 4,096-byte chunk).
• A probe is the first access to a page (e.g. transferring it from disk into memory).
• A probe is much slower than comparing keys already in memory.
• Cost model: number of probes.
• Goal: access data using the minimum number of probes.

2. B-trees

B-tree (Bayer-McCreight, 1972). Generalize a 2-3 tree by allowing up to M - 1 key-link pairs per node - choose M as large as possible so that M links fit in one page (e.g. M = 1024).

• At least 2 key-link pairs at the root.
• At least M / 2 key-link pairs in every other (internal) node.
• At most M - 1 key-link pairs in any node.
• External nodes (the bottom level) hold the actual client keys.
• Internal nodes hold copies of keys, purely to guide the search - each key in an internal node is a copy of the smallest key in the subtree below it.
• A sentinel key *, smaller than every possible client key, is kept in the leftmost slot of the leftmost node on every level, so that node still has one more link than it has “real” keys.

Here’s a B-tree of order M = 6 (so every node holds between 3 and 5 key-link pairs, except the root):

The root is a 2-node (2 key-link pairs). *, 20, 35 and 50, 65, 75 are internal 3-nodes. 50, 52, 55, 58, 60 is a full external 5-node (M - 1 = 5 keys), and every other leaf is a 3- or 4-node. Notice 20, 35, 50, 65 and 75 each appear twice: once as a guide key in an internal node, and once as the smallest client key of the leaf it points to.

3. Search in a B-tree

• Start at the root.
• Find the interval containing the search key and follow the corresponding link.
• Repeat until the search terminates in an external node.

Example: searching for 68 follows the right link at the root (68 >= 50), then the middle link at 50, 65, 75 (68 is between 65 and 75), landing in the external node 65, 68, 70:

Most other read-only operations (floor, ceiling, iteration, …) work the same way - always following the single interval that contains the key.

4. Insertion in a B-tree

• Search for the new key, as above; this always terminates in an external node.
• Insert the new key into that external node, in order.
• If the node now has M key-link pairs (overflow), split it into two half-full nodes and push a copy of the new node’s smallest key up into the parent - which may itself overflow and split, and so on, possibly all the way up to the root.
• If the root splits, create a brand-new root above it with one key and two links. This is the only way a B-tree grows in height, and it does so uniformly across every leaf - the tree stays perfectly balanced.

Worked example, starting from a small order-6 B-tree whose root is already a full 5-node:

Inserting 100 (the new smallest key) lands in the leftmost leaf, which now has 6 key-link pairs - one too many:

That leaf splits into *, 100, 103 and 105, 108, 112, pushing a copy of 105 up into the root - which now overflows too (6 key-link pairs):

The root splits too, into *, 105, 130 and 160, 190, 220, and a brand-new root *, 160 is created above them - the tree just grew by one level, uniformly across every leaf:

5. Balance in a B-tree

Proposition: a search or an insertion in a B-tree of order M with N keys requires between log_(M-1) N and log_(M/2) N probes.

• Every internal node (besides the root) has between M / 2 and M - 1 links, which squeezes the height between those two logarithms.
• In practice, the number of probes is at most 4 or 5 even for huge tables, because M is chosen large enough that a handful of levels covers billions of keys.
• Optimization: always keep the root page in memory - that’s one guaranteed probe saved on every single search or insert.

Splitting always divides an overflowing node into two halves, so right after a split each half is about half full; as more keys are inserted into the surrounding leaves those pages gradually fill back up until they overflow and split again:

6. B-trees in the wild

B-tree variants - B+ tree, B* tree, B# tree, … - are widely used for file systems and databases, where minimizing the number of page reads matters far more than the number of comparisons:

• Windows: NTFS.
• Mac: HFS, HFS+.
• Linux: ReiserFS, XFS, Ext3FS, JFS.
• Databases: Oracle, DB2, INGRES, SQL Server, PostgreSQL.

Compare that to the red-black BSTs from the previous post, which shine as in-memory symbol tables - both are ultimately descendants of the same idea, a 2-3 tree, just tuned for very different costs: comparisons in memory vs. probes on disk.