B+ Tree Database Index Visualizer (Page Splits & Range Scans)
Insert keys, watch node splits, and see why B+ Trees power relational database indexes. Visual breakdown of B+ Tree operations: root insertions, internal node routing, page splitting at fill factors, and sequential leaf node range scans.
B+ Tree Index vs Sequential Scan Visualizer
Compare O(log N) 3-level tree traversal against scanning 1,000,000 rows on disk.
Query Performance Comparison (1,000,000 Rows)
How It Works Under the Hood
B+ Trees are the backbone of relational database storage engines (MySQL InnoDB, Postgres). Unlike binary search trees that have poor cache locality and high tree height, B+ Trees are shallow, multi-way balanced search trees with a high branching factor (fan-out of 100+). In a B+ Tree, all actual record pointers reside exclusively in the leaf nodes, which are linked together in a bidirectional linked list. Internal nodes store only routing search keys. This design ensures that range scans (`BETWEEN X AND Y`) require only finding the first leaf node and walking the sequential pointers without traversing back up the tree.
Core Architectural Principles
- High fan-out: A 4-level B+ Tree with fan-out 100 can store over 100,000,000 index keys with only 3 to 4 disk page reads.
- Sequential leaf traversal: Range scans execute at sequential memory/disk speed across leaf page pointers.
- Page split and fill factor: Nodes split 50/50 when full; sequential primary keys (auto-increment) prevent random fragmentation.
When asked why databases use B+ Trees instead of Hash indexes or Binary Search Trees, answer: "Hash indexes cannot perform range scans, and binary trees have deep depth resulting in excessive random disk I/O. B+ Trees have massive fan-out and linked leaf nodes for rapid range queries."
Read and range scan optimization vs write amplification during node split rebalancing (LSM-trees offer faster writes).