B-Tree
A wide, shallow search tree tuned for block storage; nodes hold many keys.
3 8 15 27 40 has 5 keys and the limit is 4, so it splits. The middle key, 15, moves up to the parent; the keys below it form the left node and the keys above it the right node.
What you will see
Wide nodes; a full node splits into two and promotes its middle key.
Cost
| search | O(log n) |
|---|---|
| insert | O(log n) |
| delete | O(log n) |
| Space | O(n) |
Height is O(log_t n) for minimum degree t; disk reads scale with height.
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.