Interactive LabClient-side Simulation
B+ Tree Database Index
Interactive B+ Tree with node splits, key promotion, and leaf linked-list range scans.
Order M:
B+ Tree Index ready (Order M=3).
Range Scan [A, B]:to
Root (Internal Node)
50
Subtree < 50
30
Subtree ≥ 50
70
Leaf Nodes (Physical Record Storage & Doubly Linked List)
10
20
30
40
50
60
70
80
Why Databases (MySQL InnoDB) Use B+ Trees:
1. High Fanout & Low Tree Depth: A typical 16KB InnoDB page with 4-level B+ Tree can index over 20,000,000 rows with only 3 to 4 disk I/O reads.
2. High Speed Range Scans: Unlike standard binary search trees that require costly recursive in-order tree traversals, B+ tree leaf nodes are linked directly in a doubly-linked list. Once the first matching leaf node is located via binary search from root, subsequent records are scanned linearly along the leaf chain with sequential disk I/O.