Free Indexes, queries and scale lessonsIndexes, queries and scale · Stage 1 · Indexes · Step 1
B+ tree indexes
See how a wide, shallow tree finds one row in a few page reads, and why its height barely changes as the table grows. About 14 minutes.
A table grows from 10 million to 20 million rows, with a B+ tree fanout of about 500. What happens to the index lookup cost?
- AIt almost certainly stays the same: the height is still 3
- BIt doubles
- CIt increases by a factor of about 1.4
Show the answer
It almost certainly stays the same: the height is still 3. Height grows with the log of the size; 500^3 = 125 million.
4 questions on this idea
Short questions that apply the idea to new cases: trace it, work out a number, put steps in order. A wrong answer explains itself.
Answer them in your browserFree account, no card. Your progress is saved, and the idea comes back in a quick review later.
Sign up free to solve