B+ Tree Visualization
A B+ Tree is a self-balancing search tree and a variant of the B-Tree. Like a B-Tree, each internal node can hold multiple keys and have more than two children. The key difference is that in a B+ Tree all data records are stored only in the leaf nodes, while internal nodes act purely as routing guides. Leaf nodes are also connected in a linked list (shown by the dashed green arrows), enabling efficient range queries without traversing the tree.
When inserting a new key, it is placed into the appropriate leaf node. If the leaf overflows, it splits — the smallest key of the right half is copied (not moved) up to the parent as a separator, so the key remains in the leaf. This copying behaviour is what distinguishes a B+ Tree from a B-Tree. Internal nodes split using the traditional median-push approach. The splitting process can propagate upward and may create a new root, always keeping all leaves at the same depth.
For simplicity, the order of this B+ Tree visualizer is fixed to 3.
AI Summary
(3 credits)
Common Interview Questions
Why does a B+ Tree support range queries more efficiently than a B-Tree?
B+ Tree leaf nodes are linked in a sorted linked list. A range query only needs one O(log n) traversal to find the start key, then a linear scan along the leaf chain to collect all records in range — no backtracking up the tree. In a B-Tree, data scattered across internal nodes forces repeated upward/downward traversals.
What are the time complexities for search, insert, and range queries in a B+ Tree of order m with n keys?
All three basic operations — search, insert, and delete — run in O(log n) with a base of m (tree height ~ logm n). A range query retrieving k records costs O(log n + k): one top-down traversal to the first leaf plus a linear scan of k leaf entries.
Why do relational databases use B+ Trees rather than B-Trees for table indexes?
B+ Trees give databases two key advantages: 1) Higher fanout — internal nodes hold only keys (no data records), fitting more separators per disk page and reducing tree height. 2) Efficient range scans — the leaf linked list enables BETWEEN, ORDER BY, and full table scans without revisiting internal nodes, which is critical for OLAP and query optimizers.
💬 Discussion
to join the discussion
Curious to Learn More?
Hand-picked resources to deepen your understanding
© 2025 See Algorithms. Code licensed under MIT, content under CC BY-NC 4.0