Database Indexing Explained: B-Trees, B+Trees, LSM Trees & Composite Indexes

If you have ever fixed a slow API by adding one line of SQL, you have seen indexing at work: a query goes from 4 seconds to 3 milliseconds. This guide explains why that happens, from the page layout of a B+tree up to reading an EXPLAIN ANALYZE output. It is written for backend engineers preparing for system design and DBMS rounds, and for anyone who wants to stop guessing which index to create.

Why Indexes Exist: The Cost of a Full Table Scan

Databases store rows in fixed-size pages (8 KB in Postgres, 16 KB in MySQL InnoDB). Reading from disk or even from the OS cache happens a page at a time. Without an index, answering SELECT * FROM orders WHERE order_id = 98123 means reading every page of the table and checking every row. That is a sequential scan, and its cost grows linearly with table size.

Let us put numbers on it. Take an orders table with 100 million rows of about 200 bytes each:

• Table size ≈ 100M × 200 B = 20 GB, which is about 2.5 million 8 KB pages.
• A full scan reads all 2.5M pages. Even at 1 GB/s of sequential throughput, that is ~20 seconds, and it evicts useful pages from the buffer cache.
• With a B+tree index on order_id, the lookup reads ~4 pages (root, two internal levels, leaf) plus one heap page. With the upper levels cached in memory, that is usually one or two actual I/Os: well under a millisecond on SSD.

That gap, O(n) versus O(log n) with a huge logarithm base, is the entire reason indexes exist. The price you pay is extra storage and slower writes, because every INSERT, UPDATE of an indexed column and DELETE must also update every index on the table.

How a B+Tree Index Works (and How It Differs from a B-Tree)

A binary search tree has a fan-out of 2, so 100 million keys would need about 27 levels. Twenty-seven random disk reads per lookup is unacceptable. A B-tree fixes this by making every node a whole disk page holding hundreds of keys, so each node has hundreds of children. The tree becomes short and wide.

The B+tree structure

Almost every relational engine actually uses the B+tree variant, which has two defining properties:

1. Internal nodes only route. They hold separator keys and child pointers, never row data. That keeps them small, which maximises fan-out.
2. All entries live in the leaves, and leaves are linked to their neighbours (doubly linked in InnoDB and Postgres). A range query finds the first leaf and then walks sideways.

In a classic B-tree, by contrast, a key and its data can sit in an internal node. A lookup might finish higher up, which sounds good, but internal nodes become bigger (lower fan-out) and range scans need an in-order traversal that bounces up and down the tree. In practice the B+tree's predictable leaf-level access and cheap range scans win.

Fan-out math: why the tree is only 3–4 levels deep

Suppose the key is an 8-byte BIGINT and a child pointer is about 6–8 bytes. With per-entry overhead, an 8 KB internal page holds roughly 400–500 entries. Use 400 to be conservative:

• Level 1 (root): 1 page, 400 children
• Level 2: 400 pages, 160,000 children
• Level 3: 160,000 pages, 64 million leaf pointers
• Level 4: enough for ~25 billion entries

So a 100M-row index is 4 levels deep. The root and level 2 total ~401 pages (~3 MB), which stay hot in memory. Real lookups hit disk at most for the bottom one or two levels. This is why "an index lookup is O(log n)" undersells it: with a base of 400, log n is tiny.

A practical consequence: wide keys hurt. Index a 255-character VARCHAR email and fan-out drops sharply, the tree grows deeper and fewer pages fit in cache. This is also why InnoDB advice says to keep primary keys small: every secondary index stores the primary key in its leaves.

Inserts, page splits and why random UUID keys hurt

Inserting a key means finding the correct leaf and adding the entry. If the leaf is full, it splits into two half-full pages and a new separator is pushed into the parent, which can cascade up to the root (the only way a B+tree grows taller). Deletes can merge underfilled pages, though many engines delay this.

With a monotonically increasing key (auto-increment ID, timestamp, ULID, UUIDv7), inserts always land in the rightmost leaf. Pages fill up neatly and the working set of "hot" pages is tiny. With random UUIDv4 keys, every insert lands on a random leaf. Across a large index that means random I/O, frequent splits leaving pages around half full, and a buffer pool that cannot hold the whole hot set. This is a classic reason write throughput collapses as a MySQL table grows past memory, and why time-ordered IDs are recommended (see our Snowflake ID generator design).

Clustered vs Secondary (Non-Clustered) Indexes

A clustered index is one where the table data is physically stored in index order: the leaves of the index are the rows. A secondary index is a separate B+tree whose leaves store the indexed key plus a pointer to the row. How that pointer works differs between the two most common engines, and interviewers love this difference.

MySQL InnoDB: the table is the primary key index

InnoDB always clusters by primary key. If you do not define one, it uses the first non-null unique index, or else a hidden 6-byte row ID. Secondary index leaves store (indexed columns, primary key). A lookup through a secondary index therefore does two tree traversals: one in the secondary index to find the primary key, then one in the clustered index to fetch the row. This is sometimes called a "bookmark lookup" or a lookup "back to the table".

PostgreSQL: heap table plus indexes

Postgres stores rows in an unordered heap. Every index, including the primary key index, is secondary: leaves store (key, TID), where the TID is a physical (page, offset) address. A lookup is one tree traversal plus one heap page fetch. CLUSTER can physically reorder a table once, but the order is not maintained afterwards.

Composite Indexes and Why Column Order Matters

A composite (multi-column) index on (a, b, c) is a single B+tree whose entries are sorted by a first, ties broken by b, then by c. Think of a phone book sorted by (last name, first name): great for "Sharma, Priya", useless for "everyone named Priya".

The leftmost prefix rule

Given CREATE INDEX idx ON orders (customer_id, status, created_at):

Equality first, range last (the ESR rule)

A practical ordering heuristic (MongoDB documents it as the Equality, Sort, Range rule, and it applies equally to SQL):

1. Equality columns first. Columns compared with = or a small IN list. Every equality narrows the seek to a contiguous slice of the index.
2. Then the sort column. If the remaining slice is already sorted by your ORDER BY column, the database avoids a sort step and can stop early with LIMIT.
3. Range columns last. Once the index hits a range predicate, columns after it can no longer be used for seeking, only filtering.

Worked example: the "my orders" page

A food delivery app shows a customer's recent orders:

SELECT order_id, restaurant_id, total_amount, created_at
FROM orders
WHERE customer_id = 42
  AND status IN ('DELIVERED', 'CANCELLED')
ORDER BY created_at DESC
LIMIT 20;

Options and what happens:

• Index on (created_at): the database walks recent orders across all customers and filters for customer 42. If customer 42 last ordered months ago, it scans millions of entries. Bad.
• Index on (customer_id): finds all of customer 42's orders (maybe 300), fetches each row, filters status, sorts and returns 20. Acceptable, but 300 random heap fetches plus a sort.
• Index on (customer_id, created_at): seeks to customer 42, reads entries already ordered by created_at, walks backwards, fetches rows and checks status, stopping after 20 matches. Usually excellent.
• Index on (customer_id, status, created_at): with an IN list, the database seeks once per status and must merge the two sorted streams. Postgres often does this fine; some planners fall back to a sort. Measure with EXPLAIN.

Usually the winner is (customer_id, created_at), possibly with the selected columns added for a covering index (next section). Notice the reasoning: start from the query's filter and sort shape, not from "which columns appear in WHERE".

Covering Indexes and Index-Only Scans

Every secondary index lookup has two costs: walking the index, and fetching the row from the table (heap fetch in Postgres, clustered index lookup in InnoDB). For queries that return many rows, the second part dominates because those fetches are random I/O. A covering index removes it by including every column the query reads.

-- PostgreSQL 11+: INCLUDE adds payload columns to the leaves only
CREATE INDEX idx_orders_cust_created
  ON orders (customer_id, created_at DESC)
  INCLUDE (order_id, restaurant_id, total_amount, status);

-- MySQL: no INCLUDE clause, so append the columns as key columns.
-- order_id is the primary key, so InnoDB stores it in the leaf anyway.
CREATE INDEX idx_orders_cust_created
  ON orders (customer_id, created_at, status, restaurant_id, total_amount);

In EXPLAIN, Postgres reports Index Only Scan and MySQL shows Using index in the Extra column. In Postgres there is one subtlety: because of MVCC, the index does not know whether a tuple is visible to your transaction. Postgres checks the visibility map; for pages marked all-visible it skips the heap, otherwise it still visits the heap. The Heap Fetches number in EXPLAIN ANALYZE shows how often that happened. A recently vacuumed table gets the full benefit.

Covering indexes are not free: they are bigger, slower to maintain, and duplicate data. Use them for a small number of very hot, read-heavy queries, not as a default.

How to Read EXPLAIN and EXPLAIN ANALYZE

EXPLAIN shows the plan the optimizer chose and its estimates. EXPLAIN ANALYZE actually runs the query and shows real times and row counts. (Careful: EXPLAIN ANALYZE on an UPDATE or DELETE really modifies data, so wrap it in a transaction and roll back.)

A Postgres example, before and after

EXPLAIN ANALYZE
SELECT order_id, total_amount FROM orders
WHERE customer_id = 42 ORDER BY created_at DESC LIMIT 20;

-- Before (no suitable index)
Limit  (cost=2189134.21..2189134.26 rows=20 width=16)
       (actual time=4210.552..4210.560 rows=20 loops=1)
  ->  Sort  (cost=2189134.21..2189135.01 rows=318 width=16)
            (actual time=4210.550..4210.553 rows=20 loops=1)
        Sort Key: created_at DESC
        ->  Seq Scan on orders  (cost=0.00..2189125.75 rows=318 width=16)
                                (actual time=12.1..4209.8 rows=301 loops=1)
              Filter: (customer_id = 42)
              Rows Removed by Filter: 99999699
Execution Time: 4210.6 ms

-- After CREATE INDEX ON orders (customer_id, created_at DESC) INCLUDE (order_id, total_amount)
Limit  (cost=0.57..9.21 rows=20 width=16) (actual time=0.031..0.058 rows=20 loops=1)
  ->  Index Only Scan using idx_orders_cust_created on orders
        (cost=0.57..138.02 rows=318 width=16) (actual time=0.030..0.054 rows=20 loops=1)
        Index Cond: (customer_id = 42)
        Heap Fetches: 0
Execution Time: 0.081 ms

(The numbers are illustrative of the shape you will see, not a benchmark.)

What to look at, in order

1. Node types. Seq Scan reads the whole table. Index Scan walks the index and fetches rows. Index Only Scan avoids the table. Bitmap Index Scan + Bitmap Heap Scan collects matching TIDs, sorts them by page, then reads pages in physical order; the planner picks it for medium selectivity.
2. Estimated vs actual rows. rows=318 estimated vs rows=301 actual is healthy. If the estimate is 10 and the actual is 2 million, statistics are stale or the predicate is correlated in ways the planner cannot see. Run ANALYZE, raise the statistics target, or create extended statistics.
3. Rows Removed by Filter. A big number means the database read many rows only to throw them away. That is the classic sign of a missing or wrongly ordered index.
4. Sort nodes. A Sort above a scan with a LIMIT means the index does not provide the order. Look at Sort Method: external merge Disk, which means the sort spilled to disk.
5. Loops. In nested loop joins, the inner node's time is per loop. Multiply by loops to get the real cost.

MySQL EXPLAIN in brief

In MySQL the key columns are type (from best to worst: const, eq_ref, ref, range, index, ALL), key (the index chosen), rows (estimated rows examined) and Extra. Watch for Using filesort (an extra sort step), Using temporary (a temp table, often from GROUP BY) and Using index (covering). MySQL 8.0.18+ supports EXPLAIN ANALYZE with actual timings, and EXPLAIN FORMAT=TREE gives a Postgres-like tree.

Why Your Index Is Not Being Used: 8 Common Causes

"I created an index but the query is still slow" is one of the most common production issues, and a favourite interview follow-up. The usual causes:

1. A function on the column. WHERE DATE(created_at) = '2026-10-01' or WHERE LOWER(email) = 'a@b.com' cannot use a plain index on that column. Rewrite as a range (created_at >= '2026-10-01' AND created_at < '2026-10-02') or create an expression index: CREATE INDEX ON users (LOWER(email)).
2. Implicit type conversion. Comparing a VARCHAR phone column with a number (WHERE phone = 9876543210) makes MySQL convert every row's value, which kills the index. Quote the literal.
3. Leading wildcard. LIKE '%sharma' cannot seek in a B+tree. LIKE 'sharma%' can (in Postgres, with the C collation or a text_pattern_ops index). For substring search use a trigram GIN index or a search engine.
4. Not a leftmost prefix. Filtering on the second column of a composite index only.
5. Low selectivity. If status = 'ACTIVE' matches 70% of rows, a sequential scan is genuinely cheaper than millions of random fetches. The optimizer is right to ignore the index. A partial index on the rare value (WHERE status = 'FAILED') is the fix if you only query the rare case.
6. OR across different columns. WHERE a = 1 OR b = 2 may need two indexes combined with a bitmap OR, or a UNION rewrite.
7. Stale statistics. After a bulk load, the planner may think a table has 1,000 rows. Run ANALYZE.
8. Small tables. For a table that fits in a few pages, a scan is the fastest plan. Not a problem to fix.

LSM Trees vs B-Trees: The Write-Optimised Alternative

B+trees update data in place: changing a row rewrites the page it lives on. For write-heavy workloads such as logs, metrics, chat messages and IoT events, that random I/O becomes the bottleneck. The Log-Structured Merge tree (LSM tree) takes the opposite approach: never update in place, always append.

How an LSM tree works

1. Write-ahead log. Each write is appended to a WAL on disk for durability (sequential I/O).
2. Memtable. The write goes into an in-memory sorted structure (often a skip list).
3. Flush. When the memtable reaches a size limit (tens of MB), it is written out as an immutable sorted file called an SSTable. Again sequential.
4. Compaction. Background jobs merge SSTables, discarding overwritten values and deleted keys (tombstones). Strategies are leveled (RocksDB default; lower space and read amplification, more write amplification) or size-tiered (Cassandra's traditional default; cheaper writes, more space).
5. Reads. Check the memtable, then SSTables from newest to oldest. Each SSTable has a Bloom filter to skip files that definitely do not contain the key, plus a sparse index to find the right block.

Bloom filters are what make LSM point reads tolerable; we cover the math in Bloom filters explained.

The three amplifications

In a system design interview, the right framing is: "This workload is ~95% writes of append-only events with reads by key and recent time window, so an LSM-based store like Cassandra fits. If the workload were read-heavy with complex secondary-index queries and transactions, I'd pick Postgres." See how this plays out in designing a key-value store.

Hash, GIN, GiST, BRIN, Partial and Expression Indexes

B+trees are the default, but not the only option. Knowing when to reach for something else is a strong signal in interviews.

Vector similarity indexes (HNSW, IVF) are a separate family for embeddings; they trade exactness for speed in high-dimensional nearest-neighbour search.

Indexing checklist for a new table

• List the top 5 queries by frequency and latency requirement. Index for those, not for every column.
• For each, write the filter/sort shape and derive the composite order with the ESR rule.
• Look for one index that serves multiple queries via a shared prefix.
• Consider covering only for the hottest one or two.
• Index foreign keys used in joins (Postgres does not create them automatically).
• Build indexes on big live tables with CREATE INDEX CONCURRENTLY (Postgres) or online DDL (MySQL) to avoid blocking writes.
• After a few weeks, drop indexes with zero scans in pg_stat_user_indexes or sys.schema_unused_indexes.

How Indexing Shows Up in Interviews

Indexing appears in three kinds of rounds: DBMS theory questions (common in campus and fresher interviews, see our DBMS interview questions), SQL/backend rounds ("this query is slow, fix it"), and system design rounds, where you are expected to name the access patterns and the indexes that serve them.

Questions you should be ready for

• Why B+tree and not a binary search tree or hash table? Disk is page-oriented; high fan-out minimises I/O. Hash tables cannot do ranges or ordered scans.
• Why not index every column? Write amplification, storage, buffer pool pressure, and the optimizer still uses only one or a few indexes per table access.
• Given this query, design the index. Walk through equality, sort, range. Mention covering if it is hot.
• What happens to indexes on UPDATE? InnoDB: secondary indexes change only if their columns change. Postgres: a new tuple version is created; indexes need new entries unless it is a HOT update (no indexed column changed and space on the same page).
• How would you add an index to a 500 GB table with zero downtime? Concurrent/online index build, or tools like gh-ost/pt-online-schema-change for MySQL schema changes; monitor replication lag.
• When would you choose an LSM-based database? Write-heavy, append-mostly, key-based reads; accept compaction overhead.

Red flags interviewers notice

• Saying "add an index on each column in the WHERE clause" without thinking about composite order.
• Claiming indexes make every query faster (they slow writes, and low-selectivity predicates do not benefit).
• Confusing clustered index with "primary key" in Postgres, where there is no maintained clustering.
• Not mentioning that sharded systems need indexes that align with the shard key, or else become scatter-gather (see database sharding strategies).

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.