System design · Module 13 of 29 · Level 3: Data

Choosing a database

There are dozens of database products, but only about ten families, and each is shaped by what it's good at. The skill isn't knowing every product; it's matching your access patterns, consistency needs and scale to the right family, starting from a relational default and moving away only for a reason you can say in one sentence.

New to this?Start with B4 · Storing data and B5 · Data structures behind systems in Level 0; this module assumes it.

1. The idea

A kitchen has a fridge, a freezer, a spice rack, a pantry and a recipe book. You could keep everything in the fridge, and for a small household that works. As the kitchen grows, each kind of food goes where it keeps best and is easiest to reach, but you still keep one shopping list so you know what you actually have.

Ask four questions before naming any product:

How is the data read and written? By one key? By ranges of time? By ad-hoc filters and joins? By text search or similarity? Access patterns matter most.
What must be correct? Money, inventory and bookings need transactions and strong consistency. Likes, views and feeds can be eventually consistent.
How much, how fast? Gigabytes or petabytes; hundreds or millions of writes a second (Module 03 tells you).
Who runs it? A managed service your team can operate well beats a theoretically better one nobody understands.

The families

Family	Shape and strength	Pick it when	Examples
Relational	Tables, joins, constraints, transactions, any query	The default; anything with relationships and rules	PostgreSQL, MySQL
Distributed SQL	Relational and transactional, spread over many machines and regions	You need SQL and transactions beyond one machine, or multi-region writes	Spanner, CockroachDB, YugabyteDB, Aurora DSQL
Key-value	Get and put by key, very fast, scales nearly without limit	Access is by a known key: sessions, carts, profiles, counters	DynamoDB, Redis/Valkey, etcd (small config)
Document	JSON-like documents, nested data, flexible fields	Records vary a lot in shape and are read whole	MongoDB, Firestore, Couchbase
Wide-column	Rows grouped by partition key, sorted within it; LSM-based, write-optimised	Huge write volumes with a few known queries: messages, events, IoT	Cassandra, ScyllaDB, Bigtable, HBase
Search	Inverted indexes, relevance ranking, typo tolerance, facets	Text search and filtering over many fields	Elasticsearch, OpenSearch
Time-series	Timestamped points, compression, rollups, retention	Metrics, monitoring, sensor data	Prometheus, TimescaleDB, InfluxDB, VictoriaMetrics
Analytical (columnar)	Columns stored together; scans and aggregates billions of rows	Dashboards, reporting, data science (OLAP), not serving apps	ClickHouse, BigQuery, Snowflake, Redshift, DuckDB
Graph	Nodes and edges, traversals many hops deep	Deep relationship queries: fraud rings, recommendations by path	Neo4j, Amazon Neptune
Vector	Nearest-neighbour search over embeddings	Semantic search, RAG, recommendations (Module 29)	pgvector, Pinecone, Weaviate, Milvus, OpenSearch

OLTP vs OLAP. Apps run on OLTP databases: many small reads and writes, each touching a few rows, fast. Analysis runs on OLAP systems: few huge queries over many rows. Don't run heavy reports on the database serving users; copy the data to a warehouse.

2. How it works

One product, several stores

Large systems use several databases, each for the job it's best at. This is polyglot persistence. Press Play to build an online shop's data layer one need at a time.

Keeping the copies in step

With several stores, one must be the source of truth and the others derived from it. The robust way is change data capture (CDC): read the database's own change log (PostgreSQL's write-ahead log, MySQL's binlog) with a tool such as Debezium and publish every change to a stream (Kafka), which feeds the search index, cache and warehouse. Writing to two stores from application code ("dual writes") seems simpler but breaks when one write succeeds and the other fails; Module 22 covers the outbox pattern that fixes it.

Modelling for a NoSQL store: start from the queries

Relational modelling starts from entities and lets you query any way later. Key-value and wide-column modelling starts from the queries and shapes each table to answer one of them with a single lookup. For "a chat channel's latest messages" in Cassandra:

CREATE TABLE messages (
  channel_id bigint, bucket int,        -- partition key: one channel, one 10-day bucket
  message_id timeuuid, author_id bigint, body text,
  PRIMARY KEY ((channel_id, bucket), message_id)
) WITH CLUSTERING ORDER BY (message_id DESC);   -- newest first within the partition

One partition read returns the latest messages already sorted. A different query ("messages by author") would need a second table with the data copied in. That's the trade: fast, predictable reads at any scale, but no ad-hoc queries and more write work.

3. Try it yourself

Tick what's true for the system you're designing. The chooser suggests a primary store and any additions, with the reason for each.

4. Trade-offs

Flexibility vs scale

Relational databases answer questions you didn't plan for. Key-value and wide-column stores scale further and more predictably, but only answer the questions you designed tables for.

Every extra store has a cost

Another system to run, secure, back up, monitor and keep in sync. Add one when a need is real and measured, not because it might be.

"Schemaless" isn't free

Document stores move the schema from the database into your code. Every reader must handle every old shape of the data that was ever written.

Managed vs self-run

Managed services (DynamoDB, Aurora, Atlas, Bigtable) remove operational work but tie you to a vendor's limits, pricing and features. Know the limits you'll hit.

5. In real systems

PostgreSQL as a multi-tool: with jsonb, full-text search, PostGIS and pgvector (which supports HNSW and IVFFlat indexes), one PostgreSQL instance can cover documents, search, geography and vectors for small and medium products. Move a workload out when it outgrows it.
DynamoDB limits shape designs: items up to 400 KB, and each partition delivers at most 3,000 read units and 1,000 write units per second, so the partition key must spread load (Module 15).
Cassandra (current release line 5.0) and ScyllaDB are the usual answer for very high write rates with tunable consistency. Discord, for example, has written publicly about storing trillions of messages this way.
Distributed SQL (Spanner, CockroachDB, YugabyteDB, Aurora DSQL) gives transactions across regions, at the cost of higher write latency, because commits need agreement across distant replicas (Module 21).
Analytics almost always means a separate columnar warehouse fed by CDC or batch exports, so reports never slow down the production database.

The technologies up close

The default answer in an interviewPostgreSQL by default, and name the reason whenever you choose something else, with numbers: Messages: 200k writes a second, read by channel and time, eventual consistency is fine, so Cassandra partitioned by channel and bucket. Avoid exotic choices to impress; interviewers reward the boring correct one.

Cassandra (wide-column)

Situational · huge write volume, known queries

A distributed, wide-column database built for availability and very high write throughput on commodity machines. Eventually consistent by default, write-optimised (an LSM tree), with no single leader.

How it works

Data model: keyspace → table → rows. The primary key = partition key + clustering columns. The partition key decides which nodes hold the row; clustering columns sort rows inside the partition (PRIMARY KEY ((channel_id, bucket), message_id)). No joins, no foreign keys, no multi-row transactions.
Placement: a consistent-hashing ring with virtual nodes (Module 15); each row is copied to the next N nodes, spread across racks and data centres (NetworkTopologyStrategy).
Tunable consistency per query: ONE, QUORUM (a majority), ALL. QUORUM writes plus QUORUM reads overlap on at least one replica, so reads see the latest write.
Writes: commit log (durability) → memtable (memory) → flushed to immutable SSTables. Updates and deletes are new entries; a delete writes a tombstone. Conflicts resolve by timestamp: last write wins.
Reads: memtable, then SSTables newest first, skipping files with bloom filters. Compaction merges SSTables and drops tombstones.
Membership and failures: nodes gossip with each other; any node can coordinate a request. A down replica's writes are kept as hints and replayed when it returns (hinted handoff); repair fixes longer gaps.

Status today (checked October 2026)

Cassandra 5.0 is the current stable line (5.0.9, August 2026), adding storage-attached indexes (SAI) and vector search; 6.0 is in alpha. ScyllaDB is a compatible rewrite in C++. Discord, Netflix and Apple are well-known users.

Model from the queries. Discord stored messages as PRIMARY KEY (channel_id, message_id) with time-sortable Snowflake IDs; busy channels made partitions huge, so they moved to ((channel_id, bucket), message_id) with 10-day buckets, keeping each partition bounded.

Use it when

Messages, events, activity logs, IoT and time series at very high write rates
Availability matters more than strict consistency
A few well-known query patterns, each served by its own table

Skip it when

Payments, inventory, anything needing transactions
Joins and ad-hoc queries or aggregations
Small or moderate scale, where PostgreSQL is simpler

In the interview

With numbers and a key: Messages: 200k writes a second, read by channel and time, eventual consistency is fine, so Cassandra with PRIMARY KEY ((channel_id, bucket), message_id), QUORUM writes and reads.

🚩 Red flags

Naming Cassandra without a partition key and clustering order. The design is the key; expect "what's your partition key, and how big does a partition get?"
Using it for money or inventory. No multi-row transactions; last write wins silently drops concurrent updates.
Unbounded partitions (one partition per busy channel forever). Bucket by time.
Heavy deletes without knowing about tombstones, which slow reads until compaction.

DynamoDB (managed key-value)

Situational · key lookups at any scale

AWS's fully managed key-value and document store: you define a partition key (and optional sort key), and it scales throughput and storage automatically.

How it works

Items are found by partition key, and sorted within it by an optional sort key; global secondary indexes give other access paths.
Items are limited to 400 KB, and each partition serves at most 3,000 read units and 1,000 write units a second, so the key must spread load.
Strongly consistent reads, conditional writes (ConditionExpression) and multi-item transactions are available; global tables replicate across regions.

Status today (checked October 2026)

Mature and widely used; billed per request (on-demand) or per provisioned capacity. Its design ideas come from Amazon's Dynamo paper, though the service itself is different.

Use it when

Lookups by a known key at large or spiky scale: sessions, carts, profiles, device state
Serverless stacks on AWS
Teams that want no database operations

Skip it when

Ad-hoc queries, joins, reporting
Workloads that would need table scans

In the interview

DynamoDB with user_id as partition key and created_at as sort key; it handles sharding and rebalancing for us.

🚩 Red flags

A low-cardinality or skewed partition key (country, status): hot partitions.
Planning on Scan for normal requests: it reads the whole table.
Choosing it, then needing ad-hoc queries the access patterns didn't plan for.

MongoDB (document)

Situational · rarely the interview answer

Stores JSON-like documents; related data is usually embedded in one document and read whole.

How it works

Collections of documents with flexible fields; secondary indexes on any field; multi-document ACID transactions (since version 4.0); horizontal scaling by a shard key, with automatic balancing of chunks.

Status today (checked October 2026)

Mature and popular; MongoDB 9.0 is the current release (October 2026), and Atlas is the managed service. Firestore and Couchbase are other document stores.

Use it when

Records whose shape varies a lot, read and written as a whole (product catalogues with very different attributes, CMS content)
The interviewer says the schema changes constantly

Skip it when

Data with many relationships and joins
When PostgreSQL's jsonb already covers the flexible part

In the interview

Only with a stated reason: Product attributes vary wildly by category, so a document per product; orders stay in PostgreSQL.

🚩 Red flags

"Schemaless, so it's more flexible" as the reason. The schema still exists, in your code.
"MongoDB has no transactions": outdated by years; interviewers notice.
Choosing it for relational data and then simulating joins in the application.

Elasticsearch and OpenSearch (search)

Situational · search beyond the database

Search engines built on inverted indexes (word → documents), with relevance ranking, typo tolerance, facets and aggregations.

How it works

Documents are indexed into shards; a query fans out to the shards and merges the best results. New documents become searchable after a refresh (about a second by default), so it's near-real-time. It's a derived store: fed from the main database by change data capture, never the source of truth.

Status today

Elasticsearch and its open-source fork OpenSearch are the standard choices; managed versions exist on every cloud. PostgreSQL full-text search covers simpler needs.

Use it when

Relevance-ranked search, fuzzy matching, typeahead, faceted filters
Very large search corpora and log analytics

Skip it when

Simple keyword search over tens of millions of rows or fewer: PostgreSQL tsvector with a GIN index first
As the primary database

In the interview

PostgreSQL is the source of truth; CDC streams changes into Elasticsearch for full-text search, a second or so behind.

🚩 Red flags

Elasticsearch as the system of record.
Writing to the database and the search index from app code (dual writes); use CDC or an outbox.
LIKE '%word%' as a search plan: it can't use a B-tree index.

Distributed SQL

Specialised · multi-region transactions

Relational databases that spread data and transactions over many machines and regions: Spanner, CockroachDB, YugabyteDB, Aurora DSQL.

How it works

Data is split into ranges, each replicated with consensus (Module 21). Transactions across ranges coordinate between replicas, which can be far apart, so writes pay cross-region round trips.

Status today

Production-proven (Spanner behind many Google services; CockroachDB and YugabyteDB widely deployed). Costlier and slower per write than a single-region PostgreSQL.

Use it when

Strong consistency and SQL across regions, with writes accepted everywhere
Global financial ledgers, inventory shared by regions

Skip it when

Single-region apps: PostgreSQL with replicas is simpler and faster

In the interview

Only for multi-region writes: Balances need ACID writes from three regions, so Spanner-style distributed SQL, accepting ~100 ms commits.

🚩 Red flags

Proposing it for a single-region app "for scale". Explain the latency cost or don't name it.

Graph databases

Rare · almost never the answer

Nodes and edges stored for fast traversal many hops deep: Neo4j, Amazon Neptune.

How it works

Each node keeps direct references to its neighbours, so walking "friends of friends of friends" doesn't need repeated index lookups.

Status today

Mature for niche workloads. Big social graphs mostly run on sharded relational or key-value stores: Facebook's social graph (TAO) is built on MySQL.

Use it when

Queries many hops deep: fraud rings, recommendation paths, network topology

Skip it when

"Users follow users": a follows table with two indexes handles it

In the interview

Rarely: Followers are a table follows(follower_id, followee_id) with indexes both ways.

🚩 Red flags

A graph database for a follower list. One or two hops are joins, not graph traversals.

Time-series and columnar stores

Situational · metrics and analytics

Time-series databases store timestamped points with compression, rollups and retention; columnar (OLAP) stores scan and aggregate billions of rows.

How it works

Both store data by column and time rather than by row: compression is high and scans are fast, but single-row updates are slow. Time-series: Prometheus, TimescaleDB, InfluxDB, VictoriaMetrics (Design D18). Columnar: ClickHouse, BigQuery, Snowflake, Redshift, DuckDB.

Status today

Standard for monitoring and analytics; fed from the app database by CDC or batch exports.

Use it when

Metrics, monitoring, sensor data
Dashboards and reports over large history

Skip it when

Serving user requests that read or update single rows

In the interview

Reports run on a columnar warehouse fed by CDC, so they never slow the production database.

🚩 Red flags

Running heavy reports on the database that serves users.

Before you add a second database

The default · "should we add X?"

The most senior database answer is often "not yet". A new store solves one workload and adds a permanent bill that never appears in its benchmark: someone must back it up, upgrade it, monitor it and fix it at night, for as long as it exists.

How it works

Price it first. Each line is a real cost, paid every month:

Backups, and a restore that someone actually runs on a schedule.
Dashboards and alerts someone knows how to read at 3 a.m.
Version upgrades without downtime, written down and rehearsed.
On-call engineers who can diagnose it, not just restart it.
Every new hire learning two systems, and keeping the copies in step (section 2 above).

Then see how far the database you already run stretches. PostgreSQL covers more than its reputation:

Need	Inside PostgreSQL	You've outgrown it when…
Semantic search	pgvector, with HNSW indexes	Tens of millions of vectors with tight latency and heavy filtering, or the index no longer fits in memory
Text search	Built-in full-text search (`tsvector`, GIN indexes)	You need typo tolerance, facets, relevance tuning or search across many languages
Time-ordered data	Partitioning by time, BRIN indexes, the TimescaleDB extension; drop old partitions instead of deleting rows	Ingest or retention jobs, not queries, become the daily pain
Reports on live data	A replica just for reports; materialised views refreshed every few minutes	Scans of months of data, joined across many tables: that's a warehouse (Module 23)
Relationships	Recursive queries (`WITH RECURSIVE`)	Many-hop traversal is the product itself (fraud rings, recommendations)
Throwaway fast data	`UNLOGGED` tables (no write-ahead log: emptied after a crash, not replicated)	You need it shared across services at very high rates: use Redis

If you still add it, put a seam in front of it. Reach the new store through one small module with a narrow interface (search(query, filters), not raw query language spread through the code). Then replacing it later is a contained migration, not a rewrite.

Status today

pgvector, TimescaleDB and the built-in features above are all in active use in 2026. Thresholds are rough; measure your own workload before deciding.

Use it when

Someone proposes a new store for one feature
"Should we use a vector database?"

Skip it when

The workload is the product's core and clearly beyond one relational database (a search engine company, a metrics vendor)

In the interview

I'd start with pgvector in the Postgres we already run, behind a small search module. If we pass tens of millions of vectors with tight latency, we move that module to a dedicated vector store, and nothing else changes.

🚩 Red flags

Five databases for five features on a team of six.
No exit plan: the new store's query language spread through every service.

6. Remember it

Memory hook: "Postgres until proven otherwise"Start relational. Move a workload to another family only when its access pattern, scale or consistency needs prove it, and keep one source of truth.

How this hook works: what "Postgres until proven otherwise" means

What the slogan means, phrase by phrase

"Postgres": Stands for "a mature relational database": PostgreSQL, MySQL, or a managed version. Transactions, joins and flexibility come free.
"until": It's a starting point, not a religion. Many systems outgrow it for specific workloads.
"proven otherwise": Proof is a number or a pattern: 300k writes a second, petabytes of events, fuzzy text search, similarity search, aggregations over billions of rows.

Why this picture fits: it reverses the most common mistake, picking the database first and discovering the requirements later, and it forces a stated reason for every extra store.

The story → the concept

In the kitchen	In the system
The fridge that holds most things	The relational database
The freezer for bulk	A wide-column or object store for huge volumes
The spice rack within reach	A key-value cache
The recipe book's index	A search engine
The one shopping list	The source of truth, with CDC keeping the others in step

Watch it on an example

A new SaaS product starts on PostgreSQL: accounts, projects, tasks, comments. Fine for years.
Activity logs grow to billions of rows and slow down backups: proven. They move to a time-partitioned table, later to object storage plus a warehouse.
Users ask for fuzzy search across all content: proven when PostgreSQL's full-text search isn't enough. Add OpenSearch fed by CDC.
Everything else stays in PostgreSQL, which remains the source of truth.

The trap it saves you from

Starting with five databases for a product with a thousand users, and paying for the complexity long before any of them was needed.

It still works when…

You design at huge scale from day one (an interview "design WhatsApp"): the proof comes from your estimates, so you state it and choose accordingly.

7. Common mistakes

Using a cache or search index as the source of truthRedis and Elasticsearch can lose or reorder data during failures. Keep the truth in a durable database and rebuild the rest from it.

Choosing NoSQL "because it scales"Without a scale requirement that a relational database can't meet, you give up joins and transactions for nothing.

Modelling a key-value store like a relational oneNormalised tables in DynamoDB or Cassandra need many lookups per request. Design one table per access pattern.

Dual writes from application codeWriting to the database and then the search index separately leaves them out of step whenever one fails. Use CDC or an outbox.

Analytics on the production databaseOne big report query can starve user traffic. Send analytics to a warehouse or a read replica.

8. Design exercise (25 minutes)

Choose for five systems: a bank ledger, a ride-hailing app's live driver locations, a news site's article search, an IoT fleet sending a reading every second from 10M devices, and a social graph's "people you may know". Name the family and the reason.
Query-first modelling: for the IoT fleet, write the partition key and sort key for "readings for one device over the last 24 hours".
Draw the data flow for the shop in section 2: which store is the source of truth for what, and how each derived store is kept current.
Check the chooser: enter one of your systems into the widget. Do you agree with it? What would change its answer?
Write it down: the four questions from section 1.

9. Self-check quiz

Bookings, payments and inventory with strict rules. Which family?

Transactions and constraints keep money and inventory correct. Scale it with replicas and sharding if needed.

"Revenue by country by week over the last three years", run by analysts. Where?

Columnar stores scan and aggregate huge tables efficiently, without slowing the app's database.

What's the most reliable way to keep a search index in step with the main database?

CDC reads the database's own commit log, so every committed change reaches the index, in order, even after failures.

Where does data modelling for Cassandra or DynamoDB start?

Each table is designed to answer a specific query with one partition read; data is copied across tables as needed.

Your Cassandra messages table uses PRIMARY KEY (channel_id, message_id), and a few huge channels are slowing everything down. What's the usual fix?

((channel_id, bucket), message_id) keeps each partition bounded, as Discord did with 10-day buckets.

With replication factor 3, which consistency levels guarantee a read sees the latest acknowledged write?

2 + 2 > 3, so the read and write sets overlap on at least one replica.

A team of five wants a dedicated vector database for a new search feature with 2 million documents. What's the strongest first answer?

2 million vectors fits easily; the new store's running cost outweighs its benefit until scale proves otherwise, and the interface keeps the move cheap later.

10. Go deeper

Resource	Time	Why
Designing Data-Intensive Applications, chapters 2–3	3 h	Data models, query languages and storage engines: the reasoning behind every family.
NoSQL design for DynamoDB (AWS docs)	30 min	Access-pattern-first modelling, explained by the people who built it.
How Discord stores trillions of messages (Discord engineering blog)	20 min	A real migration between wide-column stores, with partitioning lessons.
Debezium documentation	30 min	How change data capture reads database logs and streams every change.

11. Under the hood (optional)

How search engines, vector indexes and geospatial indexes really find the closest matches. Not needed for most interviews; open it when you want to know how the products really do it. All the deep dives are listed on the Under the hood page.

Search, vectors and geospatialAnalyzers and BM25 with a live lab, near-real-time segments, query-then-fetch, HNSW and IVF with a recall lab, filtered vector search, geohash lab, 8 products comparedabout 40 min

Search engines, vector databases and geospatial indexes all answer "which items are closest to this?" without comparing against everything. Text search uses inverted indexes, vector search uses graphs and clusters over embeddings, and geo search turns two dimensions into one with space-filling curves.

Inverted indexes and BM25

Indexing runs each document through an analyzer (split into tokens, lowercase, drop stop words, reduce words to a stem) and records, for each term, the list of documents containing it: the posting list, with frequencies and positions. A query looks up each term's list and scores the matches. Try a query against six product pages:

BM25 (the default in Lucene, Elasticsearch, OpenSearch and Solr) rewards a term that's rare across documents (inverse document frequency), counts repeats with diminishing returns (k1 = 1.2), and penalises long documents (b = 0.75).
Phrases ("trail running") need positions in the postings, to check the terms are adjacent.
Speed: posting lists are sorted by document ID and compressed in blocks (delta plus bit-packing), with skip data to jump ahead; Lucene's term dictionary is a compact finite-state transducer. Block-max WAND skips whole blocks that can't reach the current top 10, so top-k queries don't score every match.
Autocomplete and typos: edge n-grams or FST-based suggesters for prefixes; edit-distance (fuzzy) queries or n-gram indexes for typos.

Near-real-time indexing and distributed search

Segments are immutable. New documents collect in an in-memory buffer; a refresh (every second by default in Elasticsearch, for indexes that are being searched) writes them as a new small segment that searches can see. A translog keeps acknowledged writes durable until a flush commits segments to disk.
Updates and deletes don't change segments: a delete marks the document in a bitmap, an update is a delete plus a new document. Background merges combine small segments and drop deleted documents, like LSM compaction.
Query then fetch: the coordinating node sends the query to one copy of every shard, each returns its top-k IDs and scores, the coordinator merges them, then fetches only the winning documents. Deep pagination (page 1,000) is expensive because every shard must return 10,000+ candidates, so use search_after cursors.

Vector search: approximate nearest neighbours

Embeddings place similar items near each other in hundreds of dimensions. Exact search compares the query with every vector; approximate indexes look at a small fraction and accept missing a few true neighbours (measured as recall@k). Here 400 vectors (in 2D so you can see them) are clustered into 8 lists, as an IVF index does:

Method	How	Knobs and trade-offs	Where
HNSW	A layered graph: start at a sparse top layer, move greedily toward the query, drop a layer, repeat	`M` (links per node), `ef_construction`, `ef_search`: higher means better recall, more memory and time	pgvector, Lucene, Qdrant, Weaviate, Milvus
IVF	k-means clusters; search only the nearest `nprobe` lists	Cheap to build; recall depends on nprobe; rebuild when data drifts	pgvector IVFFlat, FAISS, Milvus
Product quantization	Split each vector into sub-vectors and store a short code for each	Huge memory savings; re-rank top candidates with full vectors	FAISS, Milvus
DiskANN, ScaNN	DiskANN: graph on SSD with compressed vectors in memory; ScaNN: anisotropic quantization	Billions of vectors per machine; very fast quantized search	Azure, AlloyDB, Milvus; Google

Filters are the hard part. "Nearest products in stock under $50" filtered after a top-10 search may return nothing; filtering during the graph walk can disconnect it. Engines handle this with filtered traversal, iterative scans (pgvector 0.8+), or partitioning by the filter (per tenant).
Distances: cosine for normalised text embeddings, dot product when magnitudes matter, L2 for geometric data; use what the embedding model was trained with.

Geospatial: turning 2D into 1D

B-trees and sorted sets index one dimension. Space-filling curves (Z-order for geohash, Hilbert for S2) number the cells of a grid so nearby places usually get nearby numbers, and a "near me" query becomes a few range scans over neighbouring cells.

Scheme	How	Where
Geohash	Interleave longitude and latitude bits (Z-order), base-32 encode; each character narrows the cell	Redis GEO (52-bit geohash as a sorted-set score), many apps
Quadtree	Split a square into four until each holds few points; adapts to density	In-memory indexes for nearby search (D14)
R-tree	Nested bounding rectangles around shapes	PostGIS (via GiST), SQLite R*Tree, InnoDB spatial indexes
BKD tree	A k-d tree built in blocks on disk	Lucene geo points and numeric ranges
S2	Project the sphere onto a cube, order cells along a Hilbert curve; 31 levels	MongoDB 2dsphere, Google services
H3	Hexagonal cells at 16 resolutions; every neighbour is the same distance away	Uber and ride-hailing, aggregation by area

The edge problem: two points a few metres apart on opposite sides of a cell boundary can share no prefix at all, so always search the cell and its 8 neighbours, then filter by exact distance.

Product by product

Product or method	How it works	The detail worth knowing
Elasticsearch / OpenSearch (Lucene)	In-memory buffer, refresh into segments, translog; query then fetch across shards	Near-real-time: a write is searchable after the next refresh
Solr, Vespa, Typesense, Meilisearch	Solr is Lucene; Vespa has its own engine with real-time indexing and tensor ranking; Typesense keeps its index in RAM; Meilisearch uses memory-mapped LMDB files	Choose by operations and ranking needs, not feature lists
pgvector	HNSW and IVFFlat inside PostgreSQL	Vectors next to your rows, with SQL filters and transactions
FAISS, Milvus	IVF, PQ, HNSW, GPU indexes	The toolbox behind many vector databases
PostGIS	Geometry and geography types, R-tree over GiST	KNN ordering with the distance operator uses the index
MongoDB 2dsphere	Shapes converted to S2 cells in a B-tree	2D search as 1D range scans
Redis GEO	Geohash as a sorted-set score; GEOSEARCH scans neighbour cells	Geo on top of an ordinary sorted set
Elasticsearch geo	BKD trees for points; geo_shape for shapes	The same structure serves numeric ranges

Say it in the interview

Answers that show depth

"Why isn't a new product searchable immediately?" Lucene makes documents visible when the buffer is refreshed into a segment, about every second; we accept that, or refresh on demand for the writer's own view.
"How does vector search stay fast at 100 million items?" An HNSW or IVF-PQ index visits a tiny fraction of vectors, trading a little recall (tuned with ef_search or nprobe and measured against exact search) for milliseconds.
"Find drivers within 2 km." Index locations by geohash or H3 cell, query the cell and its neighbours, then filter by exact distance; refresh positions every few seconds.

In BM25, why does a match on a rare word like "grippy" count more than a match on a common one like "running"?

Inverse document frequency rewards terms that distinguish documents.

Raising nprobe in an IVF index (or ef_search in HNSW) does what?

More lists or candidates are examined, finding more true neighbours at more cost.

Why must a geohash "nearby" query also search neighbouring cells?

The Z-order curve jumps at boundaries, so proximity in space isn't always proximity in the hash.