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.

flowchart TD
  A[["Primary index"]] --> B["Record ID"] --> C[("One record")]
  D[["Secondary index"]] --> E["Indexed value"] --> F["Matching record IDs"]
  F --> G["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.

flowchart TD
  A[["Nonclustered index"]] --> B["Heap location"] --> C[("Full record")]
  D[["Clustered index"]] --> E[("Full record")]
  F[["Covering index"]] --> G["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.

flowchart TD
  A[["Composite index: last_name, first_name"]] --> B["last_name = Khan: efficient"]
  A --> C["last_name + first_name: efficient"]
  A --> D["first_name alone: poor fit"]
  E{"Latitude and longitude ranges both matter?"} --> F[["Use a spatial index"]]

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.

flowchart TD
  A["Full-text matching"] --> B["run: running, ran"]
  A --> C["car: related terms or synonyms"]
  A --> D["error: typo within edit distance"]
  B --> E(["Index supports language and similarity"])
  C --> E
  D --> E

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?

flowchart TD
  A[/Client read/] --> B[["Memory-resident index and data"]]
  C["Memory writes"] --> D[("Append log, snapshot, or replica")]
  E(["Restart"]) --> F["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.

flowchart TD
  A["Hot records"] --> B(["RAM"])
  C["Cold records"] --> D[("Disk, reload when needed")]
  E[["Index"]] --> F(["Stays in RAM"])
  B --> G["Memory changes access cost"]
  D --> G
  G --> H["Recovery remains required"]

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.

flowchart TD
  A{"Query shape"} --> B[["Index structure"]]
  B --> C["Read speed"]
  B --> D["Write and storage cost"]
  B --> E["Recovery strategy"]

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