Skip to content

B+ Tree

Why B+ Trees?

  • ISAM requires overflow block usage, which makes execution slower
  • Periodic reoragnisation of the full file is requied
  • B+ trees reorganise themselves with small local changes, and do not need such reorganisation.
  • Note that they come with a minor space overhead, but it is worth the efficiency.

Example

Pasted image 20220416164501.png

Constraints

  • All paths from root ot a leaf are of the same length
  • A tree of size n can have up to \(n-1\) values and \(n\) children
  • Each node has at least half-filled children (rounded up)
  • Each node is at least half-full (rounded up)
  • A B+ Tree counts as a multi-level sparse index.
  • The tree height is no more than \(\lceil log_{\lceil n/2 \rceil} (K) \rceil\) height, for \(K\) search key values.
  • A node is generally the same size as a disk block, 4KB.