System Design · Databases
How to choose a data store, split it when it grows too big, and make it find rows fast — the three database decisions every system-design interview circles back to.
Databases force three separate choices, and they are independent. SQL vs NoSQL trades strong consistency against horizontal scale. Partitioning splits one big store into many so it can hold more and spread load. Indexing buys fast reads (O(log n)) with extra space and slower writes. In an interview you win by naming the trade-off out loud — there is no single right answer, only a justified one.
A dense, hand-copyable revision sheet. Everything here is derived from the detailed notes below.
| Axis | SQL | NoSQL |
|---|---|---|
| Data / schema | structured, fixed schema | unstructured, flexible/schemaless |
| Scaling | vertical (up); horizontal = hard (sharding) | horizontal (out) — built for it |
| Consistency | ACID → strong | BASE → eventual |
| Queries | joins, aggregation, nested — powerful | simple lookups, limited joins |
| Best for | banking, payments, inventory | social, chat, logging, analytics |
| Method | Rule | Watch |
|---|---|---|
| Hash / key | id % N | uniform; resharding hard → consistent hashing |
| Range | age 0–18 → A | uneven if ranges skewed |
| List | country ∈ {…} | value change → repartition |
| Round-robin | rec# % N | even, but no locality; range Q bad |
| Composite | country + hash | best balance; complex |
You launch a bank that pays 40% interest, and a million people rush to open accounts. Two problems land at once. First, when Priya transfers ₹10,000 to Sam, the money must never vanish or appear twice — you cannot be "roughly right" about balances. Second, a single database server cannot hold a million users, let alone a billion. One demand wants absolute correctness; the other wants raw scale. Almost every database decision in system design is a negotiation between those two pulls — and the three tools below are how you negotiate.
A database is just a place to store data — but which one you pick decides what you can promise your users. Both SQL and NoSQL stores hold data; the difference is the guarantees and the shape of the data they are good at. Before any brand name, understand the structured-store idea (a SQL database) versus the flexible-store idea (a NoSQL database).
SQL is a filing cabinet — every folder has the same labelled tabs (name, roll number, year), so you can cross-reference and audit precisely. NoSQL is a labelled junk drawer — each item can carry different fields, so you dump things in fast and sort out shape later. Neither is "better"; they suit different messes.
SQL stores fit structured, well-defined data: the schema — the table name, columns, data types, constraints (primary key, foreign key, unique, not-null), and relationships between tables — is fixed before you insert a single row. A school record always has a name, a roll number, a year; the shape never changes. NoSQL stores fit unstructured or semi-structured data where one record has five fields and the next has eleven, and you cannot predict them in advance. The schema is flexible and easy to evolve.
MySQL, PostgreSQL, Microsoft SQL Server, Oracle.
Amazon DynamoDB, Apache Cassandra, MongoDB, Azure Cosmos DB.
You are not expected to have used every product. If asked about SQL Server and you only know MySQL, say so — that is fine. Speak in terms of SQL vs NoSQL properties, and only name a specific engine if you can defend it, because naming one steers every follow-up question toward it.
Scaling is how you grow to handle more load; the two directions are "bigger machine" and "more machines." SQL databases primarily scale vertically — you add CPU, RAM, or storage to a single server (make the box bigger). NoSQL databases are designed to scale horizontally — you add more servers to a cluster (add more boxes). Horizontal scaling is possible in SQL too, but it is harder and is achieved through sharding, which is why NoSQL was invented in the first place: to store billions or trillions of records that no single machine could hold.
Consistency is the promise that everyone sees correct, agreed-upon data. SQL databases support ACID transactions, giving strong consistency — ideal wherever correctness is non-negotiable. NoSQL databases follow the BASE principle (Basically Available, Soft state, Eventual consistency): they favour staying available and scaling wide, and let all copies agree eventually.
Atomicity · Consistency · Isolation · Durability. A set of properties that keep transactions reliable even through a crash or power cut.
Basically Available · Soft state · Eventual consistency. Trades instant agreement for availability and scale.
The four ACID letters, in plain words:
| Letter | Means | In one line |
|---|---|---|
| Atomicity | all or nothing | a transaction fully completes or rolls back to the previous state — no half-done. |
| Consistency | valid → valid | every rule/constraint holds; if a balance is 10,000, all replicas show 10,000. |
| Isolation | no interference | concurrent transactions behave as if run alone; B won't read A's uncommitted change. |
| Durability | survives crash | once committed, the change persists even if the DB crashes right after. |
Atomicity is the ATM that either dispenses your cash and debits your account, or does neither — it never debits without paying out. That is why banking, payments, and airline booking live on SQL: a partial transaction is a disaster.
Some NoSQL engines (MongoDB, Cosmos DB) do offer transactions, but with different trade-offs than a traditional SQL system. The rule of thumb: if you cannot compromise on correctness, start with SQL.
Eventual consistency is the window during which a write on the master database has not yet been copied to every replica. A write lands on the master (primary) DB, then propagates to the slave (replica) DBs. If a read hits a replica during that copy window — say it takes 5 minutes — it sees stale data. Once propagation finishes, every copy agrees. Hence "eventual."
Don't say SQL is "eventually consistent" by default. In a strongly-consistent SQL system you take a write lock so no one reads a half-written record — the cost is added latency, since readers block during the write. SQL can expose looser reads via versioning/isolation levels, but its default posture is strong consistency. Eventual consistency is the design choice you associate with NoSQL. [!] The instructor initially called SQL's MVCC behaviour "eventual consistency"; the precise framing is that it's a tunable isolation/locking trade-off, not the same replica-lag eventual consistency as NoSQL.
SQL's query language is its superpower. It supports joins, aggregation, nested queries, and complex reporting — you can hang a BI dashboard straight off it. NoSQL is optimised for simple lookups with limited joins, and the query interface depends on the engine. So for rich analytics, SQL usually has the edge.
The instinct that "it must be one or the other" is wrong. A real system mixes stores per component. Amazon: SQL for payments (consistency), NoSQL for the product catalog (scale). An online game: NoSQL for real-time state, leaderboards, sessions (low latency, millions of players), SQL for accounts, purchases, and friend graphs (strong consistency). Answer by component, not by dogma.
Partitioning divides a large database into smaller, independent segments to improve performance, scalability, availability, and manageability. Each partition holds only a subset of the data. The banking scenario from the hook is exactly why: consistency says "stay on SQL," but a billion users won't fit on one box — so you split.
A single national phone book is unusable. Split it by region (rows go to different books) and every lookup touches a thin book. That is sharding. Alternatively, keep names in one book and photos in another (split by column). That is vertical partitioning.
Different rows live on different servers, chosen by a value. Users 1–1M on server A, 1M–2M on server B; or zip < 10,000 on A, ≥ 10,000 on B.
Different columns/features live on different servers. Instagram: user profile on server A, followers on server B, photos on server C.
+ improves scalability, reduces per-server DB size. − risk of uneven distribution (one shard becomes a hotspot); cross-shard queries get complex.
+ feature isolation, better resource use, easy to implement. − one feature (e.g. a celebrity's followers) can still outgrow its single server, forcing further partitioning.
Vertical's weakness (one feature outgrows its box) is fixed by then applying horizontal partitioning on that feature. Virat Kohli has 10M followers on the followers server? Hash-shard the followers table. Partitioning strategies compose.
The routing lives in the application code or a dedicated DB router/proxy — placed between the backend services and the shards — using the shard key (e.g. user ID). Some managed databases route for you.
A standard load balancer spreads incoming requests across servers — it does not decide which shard holds a given row. Sharding is done by the application or a database router using the shard key. Conflating the two is a classic interview slip.
| Method | How it decides | Pro | Con |
|---|---|---|---|
| Hash / key | partition = id % N |
uniform, prevents hotspots | adding/removing a server reshuffles data → use consistent hashing |
| Range | value bands (age 0–18 → A) | efficient range queries, intuitive | uneven if a range is dense |
| List | predefined value sets (country ∈ Nordic) | logical grouping, easy manage | value changes force repartitioning |
| Round-robin | rec# % N, one each in turn |
dead simple, even spread | no data locality; range queries inefficient; ignores load |
| Composite | combine two (country + hash) | best load balancing, handles huge sets | complex to implement & maintain |
Splitting 10M rows across 10 shards isn't only about capacity — each search now scans a smaller set, so queries get faster too. Scale and speed both improve, and indexing (next) then speeds lookups inside each shard.
An index is a data structure that speeds up data retrieval so the database can locate rows without scanning the whole table. Without it, a query does a full table scan — checks every row — and gets slower as data grows. With it, the database jumps straight to the record.
To find "mitochondria," you don't read every page — you flip to the index, read the page number, and jump. The index is a small sorted structure that points into a big unsorted body. That is exactly what a database index does.
Internally, most relational databases build indexes as B-trees / B+ trees (some support hash indexes). That is what turns the search from O(n) (scan every row) into O(log n) (tree descent). On millions of rows, that is the difference between "instant" and "the user gave up."
-- Without an index: full scan, O(n)
SELECT * FROM employee WHERE employee_id = 101;
-- Build an index on the column you filter by
CREATE INDEX idx_employee_id ON employee(employee_id);
-- Now the same query descends the B-tree: O(log n)
SELECT * FROM employee WHERE employee_id = 101;How it works: the index stores value → row location. The DB searches the (sorted) index, gets
the row number, then reads that row from the table and returns the record.
If you index email but query WHERE role_number = 7, the index is useless and
you're back to a full scan. Index the columns you actually filter, join, sort, or group by — not
whichever felt important.
Sharding splits data across servers for scale; indexing speeds search inside a shard. You shard on user ID, but if you search by email you still full-scan every shard unless each shard has an email index. Routing by shard key gets you to the right box; the index gets you to the right row. You need both.
An index costs extra disk space and slows writes — and that is the right trade. Spending space to cut time complexity from O(n) to O(log n) is exactly the pattern interviewers want to hear you reach for.
Auto-created on the primary key. Values unique, no nulls; often clustered by default.
On a non-PK column to speed searches. Duplicate values allowed.
Sets the physical storage order of rows. One per table (data has one physical order). Great for range queries; inserts/updates may reorganise data.
Separate structure of value → pointer to row; doesn't change physical order. Many
allowed. Behaves like an inverted index (tokens → row list).
Forbids duplicate values in the indexed column (e.g. email).
Holds every column the query needs, so the DB answers from the index alone — no table read. Very fast, less disk I/O.
WHERE oftenJOINedORDER BY / GROUP BY| Indexing — pros | Indexing — cons |
|---|---|
| Fast SELECTs, fewer full scans | Extra disk space |
| Faster sort / filter / range queries | Slower INSERT / UPDATE / DELETE |
| Better JOIN performance | Index needs maintenance as data changes |
Anchor on the requirement, not the brand: "The data is structured with strong relationships and the workload needs ACID guarantees — money can't be off by a cent — so I'll use a SQL store." Speak in properties (schema, consistency, query power) and only name an engine if you can defend it, since a brand name invites deep follow-ups. Signal that scale is handled via sharding if pressed.
ACID (SQL) guarantees each transaction is atomic, consistency-preserving, isolated, and durable — strong consistency at the cost of scaling friction. BASE (NoSQL) is Basically Available, Soft state, Eventual consistency — it stays available and scales horizontally by letting replicas converge over time. You pick ACID when correctness is non-negotiable and BASE when availability and scale dominate.
That's eventual consistency: the write landed on the master DB but hadn't propagated to the replica the read hit. During the copy window, replicas serve old data; once replication completes, all copies agree. It's characteristic of NoSQL/replicated setups. To avoid it you'd read from the master or use a strongly-consistent read, trading latency or availability for freshness.
Horizontal (sharding) splits by rows across servers — fails via uneven distribution (hotspots) and hard cross-shard joins. Vertical splits by columns/features across servers — fails when one feature (a celebrity's followers) outgrows its single server, which you then fix by horizontally sharding that feature.
No. A load balancer distributes incoming requests across servers; it doesn't know shard keys. Shard routing is done by the application code or a dedicated DB router/proxy that computes the target shard from the shard key (e.g. user ID). Some managed databases provide built-in routing.
Round-robin (rec# % N) gives a dead-simple even spread but ignores data locality and
load, and makes range queries inefficient because related rows scatter. Hash partitioning
(id % N) distributes uniformly and prevents hotspots, but adding/removing a server
reshuffles almost everything — which is why consistent hashing exists.
Yes — they solve different problems. Sharding scales storage and cuts rows per shard; it doesn't make search within a shard fast, and it only helps routing when you query by the shard key. Search by email while sharded on user_id and you full-scan every shard unless each shard indexes email. Index for speed inside the shard; shard for scale across shards.
A clustered index defines the physical order of the rows themselves — one per table, excellent for range queries, but inserts/updates may reorganise storage. A non-clustered index is a separate structure of value → pointer-to-row that leaves physical order untouched; you can have many, and it's ideal for frequent searches on non-primary columns (conceptually an inverted index).
It costs extra disk space and slows writes, but that's an intentional space-for-time trade: it collapses reads from O(n) to O(log n). On large, read-heavy tables that's overwhelmingly worth it. You avoid indexes on tiny tables, low-selectivity columns (gender/status), volatile columns, and write-heavy workloads where the maintenance cost outweighs the read gain.
Reading proves you recognise the ideas. These prove you can use them. Attempt each before opening the walkthrough.
You're designing a ride-hailing app. Two data needs:
(a) Wallet/payment ledger — every debit/credit must be exact and survive crashes.
(b) Live driver-location pings — millions per minute, schema may add fields, occasional
staleness is fine.
Requirements:
rider_id. Write the SQL
CREATE INDEX that makes that lookup O(log n), and name the index type.Expected result: (a) SQL — ACID/strong consistency. (b) NoSQL — horizontal scale +
flexible schema. Plus a secondary index on rider_id.
Step 1 — classify each need by its dominant requirement. The wallet's non-negotiable is correctness: a debit without a matching credit is a disaster, and it must survive a crash. That is the ACID signature → SQL. The location pings are the opposite: enormous write volume, an evolving payload, and a stale position for a second is harmless. That is horizontal scale + flexible schema → NoSQL.
Step 2 — index the query you'll actually run. Riders filter transactions by
rider_id, which is not the primary key of the ledger (the PK is the transaction id). So
build a secondary index on rider_id — non-PK, duplicates allowed (a rider has
many transactions).
-- (a) wallet → SQL, chosen for ACID / strong consistency
-- (b) driver pings → NoSQL, chosen for horizontal scale + flexible schema
-- secondary index: rider_id is not the PK, and repeats per rider
CREATE INDEX idx_txn_rider ON transactions(rider_id);
-- the lookup this accelerates (O(n) full scan -> O(log n) tree descent)
SELECT * FROM transactions WHERE rider_id = 4821;Why: you matched each store to its dominant requirement (correctness vs scale) instead of forcing one database everywhere, then indexed the exact column the read filters on — the space-for-time trade that turns a full scan into a few tree hops.
A junior engineer complains their query is "still slow even though I added an index." Their table is
sharded on user_id. Here's what they did:
CREATE INDEX idx_user_email ON users(email);
-- the query that's still slow:
SELECT * FROM users WHERE phone_number = '555-0142';Requirements:
SELECT.user_id doesn't rescue this.Expected result: a full table scan across every shard; the index is on the wrong column.
Predicted failure: no error is thrown — it silently runs a full table
scan, and because the query filters on phone_number (not the shard key),
it scans every shard. Slowness, not an exception, is the symptom — which is exactly
why it's confusing.
Root cause: the index is built on email, but the query filters on
phone_number — an index only accelerates the column it was built on.
Step 1 — index the column you actually filter.
-- build the index on the queried column
CREATE INDEX idx_user_phone ON users(phone_number);
-- now this descends the B-tree inside each shard: O(log n)
SELECT * FROM users WHERE phone_number = '555-0142';Step 2 — why sharding doesn't save you. The shard key is user_id. A
query by user_id routes to exactly one shard. But phone_number is
unrelated to the shard key, so the router can't narrow it down — the request fans out to all shards,
and within each shard, without a phone index, it's a full scan. Sharding gives scale; the index
gives speed inside the shard. You need the index regardless.
Why: this is the "index only helps its own column" pitfall stacked on the "sharding ≠ indexing" trick — the two most common ways a query stays slow after someone "added an index."