Database index types
The data structures that turn a full-table scan into a pinpoint lookup.
An index is a separate data structure that trades extra storage and slower writes for dramatically faster reads. B-tree/B+tree is the balanced default that serves both ranges and equality; hash indexes give O(1) equality but no ranges; bitmap indexes suit low-cardinality columns. A clustered index dictates the physical row order (one per table) while non-clustered indexes point back to rows.
Why index at all
Without an index the engine has no choice but a full-table scan, reading every row from disk to find the ones you asked for — cost that grows linearly with table size. An index is a sorted side-structure that lets the engine jump straight to the matching keys instead, turning that linear scan into a logarithmic descent. You pay for it in extra storage and slightly slower writes, because every insert, update and delete must also maintain the index.
Start at the root
A B+tree lookup begins at the single root node held at the top of the tree. The root holds separator keys that partition the whole key space into ranges, each pointing down toward the child that contains values in that range. One comparison here already discards the vast majority of the table.
Descend the internal nodes
At each internal level the engine compares your search key against the separators and follows the one child pointer whose range contains it. Because the tree is balanced and each node fans out to hundreds of children, the height stays shallow — typically three or four levels even for millions of rows. That shallow height is exactly why a lookup is O(log n) rather than O(n).
Reach the leaf
The descent ends at a leaf node, which holds the actual keys in fully sorted order. Crucially, leaf nodes are chained together in a doubly linked list, so once you land on one you can walk sideways to read a whole range without going back up the tree. This is why B+trees serve range scans and ORDER BY just as well as single-key equality.
Follow the pointer to the row
The leaf yields either a row pointer to the heap or, for a clustered index, the full row stored inline. Other index types trade off differently at this final step: a hash index gives O(1) equality but can't do ranges or ordering, while a bitmap index packs low-cardinality columns into bit vectors that AND/OR together cheaply. Choosing the right structure is choosing which access pattern you want to make fast.
The problem: full-table scans don't scale
Imagine a users table with fifty million rows and a query WHERE email = 'a@b.com'. With no index the database has only one strategy: read every single row and check the email column — a full-table scan. The cost of that scan grows linearly with the table, so a query that was instant on ten thousand rows becomes a multi-second disk grind on fifty million. Worse, that cost is paid on every such query, by every user, forever.
An index exists to break that linear relationship. It is a separate, sorted data structure kept alongside the table that lets the engine locate matching rows without examining the ones that don't match. The bargain is explicit and worth stating up front: you spend extra storage and slightly slower writes in exchange for dramatically faster reads. Because most systems read far more than they write, that trade is usually a bargain — but not always, which is why knowing when *not* to index matters as much as knowing how to.
The key intuition is that an index is a physical performance choice, not a logical part of your data. Dropping an index never changes the answer to a query, only how long it takes to compute. That is why you can add and remove indexes freely as your query patterns evolve.
How a B+tree lookup works, end to end
The default index in essentially every relational database is the B+tree (a balanced tree variant of the B-tree). It is worth understanding concretely because it explains most of an index's behaviour.
A B+tree is a shallow, wide tree. The root node sits at the top and holds a handful of separator keys that carve the whole key space into ranges. Below it, internal nodes each hold more separators, and at the bottom sit the leaf nodes, which hold the actual indexed keys in fully sorted order. A lookup walks down from the root: at each level it compares the search key against the separators and follows the single child pointer whose range contains it.
Two properties make this fast:
- Balance. Every leaf is the same distance from the root, so no key is slower to find than any other. The engine never degenerates into a linear walk.
- High fan-out. Each node holds hundreds of keys, so the tree stays only three or four levels deep even for hundreds of millions of rows. Each level read discards the overwhelming majority of remaining candidates.
That is the source of the famous O(log n) lookup cost: the number of node reads grows with the *logarithm* of the row count, not the count itself. Doubling the table adds essentially nothing to lookup time.
The final touch is that leaf nodes are linked into a sorted doubly linked list. Once a lookup lands on a leaf, it can walk sideways to read an entire range — WHERE age BETWEEN 20 AND 30, or an ORDER BY — without ever climbing back up. This is precisely why B+trees serve ranges and sorting, which is what makes them the versatile default.
Clustered vs secondary, covering vs composite
Not all indexes point at rows the same way, and the distinction has real performance consequences.
A clustered index determines the *physical order of the rows themselves* on disk — the leaf level of the tree literally is the table data, stored in key order. Because rows can only be laid out one way, a table has at most one clustered index (in many databases it's the primary key by default). Looking up by the clustered key is maximally fast because you find the row inline, with no second hop.
A secondary (non-clustered) index is a separate tree whose leaves hold the indexed key plus a pointer back to the row. Using it means two steps: find the pointer in the index, then follow it to fetch the actual row — sometimes called a *bookmark lookup*. That extra hop is cheap for a few rows but expensive for many, which is one reason the optimizer sometimes ignores an index and scans instead.
Two refinements matter in practice:
- A composite index covers several columns in a defined order, e.g.
(last_name, first_name). It can serve queries filtering on a left-prefix of those columns (last_name, orlast_name+first_name) but not onfirst_namealone — column order is not arbitrary. - A covering index includes every column a query needs, so the query is answered *entirely from the index* without ever touching the row. Eliminating the bookmark lookup can make a query several times faster.
Beyond B+trees, other structures optimise other shapes: hash indexes give O(1) equality but cannot do ranges or ordering because hashing destroys key order, and bitmap indexes encode low-cardinality columns (like a status flag) as bit vectors that combine with fast bitwise AND/OR.
The cost side: writes, storage, and when not to index
Every index is a liability as well as an asset, and mature engineering means respecting both sides.
The clearest cost is write amplification. Each index is a separate structure that must stay consistent with the table, so every INSERT inserts into all of them, every DELETE removes from all of them, and an UPDATE to an indexed column rewrites the corresponding index entries. A table with eight indexes turns one logical write into nine physical ones. On write-heavy workloads this can dominate.
The second cost is storage: indexes are real data on disk and in the buffer pool, and a wide covering index on a large table can rival the size of the table itself. Space in memory is especially precious, because index pages compete with data pages for the cache.
There is also a subtler failure mode: an index the optimizer never uses is pure overhead — all cost, no benefit. This happens with low-selectivity columns. An index on a boolean is_active where 90% of rows are active barely narrows anything, so the optimizer correctly prefers a scan, and the index just slows writes.
So the guidance is to index deliberately:
- Index columns used in
WHERE,JOIN, andORDER BYon read-hot, high-selectivity queries. - Avoid indexing tiny tables (a scan is already cheap), very-low-cardinality columns, and columns that are written constantly but rarely queried.
- Watch for redundant indexes — a composite
(a, b)already covers queries ona, making a standalone index onawasteful.
Using indexes well in the real world
In day-to-day work, indexing is an iterative, evidence-driven loop rather than a one-time design decision.
Start from the queries, not the schema. Look at your slow query log and your most frequent statements, then read their execution plans (EXPLAIN in PostgreSQL and MySQL). The plan tells you whether the engine chose an index seek or a full scan, and how many rows it estimated versus actually touched. A plan showing a sequential scan on a large table filtered by an unindexed column is the textbook signal to add an index.
A few practical patterns recur constantly:
- Composite order follows filter shape. For
WHERE tenant_id = ? AND created_at > ?, an index on(tenant_id, created_at)lets the engine seek to the tenant and then range-scan by time. Put the equality column first, the range column second. - Covering the query — adding the selected columns into the index — removes bookmark lookups on your hottest reads.
- Foreign keys deserve indexes. A join or an
ON DELETE CASCADEon an unindexed foreign key forces a scan of the child table.
Finally, indexes interact with the rest of the database story. The query optimizer decides whether to actually use an index based on statistics, so keeping statistics fresh matters. And because indexes speed reads at the cost of writes, they sit on the same spectrum as caching and denormalization — all three trade extra maintained state for faster reads. Thinking of indexing as one tool in that broader read-optimisation toolkit is what separates reflexive index-everything habits from deliberate performance engineering.
An index speeds lookups at the cost of extra storage and slower writes (every insert/update maintains it).
B-tree / B+tree is the default: a balanced tree that's excellent for both range scans and equality.
Hash indexes give O(1) equality lookups but can't do ranges or ordering.
Bitmap indexes shine on low-cardinality columns (few distinct values, like a status flag).
A clustered index defines the physical order of rows — one per table; non-clustered/secondary indexes hold a copy of the key plus a pointer to the row.
Composite indexes cover multiple columns; a covering index answers a query entirely from the index without touching the row.
Quick quiz
Why can't a hash index serve a range query like age > 30?
How many clustered indexes can a table have?
How a SQL query executes
The pipeline that turns a text string into rows fetched off disk.
The 5 normal forms
A ladder of rules that squeezes redundancy out of a schema, one dependency at a time.
Where do we cache — and how it goes wrong
Caching lives at every layer. So do the ways it can bite you.