Cases:

• best: find tuple in first data page we read
• worst: full binary search, and not found
  • examine log₂b data pages
  • plus examine all of their overflow pages
• average: examine some data pages + their overflow pages

Cost_one :     Best = 1      Worst = log₂ b + b_ov

Average case cost analysis relies on assumptions  (e.g. data distribution)