Source material flagged in the lecture: the book Modern B-Tree Techniques (~10 years old) and a follow-up, more modern B+Tree techniques, published the month before the lecture. There is no comparable book on red-black trees or skip lists — evidence of how central this structure is 58:58 59:29.
1. Node size
- Rule: the slower the storage device, the larger the node, to maximize sequential access per fetch
59:46. - Enterprise systems like DB2 let you declare, per index, which buffer pool manager to use and what page size it has
1:00:14. - Also depends on workload: point queries want a different size than long scans
1:00:14. - Inner nodes are often made larger than leaf nodes, since they see most of the traffic
1:01:231:01:39.
2. Merge threshold
- Textbook rule (merge below half full) causes thrashing under alternating insert/delete: split, merge, split, merge
1:00:44. - Fix: relax the constraint — let nodes sit below half full, and only merge when a node becomes completely empty
1:01:09. - This is precisely why Postgres calls its implementation a non-balanced B+Tree in the code
1:01:23.
3. Variable-length keys
Four options 1:01:39:
| Option | How | Verdict |
|---|---|---|
| Pointers | store a record ID instead of the key; follow it to compare | bad — see below 1:01:39 |
| Variable-length nodes | let node size vary | only in academic systems; too much memory management 1:03:22 |
| Padding | pad every key to the type's max length so it aligns | works, wastes space 1:03:22 |
| Slotted pages inside the node | a slot array within the node page, with overflow allowed | most common; Postgres allows within-node overflow 1:03:56 1:04:16 |
Why the pointer approach fails — the T-Tree story:
- T-Trees were an in-memory data structure (1990s) that stored pointers instead of keys
1:02:09. - Problem: with no keys in the node, every comparison during a descent requires following a pointer and fetching a tuple — so a binary search inside one inner node dereferences a bunch of tuples
1:02:31. - Only defensible if keys are enormous (~1 GB), which they never are
1:02:31. - Outcome: Oracle TimesTen originally used T-Trees and got rid of them — everyone now uses B+Trees
1:02:31.
4. Intra-node search
| Method | Description | Practical status |
|---|---|---|
| Linear scan | walk from start to end | simple, works on unsorted nodes 1:04:16 1:04:33 |
| SIMD-accelerated linear scan | broadcast the search key into a vector register and compare 4 lanes (32-bit ints) — or many more with AVX-512 — in one instruction, then bit-shift to locate the match | a better linear scan; uses x86 intrinsics, ARM has its own 1:04:56 1:05:26 1:06:09 |
| Binary search | requires sorted keys; jump to midpoint, go left/right | standard 1:06:20 |
| Interpolation search | if keys are monotonically increasing with no gaps, compute the offset directly | fastest, but exists only in academic papers — no system implements it 1:06:37 1:07:03 |
Practical recommendation: binary search, or linear search with SIMD
1:07:03.