How a B-Tree Index Actually Works

You add an index on the column in the slow query, the query gets faster, and you move on. Then a report that used to take 200 ms takes four seconds, the table has grown by a million rows, and nobody can explain why the index that fixed one query made another one worse. None of that is mysterious if you know what the index physically is.

The examples ran on MySQL 9.6.0 with InnoDB. Where SQLite or PostgreSQL differs, the difference is named. PostgreSQL 16.14 is installed on this machine but has no running server, so its behaviour below comes from its own manual and the command line is not shown.

All of it happens on a table called g_narrow_50k: 50,000 rows, a primary key on id, and a secondary index on (aid, created_at).

An index is a sorted tree of key values that point back at rows

When you create an index, the engine builds a separate structure of pages. Every page is 16 KB in InnoDB. A leaf page holds many entries in key order, and each entry is the indexed value followed by a pointer to the row. Pages that are not leaves hold separator keys and pointers to the pages below them.

That shape is what makes a lookup cheap. The engine reads one page near the top, follows one pointer per level, and arrives at the leaf that can hold the value. The number of pages it reads is the depth of the tree, and the table could be a thousand times larger without that number changing.

The tree is shallow, and it stays shallow because the fanout is large. You can measure the real depth of an index rather than estimate it: the root page number is in information_schema.INNODB_INDEXES.PAGE_NO, and the level of that page is a two-byte field at offset 64 of the page header.

SELECT i.NAME AS index_name, i.PAGE_NO AS root_page
FROM information_schema.INNODB_TABLES t
JOIN information_schema.INNODB_INDEXES i ON i.TABLE_ID = t.TABLE_ID
WHERE t.NAME = 'm4lab/g_narrow_50k';

index_name  root_page
PRIMARY             4
idx                 5

The level stored at page 4 is 1, and the level at page 5 is 1. Level 0 is a leaf, so a level-1 page is a root that points directly at leaves. Both indexes on this table are two levels deep: one root page, then the leaves. Here is the whole tree for the same table, counted by reading every page header in the file.

SELECT i.NAME AS index_name, i.PAGE_NO AS root_page,
       (SELECT stat_value FROM mysql.innodb_index_stats s
         WHERE s.database_name='m4lab' AND s.table_name='g_narrow_50k'
           AND s.index_name=i.NAME AND s.stat_name='n_leaf_pages') AS leaf_pages
FROM information_schema.INNODB_TABLES t
JOIN information_schema.INNODB_INDEXES i ON i.TABLE_ID = t.TABLE_ID
WHERE t.NAME = 'm4lab/g_narrow_50k';

index_name  root_page  leaf_pages
PRIMARY             4         118
idx                 5         100

One root page is enough to point at a hundred leaf pages, because a separator entry for this key is about twenty bytes and thousands of them fit in 16 KB. The arithmetic is the whole story: with a fanout of 1,000, level 1 covers a million leaves, and level 2 covers a billion. Depth grows with the logarithm of the number of entries, which is why 50,000 rows and 5,000 rows are both two levels deep and both take the same number of page reads.

Depth is driven by key size, not by row count

Duplicate that table three times with wider index keys, load the same row count into each, and read the depth again. This is the measurement that corrects the intuition that index lookups get slower as a table grows.

table            index     leaf_pages  depth
g_narrow_1k      idx                2      1
g_narrow_5k      idx                8      1
g_narrow_50k     idx              100      1
g_mid_1k         idx               21      1
g_mid_5k         idx              101      2
g_mid_50k        idx             1001      2
g_wide_1k        idx               51      2
g_wide_5k        idx              251      2
g_wide_10k       idx              501      3

g_narrow indexes (aid, created_at), about twenty bytes of key. g_mid indexes a 308-byte string. g_wide indexes a 768-byte prefix of a TEXT column, which is the largest key InnoDB will build on a utf8mb4 column.

The narrow index is still two levels deep at 50,000 rows. The wide one is three levels deep at 10,000 rows, so it reads one more page per lookup while holding a fifth of the data. A wider key means fewer entries per page, fewer entries per root, and a deeper tree. This is the argument against putting a long string or a UUID stored as text in an index when a number would do, and it is a better argument than "indexes are big".

InnoDB's primary key is the table, which is why there is no row id

In InnoDB the table itself is the primary key index. The rows live in the leaves of that tree, in primary key order, and that structure is called a clustered index. There is no separate heap of unordered rows to point at, so PRIMARY shows up in INNODB_INDEXES like any other index and its leaves are the rows.

That changes what a secondary index can store. It cannot hold a physical row address, because rows move when a page splits. So every secondary index entry is the indexed columns followed by the primary key value, and a lookup through a secondary index is two tree descents: find the primary key in the secondary tree, then look that key up in the clustered tree.

Two consequences follow immediately. An index on (aid, created_at) is really an index on (aid, created_at, id), which is why adding id to a select list does not stop the index from covering. And a table with a long primary key makes every secondary index longer, because the key is copied into each of them.

PostgreSQL works the other way. Every index there is a secondary index over a heap, and the index entry stores a physical tuple identifier rather than a copy of the primary key. Index-only scans are possible because the index can hold the values the query needs, and PostgreSQL checks a visibility map to decide whether it can skip the heap. The manual describes both the restriction and the map in 11.9 Index-Only Scans and Covering Indexes. SQLite's ordinary tables are rowid tables, and an index stores the rowid, which is the same idea as InnoDB with a narrower pointer.

Every index is a second copy of the data that must be kept in order

An insert into an indexed table is an insert into the table plus one insert into every index on it. Those inserts have to find the right leaf and may split it, and every split has to be written durably. The same applies to an update that changes an indexed column: the old entry is marked deleted and a new one is inserted. Delete is cheaper, but it still writes.

The size of the effect is easy to measure with two tables that differ only in their indexes: one with a primary key, one with three secondary indexes. Loading 100,000 rows through the same INSERT ... WITH RECURSIVE statement, three times each on this machine:

no-index run 1: 413 ms
no-index run 2: 384 ms
no-index run 3: 390 ms
with-indexes run 1: 937 ms
with-indexes run 2: 961 ms
with-indexes run 3: 1271 ms

Three indexes roughly doubled the cost of the load, and the last run shows why single measurements are not worth quoting: background activity on the same disk moved it by a third. The ratio matters, not the milliseconds. An index is not free, and the bill arrives on every write path, including the ones you did not write.

This is also the reason UPDATE statements that touch an indexed column are the expensive ones, and the reason a bulk load into a table is faster with the indexes dropped and rebuilt afterwards. Deferred maintenance is a real technique; it is just not one to reach for until you have measured the load.

The leftmost-prefix rule is the shape of the tree, not a rule to memorise

Entries in the index on (aid, created_at) are sorted by aid first, then by created_at inside each aid. Everything people memorise as a rule comes out of that one sentence.

A query with an equality on aid knows where to start and where to stop, because all the entries for aid = 7 are adjacent. A range on aid works the same way, since a range is a contiguous run of entries. A condition on created_at alone gives the engine nowhere to aim, because those values are scattered across every aid group.

EXPLAIN SELECT id FROM g_narrow_50k WHERE aid = 7;

-> Covering index lookup on g_narrow_50k using idx (aid = 7)  (cost=50.5 rows=500)

An index lookup, from one page at the top to the leaves that hold aid = 7. Now the same index with only the second column in the predicate:

EXPLAIN SELECT id FROM g_narrow_50k WHERE created_at > '2026-01-01 13:00:00';

-> Filter: (g_narrow_50k.created_at > TIMESTAMP'2026-01-01 13:00:00')  (cost=4263 rows=16372)
    -> Covering index skip scan on g_narrow_50k using idx over '2026-01-01 13:00:00' < created_at  (cost=4263 rows=16372)

The access path is a skip scan, which is not a seek. MySQL walks the index collecting distinct aid values and jumps between them, reading 16,372 rows to answer a question the index cannot answer directly. It is cheaper than the table scan here only because the index is small. SQLite has no skip scan and scans the index entry by entry; PostgreSQL can use a bitmap index scan when the leading column is missing but has the same limitation on the seek.

The rule has one part that surprises people. A range on a column stops the index from helping with the columns after it, because once you are scanning a range there is no single position to seek to inside it. An equality followed by a range is fine; a range followed by anything is not. Lesson eleven works through this with a plan for each shape.

A covering index answers the query without touching the row

If every column a query needs is present in the index, the engine can return the answer from the leaves and skip the second descent into the clustered index. InnoDB reports this in the plan with the word "Covering", and PostgreSQL calls the same thing an index-only scan.

EXPLAIN SELECT aid, created_at FROM g_narrow_50k WHERE aid = 7;

-> Covering index lookup on g_narrow_50k using idx (aid = 7)  (cost=50.5 rows=500)

Add a column the index does not hold and the plan loses the word:

EXPLAIN SELECT customer_id, created_at, amount_cents FROM orders WHERE customer_id = 7;

-> Index lookup on orders using idx_customer_created (customer_id = 7)  (cost=8.75 rows=25)

Twenty-five rows, each requiring a primary key lookup to fetch amount_cents. For twenty-five rows that cost is invisible. For a query that returns a hundred thousand rows it is the difference between a report that finishes and one that does not, because a secondary lookup scattered across the clustered index is random I/O inside the buffer pool.

The covering trick has a limit worth stating: you cannot cover a query that asks for a column the index does not contain, and adding that column to the index widens every entry. Covering is a decision to trade write cost and index size for read cost, and it should be made for a query you run constantly, not as a default.

A low-cardinality index is often not worth the descent

The planner compares the cost of reading the index and fetching rows with the cost of reading the table once. When a value appears in a large fraction of the table, the second option wins, and your index is ignored.

CREATE TABLE big_flags (
  id BIGINT NOT NULL AUTO_INCREMENT PRIMARY KEY,
  customer_id INT NOT NULL,
  is_gift TINYINT(1) NOT NULL,
  amount_cents INT NOT NULL,
  KEY idx_gift (is_gift)) ENGINE=InnoDB;

SELECT is_gift, COUNT(*) FROM big_flags GROUP BY is_gift;

+---------+----------+
| is_gift | COUNT(*) |
+---------+----------+
|       0 |    25000 |
|       1 |    25000 |
+---------+----------+

-> Filter: (big_flags.is_gift = 1)  (cost=5047 rows=25193)
    -> Table scan on big_flags  (cost=5047 rows=50100)

Half the table matches, so the planner reads the table sequentially and checks the flag on each row. It still estimates 25,193 matching rows, which is close, and it still refuses the index. When the same index is used, the reason is selectivity rather than the existence of the index: on the same table in an earlier run, is_gift = 1 matched 0.1% of the rows and the planner estimated 50, and the plan became a covering index lookup with a cost of 5.26.

Cardinality here means the number of distinct values, and information_schema.STATISTICS.CARDINALITY reports what the engine currently believes. On the orders table, the composite index shows 200 for customer_id and 5,000 for created_at, which is exactly the shape of the data: two hundred customers, a distinct timestamp per row.

SELECT INDEX_NAME, SEQ_IN_INDEX, COLUMN_NAME, CARDINALITY
FROM information_schema.STATISTICS
WHERE TABLE_SCHEMA = 'm4lab' AND TABLE_NAME = 'orders'
ORDER BY INDEX_NAME, SEQ_IN_INDEX;

INDEX_NAME           SEQ_IN_INDEX  COLUMN_NAME  CARDINALITY
idx_customer_created            1  customer_id          200
idx_customer_created            2  created_at          5000
PRIMARY                         1  id                  5000

Those numbers come from sampled statistics, not from a full count, and they move as the data changes and after ANALYZE TABLE. A planner that believes the wrong cardinality picks the wrong plan, which is the practical reason to keep statistics fresh on a table that gets bulk-loaded.

Show the solution and the reasoning

Reading the level field is the only honest way to answer the depth question on a small table, because the fanout is large enough that depth 1 is normal. The integer index will be level 1: its entries are small, so a few leaf pages fit under one root. The wide index will also be level 1 at 4,000 rows, with roughly eighty leaf pages, because a 300-byte key still leaves about fifty keys per page. If you loaded 40,000 wide rows instead, the wide index would reach level 2 while the integer index stayed at level 1, which is the point of the exercise: the thresholds are different for the two indexes, so "is my index fast" has no answer that does not name the index.

On the plan costs, the wide index reports a higher cost per lookup even when both are covering, because each entry is larger and fewer fit in a page. The buffer pool hides the difference on this machine, which is why the plan cost is more informative here than the wall-clock time. On a table larger than memory the difference becomes I/O.

The four queries are the leftmost-prefix rule restated. Filtering on aid seeks: the matching entries are adjacent. Filtering on created_at alone cannot seek, because entries with a given timestamp are spread across all fifty aid groups. Filtering on aid with a created_at range seeks to the group and scans within it, which is the shape the index was built for. Filtering on both with equality is the best case, and it is the only one where the index lands on a single leaf and reads exactly the matching entries. There is no configuration or hint that changes the third case into a seek; the tree is sorted by the first column, so that is the only column a seek can start from.