B-Tree Internals — Pages, Splits & Buffer Pool
Pages, fanout, leaf/internal, splits; buffer pool caches dirty pages async; WAL still required; Postgres/InnoDB.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Why OLTP still loves B+Trees
Prefer
Leaf-linked B+Tree + buffer pool sized to the hot set
Point lookups are a few page I/Os (often RAM). Range scans walk sibling pointers. Height stays tiny because fanout is huge.
- 8–16KB pages: I/O unit and latch granularity.
- Dirty pages flush in the background; WAL still owns durable commit.
- InnoDB clustered primary; Postgres heap + secondary B-Trees.
Alternative
Hash everything, or assume RAM makes WAL optional
Hash has no ranges. The buffer pool is volatile. LSM is the sequential-write cousin when ingest dominates — not a drop-in for every OLTP table.
- Working set larger than RAM → eviction cliffs.
- Splits rewrite multiple pages + parent → write amp.
- Random dirty flushes still matter on SSD under high queue depth.
Insert until the leaf is full
Space in the leaf is the cheap path. Split is the write-amp path.
- 1
Traverse root → leaf
Binary-ish search inside each page. Fanout keeps height small. - 2
If space: insert ordered
Mark the page dirty in the buffer pool. Log the change. - 3
If full: split the leaf
Two pages + separator key to parent. Parent may split recursively. - 4
WAL then ack
Durable policy is still the log. Pages flush later.
Overview
B-Trees store sorted keys in fixed-size pages (blocks) with high fanout: internal nodes guide search; leaves hold entries (and often sibling pointers for range scans). Inserts that fill a page split; deletes may merge/underflow. A buffer pool caches pages in RAM; dirty pages flush asynchronously — but WAL is still required for durability.
Postgres and InnoDB are B-Tree-centric. Interview favorites: page size vs fanout, why splits cause write amplification, how shared_buffers / the buffer pool interact with WAL, and why random writes hurt spinning disks (and still matter on SSDs under high queue depth). Understanding buffer-pool eviction explains latency cliffs when the working set exceeds RAM.
This page is engine pages. Which Postgres access method you CREATE INDEX USING is B-tree vs hash vs GIN vs GiST.
Core mechanism
- Page/block size (often 8–16KB): unit of I/O and latching.
- Fanout: roughly
page_size / (pointer + key size). High fanout → short trees (3–4 levels for huge tables). - Search: root → internal → leaf (binary-ish within a page).
- Insert: find leaf → if space, insert ordered; else split leaf into two, push a separator key to the parent (parent may split recursively).
- Delete: remove; if underflow, merge or redistribute with a sibling (engine-specific; often lazy in practice).
- Sibling pointers on leaves: efficient range scans / index-only scans.
- Buffer pool: hash table of cached pages; clock/LRU variants; dirty pages written by background writers; WAL before durable page write.
Point updates touch scattered leaf pages → random I/O. Bulk-sorted loads and sequential scans are kinder. Page splits write multiple pages + parent → write amplification.
Postgres vs InnoDB shape
- Postgres: heap + B-Tree indexes;
shared_buffers; WAL; hint bits; vacuum for dead tuples (MVCC interacts with space reuse — VACUUM). - InnoDB: clustered index B+Tree as primary table organization; secondary indexes store PK; buffer pool + redo.
Comparative
| Structure | Pros | Cons |
|---|---|---|
| B+Tree (leaf-linked) | Great range scans; stable height | Page-split write amp; random dirty flushes |
| Hash index | Fast equality | No ranges; growth/rehash pain |
| LSM | Sequential writes | Read amp / compaction — LSM lesson |
| In-memory tree | Lowest latency | Durability and capacity limits |
Insert + split flow
Decisions
- 1
1. Insert key K
- next2. Traverse root to leaf L
- 2
2. Traverse root to leaf L
- next3. Space in L?
- ?
3. Space in L?
- yes4. Insert in sorted order
- no5. Split L into L1 and L2
- 4
4. Insert in sorted order
- next10. WAL log change; mark dirty
- 5
5. Split L into L1 and L2
- next6. Promote separator to parent P
- 6
6. Promote separator to parent P
- next7. Space in P?
- ?
7. Space in P?
- yes8. Insert separator
- no9. Split P recursively or new root
- 8
8. Insert separator
- next10. WAL log change; mark dirty
- 9
9. Split P recursively or new root
- next10. WAL log change; mark dirty
- 10
10. WAL log change; mark dirty
- next11. Ack after durable policy
- 11
11. Ack after durable policy
Lesson map
B-Tree Internals — Pages, Splits & Buffer Pool
Pages, fanout, leaf/internal, splits; buffer pool caches dirty pages async; WAL still required; Postgres/InnoDB.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB a["1. Insert key K"] b["2. Traverse root to leaf L"] c["3. Space in L?"] d["4. Insert in sorted order"] a -->|1. Insert key K to 2. Traverse root to leaf L| b b -->|2. Traverse root to leaf L| c c -->|yes| d
Sandbox: leaf split sketch (Python)
Fixed-capacity leaf only — not a full B-Tree.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Buffer-pool mental model (TypeScript)
WAL is assumed external. Evicting a dirty page would flush it.
Press Run. Snippets must be self-contained — no network, files, or native modules.
Interview Q&A
B-Tree vs B+Tree?
Answer
B+Tree keeps all values in leaves and links leaves — the standard for DB indexes. Internal nodes are separators only. That is why range scans and index-only scans are cheap.
Why high fanout matters?
Answer
Tree height ≈ log_fanout(N). Fewer levels → fewer I/Os per lookup (often 3–4 even for billions of keys).
What causes write amplification in B-Trees?
Answer
Splits rewrite pages; updating the parent; WAL + eventual page flush; secondary indexes multiply per-row write cost. Numbers: amplification.
Can the buffer pool make WAL unnecessary?
Answer
No. RAM is volatile. WAL (or equivalent) is required for durable commits across crash. WAL lesson.
Clustered vs secondary index (InnoDB)?
Answer
Primary/clustered organizes row data. Secondary stores the PK and needs a lookup to the clustered leaf unless the query is covering.
Why 8KB/16KB pages?
Answer
Balance I/O size, latch granularity, and wasted space from half-full pages after splits. Tiny pages → more I/Os and height; huge pages → more contention and split waste.
What is a latch vs lock?
Answer
Latching protects physical page structures in memory (short). Locks / MVCC protect transactional semantics (longer). Do not mix the words in an interview.
Sequential scan vs index lookup tradeoff?
Answer
Large selectivity → seq scan wins (fewer random jumps). Point / highly selective → index. Cost models estimate this. Which AM: B-tree vs hash vs GIN vs GiST.
Pitfalls
Draw a leaf with fanout 4, insert until it splits, then split the parent. Count pages written (leaves + parent + WAL). Then say what happens if that dirty leaf is still only in the buffer pool when power fails.