B+ Tree
A B-tree where all values live in linked leaves, making range scans sequential.
Decision · step 5 of 23B-Tree: B+ tree: keys stay in the chained leaves
10 20 30 has 3 keys and the limit is 2, so it splits. The middle key, 20, is copied up to the parent and stays in the right leaf; the keys below it form the left node and the keys above it the right node.
What you will see
Internal nodes route; leaves form a linked chain that a range query walks.
Cost
| search | O(log n) |
|---|---|
| range scan | O(log n + k) |
| insert | O(log n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, try operations in any order.
Screen readers: Each element is an accessibility element with position, value and state; structural changes are announced per step.
Reduced motion: Elements appear at their destination with a crossfade; no travel longer than the element's own size.