B-Tree (BBST) for postings

Balanced B-trees

Pros:

  • Solves the prefix problem

Cons:

  • O(log M)
  • rebalancing binary trees is expensive
    • B-trees mitigate the rebalancing problem