Indexes Beyond the B-tree: Full-Text, Geospatial, Vector

The B-tree is the default database index, and it's the right tool for equality and range queries. But three questions modern systems ask constantly don't fit that shape: which documents contain this word?, which points are near this place?, and which vectors are similar to this one? Each needs a different index — and reaching for a B-tree (or a full scan) instead is a classic scaling mistake. Here's a runnable tour of all three, measured against brute force.

Runnable companion: beyond-the-btree-indexes on GitHub. make inverted && make spatial && make vector reproduces every number below.

Inverted index — full-text

"Which of 100,000 documents contain term X?"

method                      latency (median)
brute-force scan                   5.5569 ms
inverted index                     0.0002 ms      (~26,000x faster)

A B-tree can't answer "contains a word". An inverted index flips the mapping — from documents→words to words→documents (posting lists) — so the query is a dictionary lookup, and boolean queries (A AND B) become set intersections. This is the core of Lucene, Elasticsearch, and Postgres full-text. Cost: storage, and it's updated on every write.

Spatial index — geospatial

"Which of 200,000 points fall inside this map box?"

method                  latency (median)   candidates examined
brute-force scan               14.344 ms               200,000
grid / spatial index            0.318 ms                   822      (~45x faster)

A B-tree orders one dimension, so a 2-D box query scans everything. A spatial index partitions space so the query examines only nearby candidates — 822 instead of 200,000. Production systems use R-trees (PostGIS, SQLite R*Tree); the grid here shows the same idea: prune by space.

Vector index — semantic search / RAG

Nearest-10 vectors to a query, over 50,000 embeddings (dim 128):

method                 latency/query   recall@10
exact (brute)                3.91 ms      100.0%
HNSW ef=10                  0.007 ms       37.8%
HNSW ef=50                  0.014 ms       60.8%
HNSW ef=200                 0.039 ms       87.3%
HNSW ef=500                 0.084 ms       98.1%

This is the one to internalize, because it powers every RAG system. Similarity isn't an ordering, so a B-tree is useless. Exact search compares the query to every vector — 100% correct but O(N). HNSW (an approximate index) is ~46x faster even at 98% recall. But note two things:

1. It's approximate — recall is below 100%; it can miss a true neighbour. Great for search, a real bug if you assumed exactness.
2. Recall is a tunable dial — the ef knob trades accuracy for latency. The lab shows recall climbing 37.8% → 98.1% as ef rises, latency growing in step. RAG systems pick a point on that curve (often ~95–99%) for speed.

This is pgvector, Pinecone, Qdrant, Weaviate, Milvus — the retrieval layer of modern AI. An architect must know it's approximate and that recall must be measured on your own data (clustered real embeddings behave nothing like uniform random vectors).

What I'd say in an interview

• Match the index to the shape of the question: equality/range → B-tree; contains → inverted; near → spatial/R-tree; similar → vector/ANN.
• Vector indexes are approximate, and recall is a dial against latency — know and measure your operating point.
• Every index is read speed bought with write cost and storage — add the ones your hot queries need, no more.
• Bonus: Postgres alone can do all four (B-tree, PostGIS, tsvector, pgvector) — often one database covers the lot.