Skip to content

B+ Trees

1. What is it? (2-3 lines)

A B+ Tree is a self-balancing \(m\)-way search tree optimized for block storage devices. Unlike binary search trees, all key-value data is stored strictly in leaf nodes, while internal nodes store only routing keys; all leaf nodes are linked sequentially in a doubly-linked list.

2. Why does it exist?

Disk I/O operates on fixed-size blocks (e.g. 4KB-16KB pages). Standard Binary Trees or B-Trees require high tree depth, causing \(O(\log_2 N)\) disk seeks. B+ Trees have a high fan-out factor (hundreds of keys per node page), resulting in shallow trees (depth 3-4 for billions of records) and enabling sub-millisecond point lookups and ultra-fast range scans.

3. Where is it used?

  • Relational Storage Engines: MySQL (InnoDB), PostgreSQL (nbtree), Oracle, SQL Server.
  • Filesystems: NTFS, XFS, ext4.

4. How does it work? (simple flow)

  1. Tree Traversal (Point Lookup): Start at root node page \(\rightarrow\) Compare search key against internal routing keys \(\rightarrow\) Follow child pointer down \(\rightarrow\) Repeat until leaf node page is reached (\(O(\log_B N)\) disk page reads).
  2. Leaf Lookup: Scan the leaf node page to locate the exact data record (or record pointer).
  3. Range Query: Perform point lookup for the start key \(\rightarrow\) Traverse the doubly-linked list of leaf pages sequentially until end condition is met (zero root-to-leaf re-traversals!).
  4. Page Split (Insert): If a leaf page exceeds its byte limit (e.g., 16KB), it splits into two 50% full pages, and the median key is pushed up to the parent node.
  5. Page Merge (Delete): If a page drops below minimum occupancy (underflow), it merges with a sibling page.

5. Advantages

  • Shallow tree height (depth 3-4 handles billions of rows), minimizing disk I/O reads.
  • Extremely fast range scans via contiguous doubly-linked leaf page traversal.
  • Predictable \(O(\log N)\) point lookup, insert, and delete search performance.

6. Limitations

  • Write Amplification & Random Disk Writes: Modifying a single key requires reading, updating, and rewriting an entire page (16KB) to disk.
  • Page Split Latency Spikes: Node page splits trigger cascading locks/latches up the tree, causing latency spikes.
  • High memory fragmentation under random non-sequential primary key writes (e.g., UUID primary keys).

7. Common interview questions (10)

  1. What is the fundamental difference between a B-Tree and a B+ Tree?
  2. How does page size (e.g. 16KB in InnoDB) determine B+ Tree fan-out and tree height?
  3. Why are UUID primary keys notorious for causing B+ Tree page fragmentation?
  4. How do doubly-linked leaf nodes optimize SQL BETWEEN and ORDER BY range queries?
  5. What are B+ Tree Latches (read/write latches) and how do they differ from ACID database locks?
  6. How does Index Condition Pushdown (ICP) optimize B+ Tree traversal?
  7. What happens to B+ Tree structure during a high-concurrency page split?
  8. Why are LSM Trees preferred over B+ Trees for write-heavy workloads?
  9. How does PostgreSQL implement B-Tree index deduplication (v12+)?
  10. How does a B+ Tree handle composite multi-column index keys (colA, colB)?

8. Common misconceptions

  • Misconception: Internal nodes in a B+ Tree hold data rows. Fact: Internal nodes store only routing keys and child page pointers; data rows exist strictly in leaf pages.
  • Misconception: B+ Trees are kept entirely in RAM memory. Fact: B+ Tree pages reside on disk; frequently accessed internal pages are cached in the database Buffer Pool.

10. 30-second cheat sheet

  • Architecture: Internal nodes = Routing keys only; Leaf nodes = Data + Doubly-linked list.
  • Key Metric: High Fan-Out (\(B \approx 1000\)) \(\implies\) Tree depth 3-4 \(\implies\) Extremely low disk I/O.
  • Strength: Read-heavy OLTP workloads and fast range scans.
  • Weakness: High write amplification and fragmentation under random UUID inserts.