Databases and Indexing (DBMS)

1The mental model (what this really is)#

A relational database is two things glued together.

• A place to store rows on disk safely.
• An engine that answers questions about those rows fast.

Everything interesting comes from one physical fact: disk is slow and memory is small.

• A random read off an SSD is tens of microseconds, off spinning disk is milliseconds, out of RAM is nanoseconds.
• That gap of a thousand to a million times is the entire story.
• The database cannot hold your whole table in RAM, and it cannot scan a billion rows per query.
• So it spends enormous effort avoiding reads: indexes avoid reads, the query planner avoids reads, the buffer pool avoids reads.

Second model: a table without an index is an unsorted pile of rows.

• To find something, you look at every row. That is a full table scan, O(n).
• An index is a separate sorted structure that points back into the pile.
• You jump close to the answer instead of walking the whole thing, O(log n), because the index is a tree.

Third model: transactions pretend the messy concurrent world is clean and sequential.

• ACID is the set of promises the database makes.
• They let you reason about your data as if you were the only one touching it, even when a thousand users are not.

2Why it matters / core idea#

The core idea an interviewer is testing: do you know the cost of what you are doing?

• An index is a trade. You pay on writes to save on reads.
• Every index makes INSERT, UPDATE, and DELETE slower, because the database keeps that extra sorted structure current.
• A table with five indexes writes to six places per insert, not one.
• It eats disk too, often as much as the table itself for a wide index.
• In return, specific reads get dramatically faster, turning a 50 million row scan into three page reads.

A senior engineer does not add indexes by reflex.

• They add them for queries that are both frequent and slow.
• They can tell you which queries those are.

The signal they listen for: when you say "add an index," do you immediately say which columns and why?

• Junior answer to "this query is slow": "add an index."
• Strong answer: "I'd run EXPLAIN first, see if it's doing a sequential scan on a column we filter by, and if so, add an index on that column, probably a composite one if we also sort by date."

Question you will get: "What is an index, in one or two sentences?"

• Strong answer: "A separate sorted data structure, almost always a B+ tree, that lets the database find rows in log time instead of scanning the table. It is a copy of one or more columns plus a pointer back to the row, kept in sorted order, and the database maintains it on every write."

3The data structures (how it actually works)#

Almost every relational index is a B+ tree. Know this cold.

• Postgres, MySQL InnoDB, SQL Server, Oracle: all B+ tree by default.
• It is a balanced tree with a high branching factor. Each node holds many keys, not two like a binary tree.
• The leaves are linked in a sorted list.

Why this shape? Because disk reads happen in fixed blocks (pages).

• Pages are usually 8KB in Postgres, 16KB in InnoDB.
• A wide node means one page read covers hundreds of keys, so the tree stays shallow.
• With a fan-out of a few hundred, even a billion rows sits in about 3 to 4 levels.
• Three or four page reads to find any row, and the top levels usually live in the buffer pool anyway. That is the whole point.

 [ 50 | 100 ] <- root (1 page read)
 / | \
 [..30..] [..70..] [..130..] <- internal nodes
 | | |
 leaves -> leaves -> leaves <- linked, sorted (range scans walk this)

The linked leaves are why B+ trees crush range queries.

• WHERE age BETWEEN 20 AND 30 finds the start, then walks the leaf chain. No jumping around.
• A plain binary search tree cannot do this efficiently, a good contrast to draw if they ask "why not a BST?"

The other structure to name is a hash index.

• O(1) exact-match lookup, but useless for ranges or sorting because hashing destroys order.
• Good for WHERE id = 5, hopeless for WHERE id > 5 or ORDER BY id.
• Postgres has them, almost nobody reaches for them, because a B+ tree is nearly as fast on equality and far more flexible.

One distinction that earns points: clustered vs non-clustered.

• Clustered index: it is the table. Rows are physically stored in the order of this key, sitting in the leaves of the tree. One per table, because data can only be physically sorted one way (usually the primary key). Looking up by it lands you right on the row, no second hop.
• Non-clustered (secondary) index: a separate structure whose leaves hold the key plus a pointer to the real row. Finding the row means a second hop. In InnoDB that pointer is the primary key value, so a secondary lookup is actually two B+ tree walks.

Question you will get: "How many clustered indexes can a table have, and why?"

• Answer: "One. The clustered index defines the physical order of the rows on disk, and rows can only be laid out in one order. Everything else is a secondary index pointing back."

4A worked example (walk it through)#

Say we have an orders table, 50 million rows, and this query is slow:

SELECT order_id, total
FROM orders
WHERE customer_id = 8812
 AND status = 'shipped'
ORDER BY created_at DESC
LIMIT 20;

Here is how I'd reason out loud in an interview.

Step 1: EXPLAIN first.

• Suppose it shows a sequential scan: the database is reading all 50M rows, filtering, then sorting.
• On 50M rows that is seconds, not milliseconds, and it gets slower every month.

Step 2: name what the query filters and sorts on.

• Filter: customer_id and status.
• Sort: created_at.
• So I want an index that covers both the filter and the sort.

Step 3: build a composite index (customer_id, status, created_at).

• Order inside a composite index is not cosmetic. The rule: equality columns first, then the range or sort column last.
• customer_id and status are both equality matches, so they lead.
• created_at goes last, and because the index is already sorted by it within each customer/status group, the database reads the top 20 in order and stops.
• No separate sort step, no scanning 50M rows. The plan goes from a sequential scan plus a sort to an index scan touching maybe a few dozen leaf entries.

Step 4: defend the column order.

• Why not (created_at, customer_id, status)? An index is sorted left to right, like a phone book sorted by last name then first name.
• Lead with created_at and you cannot efficiently jump to one customer. You would scan dates globally and filter customer the hard way.
• The leading column must be something you filter on with equality. This "leftmost prefix" rule is a favorite interview trap.

Step 5: consider making it covering.

• order_id and total are in the SELECT. Include them in the index and it becomes covering: the heap fetch disappears entirely.
• Worth it if this query is hot.
• The cost is a wider index and slightly slower writes, which I would say out loud, because naming the downside is the part that sounds senior.

5Variations and gotchas#

The leftmost prefix rule.

• An index on (a, b, c) helps queries filtering on a, or a, b, or a, b, c.
• It does not help a query filtering only on b. The sort order is useless without the leading column.
• This single idea explains half of "why isn't my index being used."

Functions kill indexes.

• WHERE YEAR(created_at) = 2026 cannot use a plain index on created_at, because the database would compute YEAR() on every row to check it.
• Rewrite as a range: WHERE created_at >= '2026-01-01' AND created_at < '2027-01-01'. Same logic, index-friendly.
• Postgres can index the expression itself with a functional index, but the range rewrite is the answer they want first.

Low cardinality is a waste.

• Indexing a boolean or a gender column rarely helps.
• If a value matches half the table, the database decides a full scan is cheaper than 25 million index-then-fetch hops. It may ignore your index, and it is right to.
• Random heap fetches cost more than a sequential scan once you are reading a big fraction of the rows.

Normalization vs denormalization.

• Normalization (splitting data to kill duplication, up to 3NF) keeps writes clean and prevents update anomalies. The classic: a customer's address stored in 10,000 order rows, so you have to update all 10,000 to change it.
• Denormalization (deliberately duplicating data) speeds reads by avoiding joins.
• The honest answer: normalize until joins hurt, then denormalize the hot paths on purpose, and own the duplication with triggers or application logic.
• Know the forms at a definition level: 1NF (atomic values, no repeating groups), 2NF (no partial key dependencies), 3NF (no transitive dependencies).

N+1 queries.

• The classic ORM disaster. You fetch 100 users, then loop and fire one query per user for their orders.
• 101 queries instead of one join or one WHERE user_id IN (...).
• Each round trip is a network hop, so 101 queries can be 100ms where one join is 2ms.
• Name this. It comes up constantly in real-world-flavored questions, and the fix is eager loading or a join.

6Trade-offs (the ACID and isolation section)#

ACID, in your own words:

• Atomicity: all of a transaction happens or none of it does. The classic transfer: debit one account, credit another. A crash in between must not lose money or create it. The database uses a log so it can undo a half-finished transaction on recovery.
• Consistency: the transaction moves the database from one valid state to another, respecting constraints like foreign keys, unique keys, and checks.
• Isolation: concurrent transactions do not step on each other, or at least appear not to.
• Durability: once committed, it survives a crash. This is why databases write to a write-ahead log on disk and fsync it before saying "done." The data pages can be flushed lazily afterward.

Isolation is where the hard questions live, because it is a dial, not a switch.

• Lower isolation means more speed and more anomalies.
• The anomalies, in increasing niceness of the level that prevents them:
• Dirty read: you read another transaction's uncommitted change, which may roll back, so you acted on data that never existed.
• Non-repeatable read: you read a row twice in one transaction and get different values because someone committed an update in between.
• Phantom read: you run the same WHERE twice and new rows appear because someone inserted rows matching your filter.

The levels:

Know the defaults, interviewers check.

• Most production systems run at Read Committed (Postgres default) or Repeatable Read (MySQL InnoDB default).
• Serializable is correct but slow: it has to either lock aggressively or abort and retry transactions that conflict.
• Know the default for whichever database is on your resume.

Modern engines pull this off with MVCC (multi-version concurrency control).

• Instead of locking readers out, they keep multiple versions of a row.
• Readers see a consistent snapshot from the moment their transaction started, while writers create new versions.
• Readers don't block writers, writers don't block readers.
• The cost is dead row versions that a process (Postgres calls it VACUUM) has to clean up later.
• Saying "MVCC" with a one-line explanation of the version snapshot is a strong signal.

7Mistakes that cost people the round#

• Reciting ACID as four nouns with no "why." Everyone can list them. Explain atomicity with the money-transfer example and durability with the write-ahead log instead.
• Saying "add an index" without EXPLAIN, without naming columns, without the write cost. It reads as cargo-culting.
• Not knowing indexes slow down writes. Present indexes as pure upside and you look junior. Every write touches every index.
• Blanking on composite index order. If you cannot explain why (customer_id, created_at) beats (created_at, customer_id) for a per-customer query, drill it until you can.
• Confusing clustered and non-clustered, or not knowing a table has exactly one clustered index.
• Treating SQL vs NoSQL as a religion. The adult answer is about access patterns. "It depends, here's on what" wins. "NoSQL is web scale" loses.

8Your practice path (study order)#

Do these in order. Each builds on the last.

1. Write and read EXPLAIN. Spin up Postgres locally, load a table with a million rows, run EXPLAIN ANALYZE. Watch a sequential scan become an index scan after you add an index, and watch the cost estimate drop by orders of magnitude. Feeling this once beats reading ten articles.
2. Drill composite index ordering. Given five queries, say which single composite index serves the most of them. Practice the leftmost-prefix reasoning until it's automatic.
3. Hand-trace a B+ tree. Insert 10 keys into a B+ tree with node capacity 3, draw the splits as nodes overflow. Then explain why it stays 3 to 4 levels deep even at a billion rows.
4. Narrate a money transfer across isolation levels. Walk two concurrent transactions and show which anomaly appears at Read Uncommitted, Read Committed, and Repeatable Read.
5. Design a schema out loud. Take "design the schema for a ride-sharing app," normalize it to 3NF, then pick three indexes and justify each by a specific query. This merges everything into one answer.

9Where this shows up#

Expect database questions almost everywhere.

• Backend and full-stack loops, and specifically the "systems" or "fundamentals" round at larger companies.
• Amazon and the big product companies love indexing and query-optimization questions because the scale is real: a missing index on a table they query millions of times a day is a real incident.
• Startups lean practical: "here's a slow query, fix it," or "how would you model this."
• System design rounds pull in SQL vs NoSQL, sharding, and replication once data outgrows one box.
• Even some phone screens sneak in an isolation-level question to separate people who have shipped from people who only read about it.

The common thread is cost awareness.

• If every answer includes the trade you are making and why, you sound like someone who has run a production database, not someone who crammed the night before.

Check the company guides to see which of these rounds lean hardest on databases, and tune your prep to the loop you're actually facing.