Beyond primary keys: how databases index real queries

A primary key is only the first index

A primary key answers one question very well: which single record has this ID? Applications quickly need other paths, such as every booking for a customer, every product in a category, or every document containing a term. Those paths need secondary indexes.

A secondary index can map one value to many records. The value can point to a list of matching record IDs, often called a postings list, or the database can make each index entry unique by pairing the value with the record ID. Both B-trees and LSM-trees can support this pattern. Secondary indexes are also a major building block for joins.

PRIMARY INDEX
record ID  ->  one record

SECONDARY INDEX
indexed value  ->  matching record IDs
customer_42    ->  [booking_8, booking_19]

An index can point to data or carry the data

The simplest secondary index stores a pointer to the real record in a heap file, an unordered area where records live. This avoids copying the same data into every index. It also creates a maintenance problem: if an updated record grows and must move, every affected pointer needs updating, or the old location must leave a forwarding pointer.

A clustered index stores the full row or document inside the index itself. InnoDB, for example, organizes a table around its primary key, while its secondary indexes refer back to that primary key. A covering index sits between these choices: it stores only the columns a query needs, so the database can answer that query without fetching the base record.

These are read versus write trade-offs, not free optimizations. Duplicating values can remove a lookup and speed reads, but costs space, extra write work, and transaction logic to keep copies consistent.

NONCLUSTERED
index  ->  heap location  ->  full record

CLUSTERED
index  ->  full record

COVERING
index  ->  columns needed by this query

The shape of a query decides the index

A composite index is ordered. An index on (last_name, first_name) can efficiently find everyone with a last name, or a person with both names, but it is usually a poor fit for a query on first name alone. Put the useful prefix first.

Some questions are genuinely multidimensional. A map search might need every restaurant within both a latitude and longitude range. A normal one-dimensional B-tree or LSM-tree can narrow one dimension, then filter the other. Spatial indexes such as R-trees are designed to narrow both together. Another option is to map a two-dimensional location to one sortable value with a space-filling curve.

The same idea applies beyond maps: color matching can use three RGB dimensions, and weather queries may combine date with temperature. Choose an index that matches the way the application filters data, not one that merely looks familiar.

COMPOSITE INDEX: (last_name, first_name)

last_name = 'Khan'                 -> efficient
last_name = 'Khan' AND first_name -> efficient
first_name = 'Aisha'              -> poor fit

latitude range AND longitude range
-> use a spatial index when both ranges matter

Full-text search is not normal key lookup

Exact-match and range indexes are not enough when people search with synonyms, grammar variations, nearby words, or spelling mistakes. A full-text engine needs to understand terms and search rules, not just compare raw strings.

Lucene is a useful example. It keeps a sorted on-disk term dictionary with an in-memory structure that can jump close to the right place. Its finite-state automaton represents shared character prefixes compactly, much like a trie. That structure can be transformed into a Levenshtein automaton to find terms within a chosen edit distance, where an edit means adding, removing, or replacing a character.

Fuzzy search is therefore a different problem class. Search engines may also use document classification or machine learning when a query needs more meaning than a conventional index can encode.

FULL-TEXT MATCHING
run  ->  running, ran
car  ->  related terms or synonyms
error ->  typo within edit distance

The index must support language and similarity,

Keeping data in memory does not remove durability work

Memory is faster and getting cheaper, while data can be partitioned across machines when it no longer fits in one. But RAM is normally volatile. A cache such as Memcached can accept data loss, while a durable in-memory database needs another survival path.

That path can be battery-backed memory, an append-only write log, periodic snapshots, replication, or a combination. After a restart, the system reloads state from disk or from another replica. A log on disk is still useful even if reads never touch it: it supports backups, inspection, and external analysis.

Different products make different promises. Some in-memory systems use a durable log and replication; others, including configurations of Redis or Couchbase, may persist asynchronously and accept weaker guarantees. The design question is always the same: how much recent data may disappear after a failure?

READS
client  ->  memory-resident index and data

WRITES
memory  ->  append log / snapshot / replica

RESTART
reload state from log, snapshot, or replica

Why memory can help even when the OS caches disk

The benefit is not simply that disks are slower. Operating systems already cache frequently used database pages in memory. In-memory engines can avoid the work of encoding in-memory structures into a disk-oriented format and decoding them again for every access.

They can also expose data structures that are awkward on disk. Redis, for example, can work naturally with sets and priority queues. Some systems use anti-caching: keep hot records in memory, evict cold records individually with an LRU policy, and reload them on demand. That is more record-aware than the operating system's page-level cache, although the index still has to stay in memory.

Nonvolatile memory may eventually change these boundaries, but the durable-data question does not disappear. It just moves closer to the data structure.

HOT RECORDS     -> RAM
COLD RECORDS    -> disk, reload when needed
INDEX           -> stays in RAM

Memory changes the cost of access.
It does not make recovery optional.

What I will carry forward

Indexing is a way to make common questions cheap. Start from the real query shape, then decide whether the data should be found by one key, many matching values, an ordered prefix, a region, or a fuzzy term. Every shortcut has a price in storage, write amplification, memory, and consistency work.

An in-memory database follows the same rule. It is not simply a database with no disk. It is a system that chooses where reads happen, how writes survive failure, and which data structures are worth keeping close to the CPU.

QUERY SHAPE
-> index structure
-> read speed
-> write and storage cost
-> recovery strategy

These are my personal learning notes from Designing Data-Intensive Applications by Martin Kleppmann.