17.4 B-Tree Invariants

B-Tree Invariants

Because of the way B-Trees are constructed, they have two invariants:

  1. All leaves are the same distance from the root.

  2. A non-leaf node with k items must have exactly k + 1 children.

These two invariants guarantee a "bushy" tree with log⁡N\log N height.

Previous17.3 B-Tree OperationsNext17.5 B-Tree Performance

Last updated