Database indexes

A database index is a separate, sorted structure that maps the values of one or more columns to the rows that hold them, so the database can jump straight to matching rows instead of reading the whole table. Most indexes are B+trees, where finding one row among hundreds of millions takes three or four page reads instead of millions. You pay for that speed on every write, because each insert, update and delete must keep every index in step.

Picture it first: the index at the back of a textbook

You have a 900-page operating systems textbook and need the page that explains “thrashing”. You could read from page 1 until you find it. Or you turn to the index at the back, where terms are sorted alphabetically: T, then “th…”, then “thrashing, 412”. You read a few lines of the index and one page of the book.

Three properties make the book’s index work, and each one maps onto a database:

• It is sorted. Because terms are in alphabetical order, you jump to the right area instead of reading every entry. A database index keeps its keys sorted for the same reason.
• It is separate and small. The index is a few pages; the book is hundreds. A database index stores only the indexed column plus a pointer, not the whole row.
• Each entry points somewhere. “thrashing, 412” is a key plus a location. A database index entry is a key plus a row pointer: a physical address in PostgreSQL, a primary-key value in MySQL’s InnoDB.

The analogy also shows the cost. A book with five separate indexes (terms, authors, figures, equations, code listings) needs five updates every time a section is added. That is exactly the write cost of database indexes.

Why a full scan is slow

A table is stored as fixed-size pages: 8 KB in PostgreSQL, 16 KB by default in InnoDB. Pages are the unit the database reads from disk and caches in memory, so “how many pages does this query touch?” is the cost question that matters.

Without an index, WHERE id = 42 has only one strategy: read every page and test every row. That is a sequential scan (a full table scan), and its cost grows linearly with the table: O(n).

Take a UPI-style payments table with 500 million rows of about 160 bytes each, including per-row overhead:

• Rows per page: 8,192 ÷ 160 ≈ 51, call it 50.
• Pages: 500M ÷ 50 = 10 million pages, about 80 GB.
• Even at an optimistic 2 GB/s of sequential reads, one lookup takes about 40 seconds.

An index turns the same lookup into a walk down a tree. Each step reads one page and picks one child out of hundreds, so the number of pages read grows with the logarithm of the table size: O(log n). For this table it is four index pages and one table page.

The ratio is about two million to one (10,000,000 ÷ 5). So the first question in any slow-query investigation is “is there an index for this predicate, and is it used?” The query execution plan answers the second half.

Inside a B+tree

Almost every relational database’s default index is a B+tree, a variant of the B-tree that Rudolf Bayer and Edward McCreight published in 1972. Douglas Comer’s 1979 survey was already calling B-trees the de facto standard for organizing files, and nothing has displaced them for general-purpose indexing since.

A B+tree has three kinds of page:

• Leaf pages hold the actual index entries, sorted by key. Each entry is a key plus a pointer to its row. In a PostgreSQL B-tree, typically over 99% of pages are leaves.
• Internal pages hold only separator keys and pointers to child pages: “keys below 150 are in this child, 150 and above in that one”.
• The root is the one internal page at the top, where every search starts.

Two properties make it far more than a sorted list:

1. It stays balanced. Every leaf sits at the same depth, so every lookup costs the same number of page reads. When a leaf fills up, it splits into two pages and pushes a new separator into its parent; if the parent is full, it splits too, and when the root splits, a new root appears one level higher. The tree grows at the top, never lopsided.
2. Its leaves are linked. Each leaf points to its neighbours (PostgreSQL links every level in both directions). Once a search has found the first key of a range, it walks sideways along the leaves without climbing back up. Comer calls this chain of leaves the sequence set.

That is the “+”. In the original B-tree, keys and data live at every level, so a range scan bounces up and down the tree; in a B+tree, internal pages are small, dense signposts and every key sits in the linked leaf level.

How tall does the tree get?

The height of a B+tree, and so the cost of a lookup, depends on its fan-out: how many children each internal page points to. Work it out for a PostgreSQL index on a bigint column:

• An index entry is an 8-byte header (which holds the row pointer) plus the 8-byte key, 16 bytes in all. Each entry also takes a 4-byte slot in the page’s array of item pointers. Total: about 20 bytes.
• An 8 KB page has 8,192 bytes, minus a 24-byte page header and a few bytes of index bookkeeping: roughly 8,150 usable bytes, so about 400 entries per page.
• Each level multiplies capacity by about 400. With h levels, the tree indexes up to 400^h rows: 160,000 with two levels, 64 million with three, 25.6 billion with four.

For the 500-million-row payments table:

• Leaves: 500M ÷ 400 = 1.25 million pages (10 GB).
• The level above: 1.25M ÷ 400 ≈ 3,125 pages. Above that: 3,125 ÷ 400 ≈ 8 pages. Then a single root.
• So the tree has four levels, and the three upper levels add up to about 3,134 pages, roughly 25 MB.

That last number is the quiet reason indexes are so fast in practice. 25 MB of upper levels stays hot in the buffer cache, so a lookup that misses the cache usually costs just two real reads: the leaf and the table page.

Real pages are rarely 100% full. InnoDB’s documentation says sequential inserts leave pages about 15/16 full and random inserts anywhere from half to 15/16. At half full the fan-out drops to about 200, and 200^4 = 1.6 billion, so hundreds of millions of rows still fit in four levels. InnoDB’s 16 KB pages roughly double the entries per page, which can save a level at the margin. The conclusion is robust: three or four levels for almost any table you will meet.

Point lookups, range scans and ORDER BY

One sorted structure serves several kinds of query. PostgreSQL will consider a B-tree whenever an indexed column is compared with =, <, <=, > or >=, plus anything built from those (BETWEEN, IN), IS NULL, and patterns anchored at the start such as LIKE 'Ban%'.

• Point lookup (WHERE id = 42): one descent, root to leaf, then fetch the row. Cost: tree height + 1 page.
• Range scan (WHERE created_at >= '2026-10-01' AND created_at < '2026-10-02'): one descent to the first matching key, then walk right along the leaves until the first key past the end. Cost: height + the matching leaf pages + one table page per matching row (fewer if those rows sit together on disk).
• ORDER BY with LIMIT (ORDER BY created_at DESC LIMIT 20): the leaves are already sorted, so the database starts at one end, reads 20 entries and stops. There is no sort step, and the work doesn’t grow with the table. Leaf levels are linked both ways, so descending order is as cheap as ascending. This is what makes keyset pagination fast.
• Prefix match (LIKE 'Ban%'): really a range scan from 'Ban' up to 'Bao'. In PostgreSQL with a non-C locale, the index needs a special operator class for this. A leading wildcard (LIKE '%galore') has no starting point in a sorted list, so a B-tree can’t help at all.

The range-scan cost hides a trap: “one table page per matching row”. If a range matches two million rows scattered across the table, an index scan performs up to two million random page reads, and reading the whole table sequentially may be cheaper. The planner weighs exactly this; index scan vs full table scan explains how.

Hash indexes: equality only

A hash index stores a hash of each key and uses it to jump straight to a bucket page, skipping the root-to-leaf descent. In PostgreSQL the stored value is a 32-bit hash code, which has three consequences:

• It answers = and nothing else. No ranges, no ORDER BY, no prefix LIKE: hashing destroys order.
• It can be much smaller than a B-tree on long values. Each entry stores a 4-byte code instead of, say, a 100-byte URL.
• It can’t enforce uniqueness. In PostgreSQL only B-tree indexes can be declared unique.

One piece of history explains a lot of old advice. Before PostgreSQL 10, hash index changes were not written to the write-ahead log, so they were not crash-safe and did not reach replicas, and PostgreSQL printed a warning when you created one. Version 10 added write-ahead logging, so “never use hash indexes” is advice from that earlier era.

A B-tree on the same column is only a page read or two slower and also handles ranges and sorting, so it stays the default. Reach for a hash index when the column is long, only ever compared with =, and index size matters, such as looking up a long URL in a URL shortener.

Clustered vs heap tables

Where does the row itself live? The two most popular open-source engines answer differently, and that changes what every lookup costs.

InnoDB: the table is the primary-key index

In MySQL’s InnoDB, every table is a B+tree ordered by primary key, and the leaf pages hold the full rows. This is the clustered index. If you don’t declare a primary key, InnoDB uses the first UNIQUE index whose columns are all NOT NULL; failing that, it clusters on a hidden 6-byte row ID that increases with every insert.

Every other index is a secondary index, and each of its entries stores the indexed columns plus the row’s primary-key value, not a physical address. A lookup by a secondary key is therefore two tree walks: descend the secondary index to find the primary key, then descend the clustered index to find the row. Oracle offers the same design as an index-organized table.

PostgreSQL: a heap plus indexes that point into it

In PostgreSQL, a table is a heap: rows go into whichever page has room, in no particular key order. Every index, the primary key’s included, is a separate B+tree whose entries point at a row version’s physical location, its ctid (a page number and a slot on that page). A lookup by any index is one tree walk plus one heap page.

Neither design wins outright. Clustering gains cheap primary-key lookups and range scans, because the row is already in the leaf. You pay with a second walk on every secondary lookup and a primary key that becomes load-bearing: a long key bloats every secondary index, and a random key scatters inserts across the tree. The heap gains one-hop access through any index. You pay with no physical ordering by key and, because PostgreSQL’s MVCC writes a new row version on each update, extra index maintenance that HOT updates only partly avoid. PostgreSQL vs MySQL covers the wider comparison.

Unique indexes and constraints

A unique index is a B+tree that refuses to hold two entries with the same key. Before inserting, the database descends to where the new key would go; if an equal key is already there, the insert fails.

• Constraints are enforced by indexes. In PostgreSQL, declaring a PRIMARY KEY or UNIQUE constraint automatically creates a unique B-tree index, and that index is the enforcement mechanism. Adding your own index on the same column only duplicates it.
• Only B-trees can be unique in PostgreSQL.
• NULLs are distinct by default, so a unique column can hold many NULLs. PostgreSQL accepts NULLS NOT DISTINCT when you want at most one.
• Multicolumn uniqueness rejects a row only when all the indexed columns match: (restaurant_id, menu_slug) lets every restaurant have its own “paneer-tikka”.
• Expressions can be unique too. A unique index on lower(email) stops Asha@x.in and asha@x.in from coexisting, a rule a plain column constraint can’t express.

Uniqueness is a correctness feature, not just a speed feature. A unique index is the cheapest race-free way to stop a double sign-up or a payment recorded twice: when two transactions insert the same key at once, only one can commit. That makes it the backbone of idempotency keys and many database constraints.

The write cost of every index

An index is a copy of data, and every copy must be kept in step with the table:

• INSERT adds an entry to every index: a descent and a leaf-page change per index, each with its own write-ahead log record.
• DELETE must eventually remove the row’s entry from every index (in PostgreSQL, vacuum does this later; see vacuum and bloat).
• UPDATE of an indexed column removes the old entry and adds a new one. In PostgreSQL, an update that can’t use the HOT optimization adds a new entry to every index on the table, even those whose columns didn’t change, because the new row version has a new ctid.

Put numbers on it. A food-delivery orders table takes 2,000 new orders a second at the lunch peak. Besides the primary key it has four secondary indexes: customer_id, restaurant_id, delivery_partner_id and created_at.

• Page changes per insert: 1 heap page + 5 index leaf pages = 6.
• Per second: 2,000 × 6 = 12,000 page changes/s, against 2,000 × 2 = 4,000 with only the primary key. That is three times the write work for the same business traffic.
• The five index leaves are five different pages, mostly in random places, so each one competes for buffer-pool memory and adds its own log record.

Space adds up too. Each bigint index costs about 20 bytes per row (from the fan-out arithmetic). If orders grows to 500 million rows, that is 500M × 20 B = 10 GB per index, so 50 GB for five: well over half the 80 GB that 500 million rows of 160 bytes occupy, and all of it competes with the table for RAM.

The rule of thumb: every index must serve a frequent or latency-critical query, because every index taxes every write. Finding the ones that don’t, and dropping them safely, is part of indexes in practice.

When an index doesn’t help

Whether an index helps depends on selectivity: the fraction of rows a predicate matches. Cardinality, the number of distinct values in a column, is a rough guide to it.

• Selective predicates match few rows: WHERE payment_id = …, WHERE email = …. An index is a huge win.
• Unselective predicates match many: WHERE status = 'delivered' when 92% of orders are delivered. The index would hand back 460 million row pointers on a 500-million-row table, each needing a table page; reading the table straight through is cheaper. PostgreSQL’s documentation draws the line at values that account for more than a few percent of the table: queries for those won’t use the index anyway.

Four patterns account for most “but there is an index!” surprises:

1. Low-cardinality columns. A boolean or a five-value status helps only for its rare values, and then a partial index on just those rows is the better tool.
2. A function or arithmetic on the column. WHERE lower(email) = 'asha@x.in' or WHERE created_at + interval '1 day' > now() can’t use an index on email or created_at, because the index is sorted by the bare column. Rewrite the predicate so the column stands alone (created_at > now() - interval '1 day'), or index the expression itself.
3. A leading wildcard. LIKE '%galore' has no starting point in a sorted list; you need a trigram or full-text index.
4. A type mismatch. In MySQL, comparing a string column with a number (WHERE phone = 9876543210 on a VARCHAR column) can’t use the index, because many different strings convert to the same number.

The planner’s side of this story is in index scan vs full table scan; the production fixes (partial, expression and trigram indexes) are in indexes in practice.

Beyond the B-tree: other index types

B-trees handle values with a natural sort order. Documents, arrays, coordinates and huge append-only logs get specialised index types. You don’t need their internals for an interview, but you should know which one fits which query.

In designs, GIN and full-text indexes power search boxes (how search engines work), GiST powers “restaurants near me” (geospatial indexes), bitmaps belong to OLAP and columnar storage, and LSM-based indexes follow from the storage engine. Once data is sharded, each index is either local to a shard or global across shards, a trade-off covered in database sharding.

Cheat sheet

How to say it in the interview

“An index is a sorted copy of a column with pointers back to the rows, usually a B+tree. Without one, a lookup scans every page, which is linear in table size. With one, I walk from the root to a leaf: at about 400 keys per 8 KB page that’s three or four page reads for hundreds of millions of rows, and the upper levels are cached anyway. The leaves are linked, so the same index serves range queries and ORDER BY with LIMIT. But every index costs space and slows every write, so I only index the hot path: here, orders by customer_id and created_at, and a unique index on the payment’s idempotency key. In MySQL I’d keep the primary key short and sequential, because every secondary index stores a copy of it.”

Why a B+tree and not a binary search tree or a hash index? A binary tree has fan-out 2, so a billion keys need about 30 levels (2³⁰ ≈ 1.07 billion), each a potential disk read. A B+tree packs hundreds of keys per page, so it needs four. A hash index answers only equality; a B+tree also does ranges, sorting and prefix matches at nearly the same cost.

How many disk reads does an index lookup really cost? Height plus one for the table page: about five for a 500-million-row table. But the root and internal levels total about 25 MB and stay in memory, so a cold lookup usually costs one or two real reads, the leaf and the row. A covering index can even skip the table page; see composite index design.

Why not index every column? Each one is updated on every insert, takes space and competes for memory: a primary key plus four secondary indexes triples an insert’s page writes. An index no query uses is pure cost.

Why is a secondary-index lookup slower than a primary-key lookup in MySQL? InnoDB secondary entries store the primary key, not a row address, so the lookup walks the secondary tree and then the clustered tree. In PostgreSQL both kinds of lookup are one walk plus one heap page.

There is an index on the column, but the query is still slow. Why? Read the plan first. The usual causes: the predicate matches a large share of the table, so a scan is cheaper; a function or type cast hides the column; a leading wildcard; or stale statistics misleading the planner.

Where to go next

• Composite index design: multi-column indexes, column order, covering indexes and index-only scans.
• Index scan vs full table scan: why the planner sometimes ignores your index, and when it is right to.
• Query execution plans: read EXPLAIN output to see which index a query actually uses.
• Indexes in practice: partial, expression, GIN and BRIN indexes, building indexes on live tables, and pruning unused ones.
• Reads and writes: how databases store and fetch data: pages, buffer pools, and B-trees versus LSM trees.
• Offset vs keyset pagination: paging through results with a sorted index instead of OFFSET.
• PostgreSQL: the engine behind most of the examples here.
• Database scaling: where index tuning sits on the ladder from one server to many shards.

References and further reading

1. PostgreSQL documentation: Introduction to indexespostgresql.orgThe book-index analogy, which WHERE and JOIN clauses an index can serve, and why every index adds write overhead and can prevent HOT updates.
2. PostgreSQL documentation: Index typespostgresql.orgOperators each index type supports: B-tree ranges and anchored LIKE, 32-bit hash codes, GiST nearest-neighbour search, GIN and BRIN.
3. PostgreSQL documentation: B-tree implementationpostgresql.orgLeaf and internal pages, levels linked in both directions, page splits that cascade up to the root, and over 99% of pages being leaves.
4. PostgreSQL documentation: Database page layoutpostgresql.org8 kB pages, the 24-byte page header and 4-byte item identifiers used in the fan-out arithmetic.
5. PostgreSQL documentation: Unique indexespostgresql.orgUnique constraints and primary keys are enforced by automatically created B-tree indexes; NULL handling and NULLS NOT DISTINCT.
6. PostgreSQL 10 release notespostgresql.orgWrite-ahead logging for hash indexes, which made them crash-safe and replicated from version 10.
7. MySQL 8.0 Reference Manual: Clustered and secondary indexesdev.mysql.comInnoDB stores rows in the primary-key index, its fallback rules, and secondary index records that carry the primary key.
8. MySQL 8.0 Reference Manual: The physical structure of an InnoDB indexdev.mysql.comB-trees for all non-spatial indexes, the 16 KB default page size, and how full pages end up under sequential versus random inserts.
9. The Ubiquitous B-Tree (Comer, ACM Computing Surveys, 1979)carlosproal.comThe classic survey: Bayer and McCreight’s B-tree, logarithmic search cost, and the B+-tree with every key in a linked leaf level.
10. Oracle Database Concepts: Indexes and index-organized tablesdocs.oracle.comBitmap indexes for low-cardinality, read-mostly warehouse columns and why they suit OLTP poorly; index-organized versus heap tables.