Every system design interview reaches the same moment. You have drawn the boxes, and the interviewer points at the cylinder and asks, "Which database would you use here?"
A weak answer is a brand name. A good answer is a short reason. This note gives you both halves of that reason: how to choose a kind of database, and how the thing that makes any database fast (the index) really works.
Start with a boring answer
Here is my honest advice, and I will say it early so it does not get lost.
Start with Postgres unless you can say why not.
Postgres is a relational database (data lives in tables with rows and columns, and you ask questions in a language called SQL). It handles money, users, orders, JSON blobs, text search and even simple queues. One Postgres server on a decent machine can hold a few terabytes and answer thousands of queries a second. Most products never outgrow it.
The mistake almost everyone makes is picking an exotic database on day one because it sounds like it scales. Then they spend a year working around missing features, such as joins or transactions, that Postgres gave them for free.
So the rule for interviews is simple. Pick the boring option first. Move away from it only when you can point at a number or a requirement it cannot meet. "We need 200,000 writes a second" is a reason. "NoSQL scales better" is not.
The six families
Databases come in a few families. Each one is good at one shape of data and one shape of question.
Relational (SQL)
Data sits in tables. Tables point at each other with ids. You can join them, filter them, group them, and wrap several changes in one transaction (a bundle of changes that either all happen or none happen).
Examples: Postgres, MySQL. Good for orders, payments, users, inventory, anything where the data has clear links and mistakes cost money.
Document
Each record is a self contained document, usually JSON. A user and all their addresses can live in one document. There is no fixed shape forced on every record.
Examples: MongoDB, Firestore. Good when you mostly read and write one whole thing at a time, like a product page or a user profile, and the shape changes often. It gets painful when you need to join lots of documents together.
Key value
The simplest idea there is. You give it a key, it gives you back a value. Nothing else. No filtering by what is inside the value.
Examples: Redis, DynamoDB (it can do more, but this is its core). Good for sessions, caches, counters, rate limits, shopping carts. Very fast, very easy to spread over many machines, and very limited in the questions you can ask.
Wide column
Think of a giant table where each row can have its own set of columns, and the rows are spread across many machines by a row key. It is built for huge write volumes and for reading a slice of one row's data.
Examples: Cassandra, HBase, Bigtable. Good for time series, message history, event logs, activity feeds. You must design the table around the exact queries you will run. Ad hoc questions are hard.
Graph
Data is dots and lines. People are dots, "follows" or "knows" are lines. The database is built to walk along lines quickly, like "friends of friends of friends".
Examples: Neo4j. Good for recommendation, fraud rings and social links. Honestly, it is rare in interviews. Many teams that think they need one are fine with a relational table of edges.
Search engine
A search engine keeps an inverted index: for every word, a list of the documents that contain it. That is why it can find "red running shoes" in a hundred million products in milliseconds, and rank the results.
Examples: Elasticsearch, OpenSearch. Good for full text search, filters over many fields, and log search. It is not a good main database. Treat it as a second copy of your data, built for searching, that you refill from your main store.
A simple decision table
| You need | Reach for | Why |
|---|---|---|
| Links between data, transactions, flexible queries | Postgres or MySQL | Joins and safe multi step changes |
| One whole object per read, shape changes a lot | Document store | No joins, no schema fights |
| Look up by one key, very fast, huge volume | Key value store | Nothing to do but get and put |
| Millions of writes a second, time ordered data | Wide column store | Built to absorb writes |
| Walk through many layers of relationships | Graph database | Following links is its job |
| Search by words, fuzzy match, ranking | Search engine | Inverted index |
Notice that most real systems use more than one. A food delivery app might keep orders in Postgres, sessions and caches in Redis, and restaurant search in Elasticsearch. That is normal. One source of truth, plus a few helpers shaped for specific jobs.
How to choose, in order
When you are stuck, ask these questions in this order.
It is a rough guide, not a law. Its real job is to make you say your reasoning out loud.
One more honest note on SQL versus NoSQL. The old story was "SQL does not scale, NoSQL does". That is mostly out of date. Postgres with read replicas and sharding scales a long way, and many NoSQL stores now offer transactions. The real difference today is which questions are easy to ask. SQL makes new questions cheap. Many NoSQL stores make a few planned questions extremely fast, and everything else hard.
Now the second half: indexes
Whatever database you pick, the same problem shows up. You have 50 million rows and you want the one with email = 'asha@example.com'.
Without help, the database reads every row from the top and checks each one. This is called a full table scan. At 50 million rows it takes seconds, and it gets slower every month as the table grows.
An index is the help.
What an index is
Open a thick textbook and look at the index at the back. It lists topics in alphabetical order, and next to each one are page numbers. You do not read 800 pages to find "photosynthesis". You flip to the back, find the word quickly because the list is sorted, and jump to the page.
A database index is the same thing. It is a separate, sorted list of the values in one or more columns, and next to each value is a pointer to where the full row lives.
CREATE INDEX idx_users_email ON users (email);
SELECT * FROM users WHERE email = 'asha@example.com';After the first line, the second query no longer scans 50 million rows. It looks in the sorted list, finds the pointer, and goes straight to the row.
The table itself is not touched or reordered. The index is extra data, kept on the side, and the database keeps it up to date for you.
B-tree in plain words
The sorted list in most databases is stored as a B-tree. You do not need to draw one with perfect rules in an interview. You need the picture and the numbers.
Think of a sorted list that is too big to search from one end. So you build a little guide on top of it, a page that says "names A to F go left, G to M go middle, N to Z go right". Each of those points to another page that splits the range finer. At the bottom are the leaf pages, which hold the actual values and the pointers to rows.
To find "ravi", you read the root, go right, read one page, go right, read the leaf. Three page reads, not 50 million row checks.
Now the part that surprises people. Each page holds hundreds of entries, not two or three. If every page points to about 500 children, then:
- 3 levels cover 500 x 500 x 500, about 125 million entries
- 4 levels cover about 62 billion entries
So even on a table with a billion rows, finding one value takes roughly 4 page reads. The top levels are almost always sitting in memory, so in practice it is one or two reads from disk. That is why an index lookup stays fast no matter how big the table gets.
B-trees are also sorted, so they do more than exact matches. Range questions like created_at BETWEEN a AND b, ORDER BY, and name LIKE 'Ash%' work well, because the answers sit next to each other in the leaves.
Why reads get faster and writes get slower
The index is not free. Every time you insert, update or delete a row, the database has to update the table and every index on that table.
Say your orders table has five indexes. One new order now means six writes: one for the row, five for the indexes. And the new entry has to go in the right sorted place, which may mean splitting a full page into two.
So the trade is plain:
- A read that used to scan a million rows now reads about four pages.
- A write that touched one place now touches one plus the number of indexes.
An index also takes space. Indexes on a big table can be as large as the table itself.
My rule of thumb: add an index when you have a real query that needs it, and not before. Tables that are mostly read, like a product catalog, can carry many indexes. Tables that are written constantly, like an event log, should carry as few as you can get away with.
A common beginner mistake is to index every column "just in case". That makes writes slow, wastes disk, and most of those indexes never get used.
Composite indexes and the leftmost rule
Often one column is not enough. Say you have this table, and this is the query that runs all day:
SELECT * FROM orders
WHERE user_id = 7 AND status = 'paid'
ORDER BY created_at DESC;You can build one index over several columns, in a chosen order:
CREATE INDEX idx_orders_user_status_created
ON orders (user_id, status, created_at);Here is the picture to keep in your head. A phone book is sorted by last name first. Inside each last name, it is sorted by first name. It would be useless for finding everyone called "Priya" across all last names, because the Priyas are scattered through the whole book. But it is great for "Sharma, Priya".
A composite index works the same way. It is sorted by the first column, then within ties by the second, then within ties by the third. That gives us the leftmost rule: the index helps only if your query uses a left to right prefix of the columns.
Let us test it on (user_id, status, created_at).
| Query filters on | Uses the index? | What happens |
|---|---|---|
| user_id | Yes | Jumps to that user's block |
| user_id and status | Yes | Narrows to that user's paid orders |
| user_id, status and created_at | Yes | Fully used, and rows come out already sorted |
| user_id and created_at (skip status) | Partly | Uses user_id only, then checks created_at row by row |
| status only | No | Paid orders are scattered across every user |
| created_at only | No | Same problem, no left part to start from |
Order matters when you design it. A reasonable habit is to put the columns you test with = first, and the column you range over or sort by last. Our ORDER BY created_at at the end works because, once user and status are fixed, the entries are already sitting in created_at order, so the database skips the sorting step.
If you also need to look up by status alone all the time, that is a different query, and it deserves its own index.
Covering index
Normally the database finds the entry in the index, then follows the pointer to the table to fetch the full row. That second trip is extra work.
A covering index contains every column the query needs, so the database never visits the table at all.
CREATE INDEX idx_orders_cover
ON orders (user_id, status, created_at, total);
SELECT status, created_at, total
FROM orders
WHERE user_id = 7;Every column in that query, both filtered and returned, lives in the index. The answer comes straight out of it. It is like a book index that also printed the one line you wanted, so you never open the book.
The cost is a fatter index and slower writes. Use it for a few very hot queries, not everywhere.
When an index is ignored
You made the index, and the query is still slow. Almost always it is one of these.
Wrapping the column in a function. The index is sorted by the raw value, not by the result of your function.
-- cannot use an index on email
WHERE LOWER(email) = 'asha@example.com'
-- can use it
WHERE email = 'asha@example.com'(Some databases let you build an index on the expression LOWER(email) itself. That works too.)
A wildcard at the front. LIKE 'Ash%' can use the sorted order, because everything starting with "Ash" sits together. LIKE '%sha' cannot, because there is no sorted place to start.
Skipping the leftmost column of a composite index, as in the table above.
Mismatched types. Comparing a number column to a string can force the database to convert every row first.
Low selectivity. Selectivity means how much an index narrows things down. An index on a gender column or a is_deleted flag splits the table into two big halves. If the query would return half the table anyway, the database decides that a full scan is cheaper than jumping back and forth, and it ignores your index. It is right to do so.
Out of date statistics. The database picks a plan using estimates about your data. If those are stale, it can pick badly. Running the database's analyze command refreshes them.
The tool to check all of this is EXPLAIN. It shows you the plan the database chose, and whether it scanned the table or used an index. In an interview, saying "I would run EXPLAIN on it first" is a small thing that signals real experience.
LSM trees, at a high level
B-trees have one weakness. A write goes into a specific sorted place on disk, which means random disk access, page splits and rewrites. When you write a lot, it hurts.
Some databases take a different route, called an LSM tree (log structured merge tree). Cassandra, HBase, RocksDB and LevelDB use it. Here is the idea in a tea shop.
Picture a shop owner who gets orders all day. Writing each one neatly into the big sorted ledger would be slow. So she jots each order on a quick notepad on the counter first, in the order they arrive. Fast. When the notepad is full, she sorts it once and files it away as a sorted sheet. Later, in a quiet hour, a helper merges the old sorted sheets into bigger sorted sheets.
The database does the same:
- A write goes to an in memory table (the notepad) and, for safety, is also appended to a log file on disk. Appending to the end of a file is the fastest thing a disk can do.
- When the memory table fills up, it is written out as one sorted, immutable file.
- In the background, compaction merges those files together and drops old or deleted values.
Writes become very cheap. The price lands on reads. A value could be in memory or in any of several files, so a read may have to look in a few places. Databases soften this with a small filter per file that says "this key is definitely not in here", which lets them skip most files.
So the tradeoff in one line: B-trees favor reads, LSM trees favor writes. That is why write heavy stores such as message history, metrics and event logs lean on LSM trees, and why a classic relational database leans on B-trees.
Interview talking points
Do not recite a list of databases. Tie the choice to the data and the questions.
A short pattern that works:
- Say what the data looks like and how it is read. "Orders have clear links to users and items, and we need transactions for payment."
- Name the default and why. "So I would start with Postgres."
- Say what would make you change your mind, with a number. "If writes grow past what one primary can take, say tens of thousands a second sustained, I would look at sharding, or move the event stream to a wide column store."
- Add helpers only for a clear job. "Search over products goes to Elasticsearch, fed from the orders database. Sessions go to Redis."
For indexes, say what you would index and give the cost. "I would add a composite index on user_id and created_at, because the order history page filters by user and sorts by time. That makes the read cheap, and it costs a little on every insert, which is fine because orders are written far less often than they are read."
Interviewers love when you mention the cost without being asked. It shows you know an index is a trade, not magic.
Interview questions to check yourself
"You have no special requirements and need a database for a new app. What is your default, and what would make you move away from it?"
Postgres. Move only for a concrete reason, like write volume one machine cannot take, or a need like full text search that a helper store handles better.
"Why does a B-tree lookup stay fast even when the table has a billion rows?"
Each page holds hundreds of entries, so the tree is only about 4 levels deep. That means roughly 4 page reads, and the top pages are usually in memory.
"You have an index on (user_id, status, created_at). Does a query that filters only on status use it?"
No. The leftmost rule says the query must use a left to right prefix. Without user_id there is no place to start in the sorted order.
"Name two reasons a database might ignore an index you created."
Wrapping the column in a function, a leading wildcard in LIKE, skipping the leftmost column, or low selectivity so a full scan is cheaper.
"Why do write heavy databases like Cassandra use LSM trees instead of B-trees?"
LSM trees turn writes into appends to memory and a log, then merge sorted files later. That avoids random disk writes, at the cost of reads checking more places.