[prev] 20 [next]

B-Trees

B-trees are MSTs with the properties:
  • they are updated so as to remain balanced
  • each node has at least (n-1)/2 entries in it
  • each tree node occupies an entire disk page
B-tree insertion and deletion methods
  • are moderately complicated to describe
  • can be implemented very efficiently
Advantages of B-trees over general MSTs
  • better storage utilisation (around 2/3 full)
  • better worst case performance (shallower)