Layer 3 · Go deeper · 8 min
Go deeper
Size it, build it, then make the calls an interviewer will push you on.
Back of the envelope
Size it up
Tap through each step of the arithmetic.
How many levels does a bigint B+tree need for 500 million rows?
Build-up · 5 steps
Walk a range through a B+tree
WHERE id BETWEEN 131 AND 420 on a three-level B+tree, drawn sideways with the root on the left and the leaves on the right.
Step 1 of 5
Leaves hold every key
Every index entry lives in a leaf page, sorted by key, as the key plus a pointer to its row. Each leaf links to its neighbours, which matters in a moment.
4 interview moments
You’re the candidate
The interviewer pushes on the hard parts. Pick an approach and see how it holds up.
Deep dive 1 of 4
Interviewer
“A food-delivery orders table takes 2,000 inserts a second at the lunch peak. A teammate wants an index on every column. Your call?”
Your move. Pick an approach:
Deep dive 2 of 4
Interviewer
“You’re creating a MySQL orders table with four secondary indexes. Which primary key do you choose?”
Your move. Pick an approach:
Deep dive 3 of 4
Interviewer
“On PostgreSQL, a URL shortener looks up long URLs by exact match,
WHERE url = $1, and never sorts them. Which index?”Say a URL is 100 bytes, and index size matters.
Your move. Pick an approach:
Deep dive 4 of 4
Interviewer
“Login runs
WHERE lower(email) = $1. There’s an index on email, yet every login scans the users table. What do you do?”Your move. Pick an approach:
Build-up · 5 steps
Find a user by email in two engines
One lookup by email, asha@x.in, on InnoDB and on PostgreSQL. The difference is where the row itself lives.
Step 1 of 5
One query, two engines
Same query, same index on email. What changes the cost is what an index entry points at, a key or a physical address.