A B-tree node holds several sorted keys, and the keys split the node’s children into ranges, so one node visit narrows the search many ways at once. A new key goes into a leaf; a leaf that overflows splits in two and pushes its median key up, which can ripple to the root. The tree only grows taller when the root splits.
- Typical operation
- O(log n)
- Space
- O(n)