[prev] 22 [next]

B-Tree Depth

Depth depends on effective branching factor  (i.e. how full nodes are).

Simulation studies show typical B-tree nodes are 69% full.

Gives   load Li = 0.69 × ci   and   depth of tree ~ ceil( logLi r ).

Example: ci=128,    Li=88

Level #nodes #keys
root 1 87
1 88 7656
2 7744 673728
3 681472 59288064

Note: ci is generally larger than 128 for a real B-tree.