An index is not a feature. It's a precomputed answer to a class of question. The structure you choose determines which questions are cheap and which are catastrophic.
There is no universal index. There are only trade-offs.
Hash Table
How it works
Key โ hash function โ bucket โ value. O(1) average lookup. No ordering. Just a direct mapping from input to slot.
When to use
Exact-match lookups. Session stores, caches, deduplication, symbol tables. When you know the key and just need the value. Fast, simple, brutal.
Cannot answer: "give me everything between A and M." No ordering, no range, no neighbours.
B-Tree
How it works
Self-balancing tree. Keys sorted across wide, shallow nodes optimised for disk pages. O(log n) search, insert, delete. Every node holds multiple keys โ minimises disk seeks.
When to use
General-purpose database indexes. Point lookups and range queries. The default choice when you don't yet know your access pattern. Mature, predictable, well understood.
Data lives in both internal and leaf nodes. Good all-rounder, but B+Tree often wins for pure scan workloads.
B+Tree
How it works
Like a B-Tree, but all data lives in the leaves. Internal nodes are pure routing. Leaves are linked together in a doubly-linked list โ you can walk the entire dataset in order without touching the tree.
When to use
Range scans, ordered iteration, pagination. The backbone of most relational databases (InnoDB, Postgres). When you need both point lookups and efficient sequential access.
The linked leaf chain is the key insight โ range queries become sequential I/O instead of tree traversals.
LSM Tree (Log-Structured Merge Tree)
How it works
Writes go to an in-memory buffer (memtable). When full, it flushes to sorted, immutable files on disk (SSTables). Background compaction merges levels. Reads check memtable first, then each level.
When to use
Write-heavy workloads. Time-series data, event logs, metrics. RocksDB, LevelDB, Cassandra, ScyllaDB. When writes must be fast and reads can tolerate some amplification.
Trades read amplification for write throughput. Bloom filters on each level help avoid pointless disk reads.
Inverted Index
How it works
Flips the relationship: instead of document โ words, it maps word โ list of documents containing it. Each term points to a posting list of document IDs, positions, and frequencies.
When to use
Full-text search. "Find every document containing these words." Elasticsearch, Lucene, Solr. Also used in search engines, log analysis, and anywhere you query by content rather than key.
Expensive to build, cheap to query. The cost is paid at write time so reads are near-instant.
Bloom Filter
How it works
A probabilistic bit array. Hash the key k times, set those bits. To check membership, hash again โ if all bits are set, "probably yes". If any bit is unset, "definitely no". No false negatives. Controllable false positive rate.
When to use
Avoiding expensive lookups. "Is this key definitely not here?" Used in LSM trees, CDNs, network routers, spell checkers. Tiny memory footprint for massive keyspaces.
Not an index in the retrieval sense โ it's a filter. It tells you when not to bother looking.
Skip List
How it works
A sorted linked list with express lanes. Multiple layers of forward pointers let you skip ahead, giving O(log n) search on a structure that's simpler than a balanced tree. Probabilistic balancing โ no rotations needed.
When to use
In-memory sorted structures where concurrency matters. Redis sorted sets. Memtable internals in LSM trees. When you want ordered access without the complexity of tree rebalancing.
Elegant because it replaces structural complexity with randomness. Lock-free variants make it ideal for concurrent access.
R-Tree (Spatial Index)
How it works
Organises multi-dimensional data into nested bounding rectangles. Each node contains a minimum bounding box that encloses its children. Queries test overlap with the target region and prune entire subtrees.
When to use
Geospatial queries. "Find all restaurants within 2km." PostGIS, mapping systems, collision detection. Any domain where data lives in 2D/3D space and you query by proximity or containment.
Extends the B-Tree idea to multiple dimensions. Degrades with high-dimensional data โ that's where vector indexes take over.
Bitmap Index
How it works
One bit per row, per distinct value. "Status = active" becomes a bit vector across all rows. Queries combine bitmaps with AND/OR/NOT โ hardware-level bitwise operations on entire columns at once.
When to use
Low-cardinality columns in analytics. Gender, status, region, boolean flags. OLAP warehouses, column stores. When the number of distinct values is small relative to row count.
Compresses beautifully with run-length encoding. Falls apart on high-cardinality columns โ don't bitmap a UUID.
Trie (Prefix Tree)
How it works
Each node represents a character. Paths from root to leaf spell out keys. Shared prefixes share nodes. Lookup time is O(key length), independent of dataset size.
When to use
Autocomplete, IP routing tables, dictionary lookups, prefix matching. When queries are "everything starting with X". Variants like radix trees (PATRICIA) compress sparse paths.
Memory-hungry in the naive form. Radix compression and adaptive node sizing (ART) make it practical at scale.
Vector Index (ANN)
How it works
Maps high-dimensional vectors into a structure that supports approximate nearest-neighbour search. Approaches include HNSW (hierarchical navigable small-world graphs), IVF (inverted file with clustering), and quantisation (PQ/SQ) to compress vectors. Trade exactness for speed.
When to use
Semantic search, RAG, image similarity, recommendation engines. "Find the 10 things most like this." The query isn't a key โ it's a point in meaning-space. This is what we built into PicoWAL.
The only index type where the question is fuzzy. Not "find this" but "find things near this." The shape of AI-era retrieval.
The Pattern
Every index encodes an assumption:
Hash Table โ "I know the exact key"
B-Tree โ "I need point + range on disk"
B+Tree โ "I need to scan in order"
LSM Tree โ "I write far more than I read"
Inverted Index โ "I'm searching by content"
Bloom Filter โ "I need to avoid wasted reads"
Skip List โ "I want sorted + concurrent + simple"
R-Tree โ "My data lives in space"
Bitmap โ "I'm filtering low-cardinality columns"
Trie โ "I'm matching prefixes"
Vector Index โ "I'm searching by meaning"
The wrong index doesn't just slow things down. It changes what questions your system can answer.
HOW DATA IS ACTUALLY STORED
Forget "primary keys" and "foreign keys" as relational theory. Think about what's physically happening on disk.
Heap: The Junk Drawer
A heap is unsorted storage. Rows go wherever there's space. Insert is fast โ just append. But finding anything means scanning the entire thing, because there's no physical order.
No structure. No sort. No promise about where anything lives.
Every query without an index = full table scan.
A heap with no indexes is a flat file. You're paying disk I/O to read every row every time. The only thing making heaps usable is the indexes you put on top.
Clustered Index: The Data Is the Index
A clustered index doesn't sit alongside the data. It is the data. The rows are physically sorted on disk in the order of the clustered key. The leaf nodes of the B+Tree contain the actual rows.
Heap + Index
Index says: "row 47 is at page 312, slot 5"
Then you go to page 312 and read it.
Two lookups. Index โ pointer โ data.
Clustered Index
Index says: "row 47 is right here"
The leaf node is the data page.
One lookup. Index = data.
You can only have one clustered index per table, because data can only be physically sorted one way. Choose it carefully โ it determines the physical layout of everything.
SQL Server default behaviour: When you add a primary key with a unique constraint, SQL Server automatically creates a clustered index on that column. If you don't add a primary key, the table is stored as a heap. Most people don't realise they're making a physical storage decision when they type PRIMARY KEY โ but they are. No primary key = no clustered index = heap = full scan on every query without a non-clustered index.
Non-Clustered Index: A Separate Lookup Structure
A non-clustered index is a separate B+Tree that stores a copy of the indexed columns plus a pointer back to the actual row. If the table has a clustered index, the pointer is the clustered key. If it's a heap, the pointer is a physical row ID (page + slot).
Non-clustered on a clustered table: stores the clustered key as the bookmark โ then uses the clustered index to find the row. Two B+Tree traversals.
Non-clustered on a heap: stores the physical RID (file:page:slot) โ goes straight there. One traversal + one seek.
You can have many non-clustered indexes on one table. Each is an extra structure to maintain on writes, but a fast path for reads that match its key pattern.
Primary Key vs Secondary Key: What It Actually Means
Strip away the relational theory. A key is just a column (or columns) you use to find rows.
Primary Key
The identity of the row. Unique, not null.
In most engines, the primary key becomes the clustered index by default. The data is physically sorted by this key.
It's not special because of theory. It's special because it determines how the bytes are laid out on disk.
Secondary Key
Any other column you index. Always a non-clustered index.
Contains a copy of the indexed columns + a pointer back to the primary key (or RID on a heap).
It's a separate data structure optimised for a different access pattern. More secondary indexes = faster reads on those columns, slower writes everywhere.
The Covering Index Trick
If a non-clustered index contains all the columns your query needs, the engine never touches the base table. It answers the query entirely from the index. This is a covering index โ the query is "covered" by the index alone.
This is why you sometimes see indexes with INCLUDE columns โ they're not part of the sort key, but they're carried along so the index can cover more queries without going back to the table.
The Physical Reality
Heap โ unsorted pages. append-only. scan everything to find anything.
Clustered index โ the data is the B+Tree. one per table. defines physical order.
Non-clustered index โ separate B+Tree. points back to clustered key or RID.
Primary key โ usually the clustered key. the identity that everything else points at.
Secondary key โ non-clustered index on other columns. a separate access path.
Covering index โ carries enough columns to answer the query without touching the table.
The primary key isn't important because of relational theory. It's important because it determines the physical shape of your data on disk. Everything else โ every secondary index, every join, every foreign key โ is just a pointer back to that shape.
Choose the index before you choose the database. The index is the database.
An index is a precomputed constraint on the wavefunction of possible queries. It collapses lookup from "search everything" to "go here."