AlgoInsight

System Design

How Indexing Works in Distributed Databases

On a single database, indexing is well understood. Spread the data across dozens of machines and a hard question appears: where does the index live? The answer shapes everything about how a distributed database performs. Here's how it works.

By Admin2026-06-1815 min readdistributed-databasesindexingshardingsystem-designdatabasesscalability

On a single database, indexing is a solved, well-understood problem: build a sorted structure (usually a B-tree) over a column, and lookups on that column get fast. But take that data and spread it across dozens or hundreds of machines - as every large-scale distributed database does - and a genuinely hard question appears: where does the index live? If the data is partitioned across many nodes, an index can't simply sit on "the" machine, because there isn't one. How you answer this question shapes how the whole distributed database performs, and it's one of the more subtle topics in data infrastructure - the kind of thing that separates engineers who've only used a distributed database from those who understand what it's actually doing underneath.

This guide walks through how indexing works when data is distributed: the two fundamental approaches, their trade-offs, and how real systems navigate them.

The setup: data spread across nodes

First, the context. A distributed database shards its data across many nodes, each holding a subset of the rows, assigned by a shard key (or partition key). A query that includes the shard key routes straight to the one node holding that data - efficient. (See the sharding guide for how this works.)

The problem indexing has to solve: you often need to query by something other than the shard key. If you shard users by user ID but need to look them up by email, the email isn't the shard key, so the database doesn't know which node holds a given email. An index on email would fix that on a single machine - but across many machines, where does that email index live, and how does it find the right node? This is the distributed indexing problem, and it's worth stressing that it's not a corner case: almost every real system needs at least one secondary access path beyond its shard key, so almost every distributed database has to answer this question. There are two fundamental answers.

Approach 1: Local (partitioned) indexes

The first approach: each node maintains its own index over just the data it holds. Every shard indexes its own local rows. So if you have an index on email, each node has an email index covering only the users stored on that node. This is sometimes called a local or partitioned index - the index is partitioned the same way the data is.

This makes writes simple and efficient: when a row is written to a node, that node updates its own local index, and nothing else is involved. The index update is local to the same node as the data - no coordination across machines. Writes stay fast.

But reads on a non-shard-key column become a problem. Suppose you query by email, which isn't the shard key. The database doesn't know which node holds that email, so it has to ask every node: "do you have this email?" Each node checks its local index and responds. This is a scatter-gather query - fan out to all nodes, gather the results. It works, but it hits every machine for a single lookup, which is expensive and gets slower as you add nodes.

graph TD
    Q[Query by email<br/>non-shard-key] --> ALL{Which node?<br/>Unknown}
    ALL --> N1[Node 1<br/>checks local index]
    ALL --> N2[Node 2<br/>checks local index]
    ALL --> N3[Node 3<br/>checks local index]
    N1 --> G[Gather results]
    N2 --> G
    N3 --> G
    G --> R[Combined result]

This diagram shows a scatter-gather query against local indexes. A query by email, which is not the shard key, doesn't know which node holds the data. So it fans out to every node - node one, node two, node three - each of which checks its own local index. The results are gathered and combined. This works but requires contacting every node for a single lookup, which grows expensive as the number of nodes increases.

So local indexes give you cheap writes but expensive non-shard-key reads (scatter-gather across all nodes). Good when writes dominate and most reads use the shard key.

Approach 2: Global indexes

The second approach: a single index spanning all the data, regardless of which node holds the underlying row. This global index is itself stored in the distributed system (partitioned across nodes), but partitioned by the indexed value rather than by the data's shard key. So a global index on email is partitioned by email - meaning all index entries for a given email range live together, on a known node.

This makes non-shard-key reads efficient. A query by email goes to the global email index, which is partitioned by email, so the database knows exactly which node holds that part of the index. It goes to that one node, finds the entry (which points to where the actual row lives), and retrieves it. No scatter-gather - a targeted lookup to the right index partition, then to the data. Reads on the indexed column are fast.

The cost lands on writes. When you write a row, its data goes to one node (by the shard key), but the global index entry for it belongs to a different node (by the indexed value). So a single write now has to update data on one node and an index entry on another node - a distributed operation spanning machines. This is slower and more complex, and it raises a consistency question: keeping the global index perfectly in sync with the data across nodes, on every write, is hard, so many systems update global indexes asynchronously (the index catches up shortly after the write rather than instantly), accepting slight staleness for performance.

graph TD
    W[Write row] --> D[Data → Node A<br/>by shard key]
    W --> I[Global index entry → Node B<br/>by indexed value]
    D --> X[Write spans two nodes]
    I --> X

This diagram shows a write with a global index. Writing a row sends the data to one node, chosen by the shard key, but the global index entry for that row belongs to a different node, chosen by the indexed value. So a single write must update two different nodes - the data on one and the index on another. This makes writes a distributed operation, slower and harder to keep consistent than the local-index approach.

So global indexes give you fast non-shard-key reads but expensive, harder-to-keep-consistent writes. Good when reads on a secondary column matter and you can tolerate write complexity or slight index staleness.

A worked comparison: looking up by email

Make the two approaches concrete with one scenario - a distributed user database sharded by user ID, where you need to look up users by email.

With local indexes: Each node has an email index over its own users. You look up an email. The system doesn't know which node holds it, so it sends the query to all, say, ten nodes. Each checks its local email index and reports back (nine say "not here," one says "found, here's the user"). The coordinator gathers the responses and returns the result. The lookup touched all ten nodes for one user - and if you grow to a hundred nodes, it touches all hundred. Meanwhile, writing a user was cheap: the new user went to one node, which updated its own email index, done.

With a global index: There's one email index spanning all users, partitioned by email across the nodes. You look up an email. Because the index is partitioned by email, the system computes which node holds that email's index partition and asks only that node. It returns a pointer to the user's actual location, and the system fetches the user. Two targeted hops, no scatter-gather - and this stays efficient whether you have ten nodes or a thousand. But writing a user was more expensive: the user data went to one node (by user ID), while the email index entry went to a different node (by email), so the write spanned two nodes and had to coordinate them.

Same lookup, two completely different cost profiles - one cheap to write and expensive to read by email, the other the reverse. That's the trade-off in action, on one concrete query.

Keeping distributed indexes consistent

The consistency problem deserves a closer look, because it's where distributed indexing gets genuinely hard. On a single machine, a row and its index entry are updated together in one transaction - they're never out of sync. Across machines, that guarantee is expensive: keeping a global index perfectly in step with the data on every write means a distributed transaction spanning the data node and the index node, which is slow and complex.

So many systems make a pragmatic choice: update the global index asynchronously. The data is written immediately; the index entry is updated a moment later. For a brief window, the index can be slightly stale - a just-written row might not yet appear in the global index, or a just-deleted one might linger an instant. For many use cases this is perfectly acceptable (the index converges quickly), and it's the price of keeping writes fast in a distributed system. But it's a real consideration: if your application can't tolerate any index staleness, you need stronger (and costlier) consistency, and you should know that's what you're paying for. This is the same eventual-consistency trade-off that runs throughout distributed systems, showing up specifically in how indexes track data across nodes.

A third option: design to avoid the problem

The two approaches assume you need a secondary index. But often the best move in a distributed system is to design so you don't - or to push the secondary access elsewhere. Two patterns:

This is often the most robust answer in practice: minimize reliance on distributed secondary indexes by designing the shard key well and offloading the rest. The cheapest distributed index is frequently the one you didn't have to build.

The fundamental trade-off

The two approaches are a clean trade-off, and there's no free lunch:

Local (partitioned) index Global index
Index covers Just one node's data All data
Writes Fast (local to the node) Slow (spans nodes)
Non-shard-key reads Slow (scatter-gather all nodes) Fast (targeted to one index partition)
Consistency Simple (local) Harder (often async)
Best when Writes dominate, reads use shard key Secondary-column reads matter

The choice comes down to your read and write patterns. If writes dominate and most reads use the shard key (with rare secondary lookups), local indexes keep writes fast and accept the occasional scatter-gather. If you frequently need fast reads on a secondary column, global indexes pay the write cost to make those reads efficient. Many distributed databases offer both and let you choose per index.

Tip: Emeka's note from the data trenches: The mistake I see most is people assuming a distributed database's secondary index behaves like a single-machine one - and then being surprised when either writes are slow (global index) or a "simple" lookup hammers every node (local index, scatter-gather). There's no magic here; the index has to live somewhere, and wherever it lives, either writes or reads pay to bridge the gap between where the data is sharded and where the index is organized. My rule: design your shard key so your most important queries use it directly and need no secondary index at all - that's the cheapest path by far. Then, for the secondary access patterns that genuinely matter, choose local or global indexes deliberately based on whether that access is read-heavy or write-heavy. And when a secondary query is both critical and doesn't fit, I often reach for a separate system built for it - a search index or a query-optimized store kept in sync via change data capture - rather than contorting the distributed database itself. Knowing where the index lives, and what that costs, is the whole game.

Interview: Distributed indexing is an advanced topic that signals real depth in a system design interview. If you propose sharding a database and the interviewer asks "how do you query by something other than the shard key?", explaining the local-versus-global index trade-off - local indexes mean scatter-gather reads but cheap writes; global indexes mean fast targeted reads but expensive cross-node writes - is a strong answer. Better still: noting that the best fix is often designing the shard key so important queries don't need a secondary index, and offloading secondary access to a purpose-built store. That shows you understand distributed data at a level beyond the basics.

The bottom line

Indexing in a distributed database hinges on one hard question: where does the index live when the data is spread across many nodes? There are two answers. Local (partitioned) indexes keep each node's index over its own data - making writes fast and local, but turning non-shard-key reads into expensive scatter-gather queries across every node. Global indexes maintain a single index spanning all data, partitioned by the indexed value - making non-shard-key reads fast and targeted, but turning writes into slower cross-node operations that are harder to keep consistent. It's a clean read-versus-write trade-off, chosen per index based on the access pattern.

The deeper lesson: wherever the index lives, something pays to bridge the gap between how the data is sharded and how the index is organized. The cheapest path is a shard key that makes your important queries need no secondary index at all - and offloading the rest to purpose-built stores. We cover distributed data and indexing across System Design Fundamentals.

Go deeper

More articles