When Ordinary Indexes Fail

For six lessons in Database Internals, the B-tree was the hero. It turned a million-row lookup into three disk reads. It made ranges, sorts, and prefix matches feel free. It was so good that it's easy to walk away believing an index is just the way you make a query fast. So it's worth saying plainly what a B-tree actually does, because the whole of this section lives in the gap between what it does and what we keep asking it to do.

A B-tree does exactly one thing: it keeps your rows in one sorted order, and hands you any contiguous slice of that order. That's it. Everything it's famous for is that single trick wearing different clothes:

• Equality (WHERE id = 42) is a slice of width one.
• A range (WHERE price BETWEEN 10 AND 20) is a slice.
• A prefix (WHERE name LIKE 'Sri%') is a slice — the names starting with Sri sit together.
• ORDER BY, MIN, MAX, pagination — those are just where you start reading and which end. The order is already there; you walk it.

Pull on that thread and the power and the limit are the same fact. A B-tree is fast because the data is sorted, and it can only answer questions that are a contiguous run of that one sorted order. Give it a question that isn't a contiguous slice of a single order — and it has nothing. Not a slower answer: no structural advantage at all. It falls back to reading everything and checking each row, which is the one thing indexes were supposed to save us from.

That sounds like a narrow failure. It is not. An enormous number of the questions real systems ask are not a slice of one order — and every one of them is a lesson in this section. Here's the whole idea on one ruler: the questions that are a slice, and the ones that fall off it.

Here are five questions systems ask constantly. Each one looks like it should be indexable. None of them is a contiguous slice of a single sort order — and seeing why is the point of this whole section.

1 · "What's near me?" (two dimensions at once). You have restaurants at (latitude, longitude) and you want the ones inside a small box on the map. Put a B-tree on latitude and you can fetch every restaurant in a band of latitudes — at any longitude on Earth. Put it on longitude and you get a band of longitudes at any latitude. As Designing Data-Intensive Applications puts it, if you want records in both a latitude range and a longitude range, "a B-tree cannot answer that efficiently" — you can have one range or the other, but not both at once. What about a composite (lat, lng) index? That's the leftmost-prefix rule from Indexes Deep-Dive, and it bites here: once you range on latitude, the longitude ordering within the index is scrambled across the whole stripe. So the box query degenerates into "scan a full latitude stripe, then throw away everything outside the longitude range" — most of the work wasted. A B-tree indexes one axis; the map has two, and they're equals.

2 · "Is this key definitely not here?" (membership, answered without the lookup). A B-tree can tell you where a key is — but it charges you the full descent even when the answer is no. For a workload that's mostly misses — has this URL been crawled before? is this username taken? does this SSTable contain this key? — you pay a log n walk (often a random disk seek or a network hop) just to learn "nope." You already saw the fix in LSM Trees & SSTables: every SSTable carries a Bloom filter that answers "definitely not here" from memory so the read can skip the file entirely. That little structure is a whole lesson of its own — because "probably yes / definitely no, from RAM" is not something a sorted order can do.

3 · "How many? How many distinct?" (counting a firehose). COUNT(DISTINCT user_id) over a day of events sounds trivial. Done exactly, it means remembering every id you've ever seen — a set that grows with the data. A hundred million distinct visitors is gigabytes of ids held in RAM just to answer one number, and it doesn't fit in the little slice of memory you'd like to answer from. A sorted index doesn't help: distinctness isn't a slice. But if you'll accept an answer within a couple of percent, there's a structure that counts past a billion distinct items in about 1.5 kilobytes — flat, forever. Gigabytes-exact versus kilobytes-approximate is a trade a B-tree can't even express.

4 · "What's similar to this?" (not what's equal). Near-duplicate news articles, "customers like you," fingerprinting images that were resized and re-saved. A B-tree indexes exact keys: two items that are 95% the same share no key and never sort next to each other. And the brute-force answer explodes — comparing every pair in a set of just 50,000 documents is about 1.25 billion comparisons, and it grows with the square of the collection. Similarity isn't equality, and it isn't a total order — there's no single line you can sort things on where alike means adjacent.

5 · "Which documents contain these words — best first?" (full text). Put a B-tree on a body column and it indexes the entire string as one key. Great for = 'exact document'; useless for "documents mentioning storage and tiering." You met this in Container 1: LIKE 'storage%' can use the index (a prefix is a slice), but the query you actually want — LIKE '%storage%', the word somewhere inside — has no prefix to seek from, so the index is forbidden and Postgres falls back to a full sequential scan. Search needs the index turned inside out — from doc → its text to word → the docs that contain it — and then a way to rank the matches. That's a different structure and a different math.

Five questions, one diagnosis. None is a contiguous slice of a single sorted order — so the tool that only sells contiguous slices has nothing to offer. Line them up:

The spatial case is the one to feel, because you can see it. A B-tree keeps points in one sorted order; a map query wants a two-dimensional box. Those two things can't be reconciled, and here you can watch them fail to.

Drop some points, draw a box, and switch which index the database is using. Whatever it sorted by, all it can hand you is a contiguous slice of that order — a horizontal stripe if it sorted by X, a vertical one if it sorted by Y, an L-shaped run if it used a composite key. Overlay that on the box you actually asked for and the mismatch is right there: the database scans a stripe of hundreds of rows to return the handful inside your box. Watch the scanned vs matched counter — that gap is the wasted work, and it's the reason spatial indexes exist. Then flip on the space-filling curve and watch the same box become almost one contiguous run — the first escape route, which the next five lessons build out.

This isn't a toy effect. Run it on a real Postgres table of one million random points and ask for a small map box that contains 147 of them. The naive "just add a second index" fix — a B-tree on latitude and another on longitude — produces a plan that says it out loud: it scans 19,230 entries from the latitude index and 8,498 from the longitude index, then intersects those two stripes down to the 147 you wanted. That's 27,728 index entries read to return 147 — and it's the slowest of the indexed plans. A single composite (lat, lng) index does better but still examines the whole 19,230-row latitude band. A real spatial index (Postgres's GiST) touches 8 index pages and lands on the 147 directly, in 0.079 ms — about 9× faster than the best B-tree plan and 350× faster than scanning the table. The stripe you see the widget scan is the same stripe Postgres scans.

Once you accept that a single sorted order can't answer these questions, there are exactly two things you can do about it — and every structure in this section is one of them.

Route A — change the geometry (stay exact, pay in space and structure). The answer is still precise; you just stop insisting on one order. You impose a different arrangement on the data so that the hard question becomes a contiguous slice again. Flatten 2-D space onto a single curve that keeps nearby points nearby (geohash, S2, H3) — that's the space-filling-curve trick, and it's exactly how you fold two dimensions back onto the one order a B-tree understands. Or split space into a tree of boxes so a region query prunes whole branches (quadtrees, R-trees). Or, for text, invert the index — word → documents — so "find these words" becomes a slice lookup after all (the inverted index, then BM25 to rank). These cost extra space and extra structure, but they never lie to you — in the million-row test above, the GiST spatial index was 63 MB against the composite B-tree's 30 MB: roughly twice the space for its ~9× speed. That's the whole bargain of Route A in two numbers — pay in space, keep the answer exact. (This isn't a new idea: the 1984 paper that introduced the R-tree opens by noting that "traditional indexing methods are not well suited to data objects … located in multi-dimensional spaces" — the field has known the B-tree's blind spot for forty years.)

Route B — trade exactness for space (accept a bounded error, live in memory). Some questions don't need a perfect answer, and paying for one is the mistake. If you'll accept probably or approximately, you can answer from a structure hundreds or thousands of times smaller — small enough to sit in cache and run at memory speed. "Is it in the set?" → a Bloom or Cuckoo filter (definitely-no / probably-yes). "How many distinct?" → HyperLogLog (billions of items, a couple percent error, ~1.5 KB). "How often does each thing occur?" → a Count-Min sketch. "How similar are these two sets?" → MinHash. These are the sketches, and their whole art is being wrong by a little on purpose.

That's the map of the section. Every lesson from here is either a new geometry that keeps the answer exact, or a new sketch that shrinks the structure by giving up a little accuracy. Keep the two routes in mind and each one will slot cleanly into place.

A section full of exotic structures can leave you reaching for them too early, so here's the honest boundary — the mirror image of everything above.

Most applications never leave B-tree territory, and shouldn't. If your queries are slices of a sorted order — and the overwhelming majority are — a plain index or a well-chosen composite key is faster, simpler, and already built into your database. Specialized structures earn their complexity only when the question itself isn't a slice, or when the exact answer literally won't fit in the memory you have. Reaching for a Bloom filter to check membership in a ten-thousand-row table is not clever; it's a second thing to get wrong in front of a hash set that was already instant.

And the obvious workaround doesn't rescue the B-tree. The tempting fix for the map query is "put a B-tree on latitude and a separate one on longitude, and combine." Real databases will even try: Postgres can scan both indexes and BitmapAnd the results. But it disappoints for a concrete reason — each index first hands back a huge stripe (every point in the latitude band, every point in the longitude band), and only then intersects them down to the sliver you wanted. You paid to read two enormous lists that were each almost entirely wrong, just to AND them together. Two one-dimensional indexes are still one-dimensional twice; they never become a two-dimensional index. And the reason is deep, not incidental: there is no way to lay 2-D points out on a single line so that everything close on the map is close in the ordering — some near neighbors always land far apart. Space-filling curves (the next lessons) get close to that impossible ideal, which is exactly why they need care at the seams. That gap — not raw speed — is what the specialized structures close.

So the rule for the rest of the section is diagnostic, not eager: name the shape of your question first. Is it a contiguous slice of one order? Use the B-tree you already have. Is it a region, a membership test, a count, a similarity, a search? Then — and only then — reach for the structure built for that shape.

• ⭐ A B-tree answers exactly one kind of question: a contiguous slice of one sorted order. Equality, range, prefix, ORDER BY, MIN/MAX — all the same trick. Its power and its limit are the same fact.
• ⭐ Five common questions aren't that shape: what's near me (2-D), is it definitely absent (membership), how many distinct (cardinality), what's similar (not equal), which docs contain these words (full text). No single order makes any of them a slice — so a B-tree has no structural edge.
• ⭐⭐ There are only two escapes, and every structure in this section is one of them. Change the geometry — a new order or partition that keeps the answer exact (spatial curves and trees; the inverted index). Or trade exactness for space — a sketch that's a little wrong on purpose so it fits in memory (Bloom, Cuckoo, HyperLogLog, Count-Min, MinHash).
• Don't specialize early. If the question is a slice, the B-tree you already have wins. And two 1-D indexes never add up to one 2-D index — their intersection is a lot of work for a sliver of answer.
• The section's real skill is diagnosis: name the shape of the question before you pick the structure. §2 asked which amplification you could afford; §8 asks whether a sorted order is even the right shape for the question at all.

We'll start with the escape you can literally see. Next up — Geospatial Search: The Problem — takes the "what's near me?" query apart properly: why it's genuinely hard, what "near" even means on a sphere, and what a good spatial index has to deliver before we build the first one.