Pages a range query reads

How it behaves

One input on the horizontal axis, the others held fixed.

Worked examples, recomputed

Every number the mechanisms quote for this relationship is recomputed from it, so none of them disagrees with it.

• 50,000 rows at f = 100 → 500 sequential pages
• 50,000 random reads × 4 = 200,000: a 400× difference

Where it appears

Each mechanism states it in its own names. The general symbol each name stands for is shown with it.

• Indexing

  When does a separate "where is it?" structure pay for itself, and what does it cost to keep it true?

  $$\text{clustered}\approx k/f,\text{unclustered}\approx \min (k,N/f)$$

  Read it in place →