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 logN\log N height.

Last updated