Indexes in depth series: 1. Inside an index · 2. Index types beyond the B-tree
This post goes below “add an index and it gets faster”: what a B+tree stores, where InnoDB and PostgreSQL put the row, and why a UUIDv4 primary key is slow. Afterwards you can pick a primary key, read a composite-index plan correctly and know when to rebuild. Every number comes from real runs on PostgreSQL 16 and MySQL 8.4.
Read first: Indexes, EXPLAIN, N+1 and pagination (leftmost prefix, covering indexes, sargability). The hands-on parts on hash indexes, LIKE, composite column order and INCLUDE live in the index lab on the airline dataset and aren’t repeated here.
1. Keys vs indexes
Key idea: a key is a constraint (a rule the data must follow); an index is a data structure (for fast lookup). The database enforces PK and UNIQUE with indexes.
- Key: primary key = not null and unique; unique key = unique; foreign key = the value must exist in the parent table.
- Index: a sorted copy of a few columns plus a pointer back to the row, trading disk space and write cost for read speed.
Without an index, checking “does this value already exist?” would mean scanning the whole table on every insert, so PRIMARY KEY and UNIQUE always come with one. Foreign keys differ: InnoDB creates an index on the child column automatically, PostgreSQL doesn’t.
2. B-trees and B+trees
Key idea: databases use B+trees: internal nodes hold only separator keys, data lives only in the leaves, and the leaves form a linked list. That keeps the tree very short and turns a range scan into a sideways walk.
- B-tree: a balanced multi-way search tree, all leaves at the same depth, a node with k children holds k−1 sorted keys, search/insert/delete are O(log n). Every node carries data.
- B+tree (InnoDB, PostgreSQL, SQL Server, Oracle): only the leaves carry data, or row pointers.
flowchart TB
R["Internal: 30 | 90"] --> A["Internal: 8"]
R --> B["Internal: 40"]
R --> C["Internal: 99"]
A --> L1["Leaf: 1"]
A --> L2["Leaf: 8, 20"]
B --> L3["Leaf: 30"]
B --> L4["Leaf: 40, 44"]
C --> L5["Leaf: 90"]
C --> L6["Leaf: 99, 150"]
L1 -.-> L2 -.-> L3 -.-> L4 -.-> L5 -.-> L6
| B-tree | B+tree | |
|---|---|---|
| Data | In every node | Only in leaves |
| Single-key lookup | May stop early | Always reaches a leaf, uniform cost |
Range, ORDER BY |
Walks up and down the tree | Walks sideways along the leaves |
| Internal fan-out | Small (nodes also carry data) | Large (keys only) |
Fan-out is the number of children per node. A node is a page (the database’s unit of I/O: 16 KB in InnoDB, 8 KB in PostgreSQL). The upper levels almost always sit in RAM, so a lookup usually costs a single disk read, at the leaf.
Doing the height math: InnoDB and PostgreSQL
- InnoDB,
BIGINTPK: an internal entry is about 8 bytes of key plus a 6-byte page number, so roughly 1,170 pointers per page. With ~1 KB rows a leaf holds ~15 rows. Three levels: 1,170 × 1,170 × 15 ≈ 20 million rows. - PostgreSQL, measured in section 5: a
bigintPK index on 1 million rows has 2,733 leaf pages (~366 entries per leaf) andtree_level = 2, meaning root, one internal level, then leaves.
3. Clustered indexes and heaps
Key idea: InnoDB stores the whole row in the leaves of the PK tree (the clustered index), and secondary indexes point back by PK. PostgreSQL stores rows in a heap, and every index points straight at a physical location (TID).
InnoDB: the table is the clustered index. The table is a B+tree ordered by the PK, with whole rows in its leaves. A secondary index stores the column value plus the PK value in its leaves, so reading through a secondary index means walking two trees.
flowchart LR
Q["WHERE email = ?"] --> S["Secondary index on email: leaves hold email and PK"]
S -->|"PK = 4791"| C["Clustered index on PK: leaves hold the full row"]
C --> R["Full row"]
PostgreSQL: the table is a heap (rows sit in insertion order, unsorted). Every index, the PK included, stores a TID (page number + slot) in its leaves: one tree walk, then a direct jump into the heap. CLUSTER only reorders the table once; it isn’t maintained.
Why does InnoDB store the PK instead of an address? Row locations move constantly (page splits, merges, rebuilds); storing the PK means a moved row never forces secondary index updates.
PostgreSQL pays on the write side: with MVCC (keeping several versions of a row), every UPDATE writes a new row version at a new TID, so every index needs a new entry, even indexes on columns that didn’t change. The escape hatch is the HOT update (heap-only tuple): if the update touches no indexed column and the page has free space, the new version stays on the same page and no index is touched.
fillfactor is the percentage of a page filled on write, the rest kept for updates (PostgreSQL defaults to 100 for tables and 90 for B-trees; lower it to 80–90 on update-heavy tables). Full pages can’t do HOT; touching an indexed column is never HOT.
HOT update lab: fillfactor and indexed columns
A 100,000-row table with an index on status, updating 50,000 rows:
| Table | Column updated | fillfactor |
HOT updates |
|---|---|---|---|
h100 |
note (not indexed) |
100 | 0 / 50,000 |
h80a |
note (not indexed) |
80 | 12,506 / 50,000 |
h80b |
status (indexed) |
80 | 0 / 50,000 |
Leaving 20% free got 25% HOT: updating consecutive rows used up each page’s free space; scattered updates with autovacuum cleaning up do much better.
4. Unique indexes and NULL
Key idea: in standard SQL, NULL is not equal to NULL, so a UNIQUE column usually allows many NULLs. To forbid that, you have to say so explicitly.
| Database | Multiple NULLs in a UNIQUE column |
|---|---|
| MySQL InnoDB | Allowed (verified: two email = NULL rows insert fine) |
| PostgreSQL | Allowed, unless you declare NULLS NOT DISTINCT (15+) |
| SQL Server | Only one NULL; for more, use a filtered index WHERE col IS NOT NULL |
CREATE UNIQUE INDEX acc_email ON acc (email); -- many NULLs allowed
CREATE UNIQUE INDEX acc_phone ON acc (phone) NULLS NOT DISTINCT; -- one NULL only
INSERT INTO acc VALUES (1, NULL, NULL), (2, NULL, '1'); -- OK
INSERT INTO acc VALUES (3, NULL, NULL);
-- ERROR: duplicate key value violates unique constraint "acc_phone"
The slides recommend NOT NULL indexed columns because NULLs “take space”. The space part is negligible (a NULL is one bit in the null bitmap); the real reason is semantics: NOT IN against a subquery containing NULL returns nothing, and unique indexes allow many NULLs.
5. Choosing a primary key: bigint, UUIDv4 or UUIDv7
Key idea: increasing keys append to the end of the tree, so pages stay full; random keys insert in the middle, so pages keep splitting in half. UUIDv7 is nearly increasing, so it stays almost as compact as bigint.
- Increasing keys always insert into the rightmost leaf: when a page fills up, a new one is started and the old one stays full.
- Random keys insert in the middle of the tree: full pages get split in half (page split), each half ~50% full, scattered across RAM and disk.
Lab results, 1 million rows per table:
bigint |
UUIDv4 / random | UUIDv7 / time-ordered | |
|---|---|---|---|
| PostgreSQL: PK size | 21 MB | 38 MB | 30 MB |
| PostgreSQL: WAL for 200,000 inserts | 27 MB | 60 MB | 30 MB |
| InnoDB: clustered index | 41 MB | 80 MB | 50 MB |
In InnoDB the secondary email index grows with the PK too (62 MB vs 48 MB) even though nobody touched it, because secondary leaves carry a copy of the PK.
Page split measurements on PostgreSQL 16 and MySQL 8.4, plus a UUIDv7 generator in Java 21
PostgreSQL 16 lab, 1 million rows per table. UUIDv7 is hand-rolled in PL/pgSQL (48 bits of milliseconds + 12 bits of sub-millisecond fraction + random bits, like PostgreSQL 18’s uuidv7()):
| Primary key | PK size | Leaf density | leaf_fragmentation |
WAL for 200,000 more inserts |
|---|---|---|---|---|
bigint identity |
21 MB | 90% | 0 | 27 MB |
UUIDv4 (gen_random_uuid()) |
38 MB | 71% | 50% | 60 MB |
| UUIDv7 | 30 MB | 90% | 0 | 30 MB |
InnoDB lab on MySQL 8.4, 1 million rows, plus a secondary index on email:
| Primary key | Clustered index | Secondary on email |
Insert time |
|---|---|---|---|
BIGINT AUTO_INCREMENT |
41 MB | 48 MB | 2.7 s |
random BINARY(16) (v4-style) |
80 MB | 62 MB | 4.4 s |
UUID_TO_BIN(UUID(), 1) (time-ordered) |
50 MB | 62 MB | 2.7 s |
UUIDv7 insert time on PostgreSQL was dominated by the hand-written PL/pgSQL function, so it’s left out.
A minimal UUIDv7 generator in Java 21, with a 12-bit counter to keep order within the same millisecond:
import java.security.SecureRandom;
import java.util.UUID;
import java.util.concurrent.locks.ReentrantLock;
public final class UuidV7 {
private static final SecureRandom RANDOM = new SecureRandom();
private static final ReentrantLock LOCK = new ReentrantLock();
private static long lastMillis = -1;
private static int counter; // 12 bits in the rand_a field
public static UUID next() {
long millis; int seq;
LOCK.lock();
try {
millis = System.currentTimeMillis();
if (millis <= lastMillis) { // same millisecond or clock went back
millis = lastMillis;
if (++counter > 0xFFF) { millis = ++lastMillis; counter = 0; }
} else {
lastMillis = millis;
counter = RANDOM.nextInt(0x400); // random start, leaves room to grow
}
seq = counter;
} finally {
LOCK.unlock();
}
long msb = (millis << 16) | 0x7000L | seq; // 48-bit time | version 7 | 12-bit counter
long lsb = (RANDOM.nextLong() & 0x3FFFFFFFFFFFFFFFL) | 0x8000000000000000L; // variant
return new UUID(msb, lsb);
}
}
On JDK 21: 1 million IDs in ~160 ms, with the top 64 bits strictly increasing (compared unsigned). ReentrantLock avoids pinning virtual threads (sticking them to an OS thread). In production, use a well-tested library.
6. Composite indexes with range predicates
Key idea: without the leading column a composite index usually can’t be used, except via skip scan. A range on the leading column means the next column only positions the starting point and doesn’t narrow the scan, even when the plan names it.
“You must have the leading column” is no longer absolute. The slides conclude that an index on (country, province, name) can’t serve a query filtering only on province. But MySQL 8.0.13+ and PostgreSQL 18 have skip scan: when the leading column has few distinct values (like country), the database hops through each leading value and seeks the second column within each group. MySQL’s skip scan requires the index to cover every column read; PostgreSQL 16 doesn’t have it.
A range on the leading column (the slide quiz). With an index on (a, b): how many columns do a > 1 AND b = 2, a >= 1 AND b = 2 and a BETWEEN 2 AND 8 AND b = 2 use? The slides answer (a), (a, b), (a, b). Measured: a >= 97 AND b = 2 shows key_len = 8 but still scans ~63,000 entries; only a IN (97, 98, 99) AND b = 2 narrows it to 30. Look at the scanned range in EXPLAIN FORMAT=TREE.
Measured on MySQL 8.4: skip scan, the range quiz and the key_len trap
MySQL 8.4, 1 million rows, index (a, b), a has 100 values:
EXPLAIN ANALYZE SELECT a, b, id FROM t WHERE b = 2;
-> Covering index skip scan on t using idx_ab over b = 2
(actual time=0.016..0.391 rows=1000 loops=1)
SELECT * ... WHERE b = 2 still scans the whole table. PostgreSQL 16: Parallel Seq Scan, 18 ms; the PostgreSQL 18 behaviour couldn’t be run in this lab.
The range quiz, with constants changed so the range is narrow enough to be chosen (with a > 1 on data where a runs 0–99, the range covers 98% of the table and the optimizer scans the table):
| Predicate | key_len |
Scanned range (EXPLAIN FORMAT=TREE) |
Estimated entries scanned |
|---|---|---|---|
a > 97 AND b = 2 |
4 | (97 < a) |
37,722 |
a >= 97 AND b = 2 |
8 | (97 <= a AND 2 <= b) |
62,908 |
a BETWEEN 97 AND 99 AND b = 2 |
8 | (97 <= a <= 99 AND b = 2) |
38,702 |
a IN (97, 98, 99) AND b = 2 |
8 | three ranges (a = 97 AND b = 2), … |
30 |
The slides also advise putting high-cardinality columns (many distinct values) first because “the tree gets more branches”. That’s wrong: B+tree height depends on the number of entries and the key length, not on column order (the correct rule is in step 5 of the index lab). Switching to (name, province, country) would also break WHERE country = 'US'.
7. Index maintenance
Key idea: an index doesn’t get unbalanced, it bloats, so measure before you rebuild. To build an index on a live table, use the online method and watch for INVALID indexes and the metadata lock.
7.1. B+trees don’t get unbalanced, they bloat
The slides say “a B+tree may become unbalanced over time, so rebuild it”. B+trees are always balanced by the way splits and merges work. What degrades is page density (bloat: pages with lots of free space that’s never reclaimed) and fragmentation.
Example: delete 90% of the rows and VACUUM, and the index is still 21 MB at 9% leaf density; REINDEX INDEX CONCURRENTLY brings it to 2.2 MB. Measure with pgstatindex() and rebuild when density stays low (MySQL: OPTIMIZE TABLE), not on a calendar.
Bloat lab: delete 90%, VACUUM, REINDEX, and measuring with pgstatindex
PostgreSQL, a bigint PK index on 1 million rows, delete 90%, then VACUUM:
| State | tree_level |
Leaf pages | Leaf density | Size |
|---|---|---|---|---|
| Freshly built | 2 | 2,733 | 90% | 21 MB |
After 90% DELETE + VACUUM |
2 | 2,733 | 9% | 21 MB |
After REINDEX INDEX CONCURRENTLY |
1 | 274 | 90% | 2.2 MB |
7.2. Building an index on a live table
- PostgreSQL: a plain
CREATE INDEXblocks all writes for the whole build. In production useCREATE INDEX CONCURRENTLY: no write block, but two table scans, no transaction block, and it waits for open transactions. - MySQL 5.6+:
ALTER TABLE t ADD INDEX idx (col), ALGORITHM=INPLACE, LOCK=NONE. Before 5.6 you usedpt-online-schema-change(shadow table + triggers) orgh-ost(binlog-based).ALTERalgorithms and expand/contract are covered in the database basics post.
7.3. Unused indexes, prefix indexes, and when not to index
Don’t index: tiny tables; evenly distributed low-cardinality columns (unless you look up a rare value, then use a partial index); write-mostly tables such as raw logs; columns that never appear in WHERE, JOIN, ORDER BY or GROUP BY. Unused indexes: measure before you drop.
Finding unused indexes, prefix indexes and index merge for OR
- Unused indexes: find them with
pg_stat_user_indexes(idx_scan = 0) orsys.schema_unused_indexes(MySQL 8). Before dropping one, make sure the stats cover a long enough period and the index doesn’t back a unique/foreign key or serve a replica. MySQL 8 has invisible indexes to switch one off as a trial. - MySQL prefix indexes (
INDEX (email(12))) are smaller but can’t cover a query, can’t serveORDER BYon the full column, and aUNIQUEprefix treats two strings sharing the first 12 characters as duplicates. PostgreSQL has no prefix indexes; use an expression index on(left(email, 12)).
Exercises
Exercise 1: Verify three claims from this post
Task (paraphrased): pick three claims about indexes; for each, give the statement, the SQL that tests it, the real result and an explanation.
Solution to Exercise 1: covering index, skip scan, implicit casts
Claim 1: reading through a secondary index needs an extra step to fetch the row, and a covering index removes it. PostgreSQL 16, table t(id, a, b, c) with 1 million rows, index (a, b):
EXPLAIN (ANALYZE, BUFFERS) SELECT c FROM t WHERE a = 5 AND b BETWEEN 1 AND 50;
-- Bitmap Heap Scan, rows=500, Heap Blocks: exact=275, Buffers: 279
EXPLAIN (ANALYZE, BUFFERS) SELECT a, b FROM t WHERE a = 5 AND b BETWEEN 1 AND 50;
-- Index Only Scan using idx_ab, Heap Fetches: 0, Buffers: 5
CREATE INDEX idx_ab_inc ON t (a, b) INCLUDE (c);
-- first query again: Index Only Scan using idx_ab_inc, Buffers: 6
Needing column c means visiting 275 heap pages (the 500 rows are scattered); with every column in the index it’s 5–6 pages.
Claim 2: without the leading column a composite index is unusable, except via skip scan. MySQL 8.4: SELECT a, b, id ... WHERE b = 2 runs a covering index skip scan in 0.4 ms; SELECT * ... WHERE b = 2 is type: ALL over 998,360 rows because skip scan requires a covering index. PostgreSQL 16: Seq Scan for both.
Claim 3: implicit casts and functions on the column disable the index. MySQL 8.4, table u with 1 million rows, indexed code VARCHAR(20), id INT primary key:
| Query | Plan | Time |
|---|---|---|
WHERE id = '500' (numeric column, string literal) |
PK lookup | ~0.04 ms |
WHERE code = '00000500' |
Index lookup ... idx_code |
~0.006 ms |
WHERE code = 500 (string column, numeric literal) |
Table scan |
~114 ms |
WHERE LENGTH(name) = 6 |
Table scan |
~102 ms |
WHERE id + 1 = 501 |
Table scan |
~106 ms |
Comparing a string column to a number makes MySQL convert every column value to a number, so an index sorted as strings is useless; a numeric column compared to a string literal only converts the literal once. code = 500 is also semantically wrong: '500', '0500' and '500abc' all equal the number 500. Functions and arithmetic on the column fail the same way because the index stores raw values.
Exercise 2: Choose a primary key for an orders table
Task (my own): an order service on PostgreSQL, 5 million orders a month, a mobile app that creates orders offline and syncs later (IDs generated on the client), and IDs that appear in public URLs.
Solution to Exercise 2: UUIDv7 as the PK
- Rule out
bigintas the only ID: clients can’t generate it upfront, and it leaks order volume. - Rule out UUIDv4: the table will reach hundreds of millions of rows; the lab showed an ~80% larger index and double the WAL.
- Pick UUIDv7 as the PK: clients can generate it, the index stays compact (30 MB, 90% leaf density), and the next ID can’t be guessed. Accept that it reveals creation time (orders already have
created_at). Store it asuuid.
When the table grows and old data must go, see partitioning and deleting old data safely.
The slide’s range quiz on composite indexes is solved in section 6.
Remember
- Explain why databases use B+trees, and why the tree is only 3 levels tall.
- Draw the read path through a secondary index in InnoDB and in PostgreSQL, and name each side’s write cost.
- Know why a UUIDv4 PK is slow, and when to pick
bigint, UUIDv7 or Snowflake. - Read the plan for
(a, b)with a range ona: doesbreally narrow the scan? - Measure bloat before rebuilding, and know the two traps of building an index online.
Interview questions
Junior
What’s the difference between a key and an index?
A key is a data constraint (PK, unique, foreign key); an index is a data structure for fast lookup.
The database enforces PK and UNIQUE with indexes. For foreign keys, InnoDB creates an index on the child column automatically, PostgreSQL doesn’t.
Why do databases use B+trees rather than binary trees or B-trees?
Because a B+tree is very short (fan-out in the thousands) and a range scan is just a sideways walk along the leaves.
Each node is a disk page. B+tree internal nodes hold only keys, so 20 million rows fit in 3 levels; linked leaves make range scans and ORDER BY a sideways walk. Binary trees are far too tall; B-trees carry data in internal nodes, so their fan-out is smaller.
Does a unique index allow multiple NULLs?
On MySQL and PostgreSQL, yes, because NULL isn’t equal to NULL. SQL Server allows one NULL.
PostgreSQL 15+ has NULLS NOT DISTINCT to treat NULLs as duplicates.
Mid
What’s a clustered index? Can InnoDB cluster on a column other than the primary key?
A clustered index has whole rows in its leaves and defines the physical order; one per table. InnoDB doesn’t let you choose.
InnoDB uses the PK; otherwise the first unique index with all columns NOT NULL; otherwise a hidden row id. SQL Server is the one that lets you cluster on a non-PK column. PostgreSQL uses a heap.
Why do InnoDB secondary indexes store the primary key rather than the row address?
Because row locations change on page splits, merges and rebuilds; storing the PK means moving a row never forces secondary index updates.
The cost is a second lookup into the clustered index, and a fat PK makes every secondary index fat.
What is a HOT update in PostgreSQL, and how do you get more of them?
If an update changes no indexed column and the page has room, the new version stays on the same page and no index gets a new entry.
To get more: lower the table fillfactor, don’t index frequently changing columns, keep autovacuum fast enough. Track n_tup_hot_upd in pg_stat_user_tables.
With an index on (a, b), can WHERE b = ? use the index?
Usually not, because the leading column is missing; the exception is skip scan when a has few values.
Skip scan exists in MySQL 8.0.13+ and PostgreSQL 18; MySQL also requires a covering index. If WHERE b = ? is a main query, create an index that starts with b instead of relying on skip scan.
Senior
Why is a UUIDv4 primary key slow, and what would you use instead?
Random keys insert into the middle of the tree, causing page splits and a bigger, fragmented index. Use bigint if the database assigns IDs, UUIDv7/ULID/Snowflake if they’re generated in a distributed way.
Once the index outgrows RAM, every insert also costs a random read. On 1 million rows: an 80 MB InnoDB clustered index vs 41 MB for bigint; PostgreSQL writes twice the WAL of UUIDv7.
How do the InnoDB and PostgreSQL storage models affect index design?
InnoDB needs a short, increasing PK; PostgreSQL needs few indexes on update-heavy tables.
- InnoDB: secondaries store the PK, reads cost two tree walks; updating non-indexed columns touches no index.
- PostgreSQL: indexes point to TIDs, reads cost one tree walk, but non-HOT updates add an entry to every index. Update-heavy tables need few indexes, a lower
fillfactorand a well-tuned autovacuum.
Should you rebuild indexes regularly because B+trees become unbalanced?
No. B+trees are always balanced; what degrades is bloat after mass deletes or updates.
Measure with pgstatindex, rebuild deliberately with REINDEX CONCURRENTLY or OPTIMIZE TABLE. If bloat keeps coming back from time-based deletes, partition instead.
How would you add a unique index to a 200-million-row production table?
Clean up duplicates first, then build the index online (CONCURRENTLY or LOCK=NONE/gh-ost), verify the result, and run it off-peak.
- Clean up duplicates:
GROUP BY ... HAVING count(*) > 1. - PostgreSQL:
CREATE UNIQUE INDEX CONCURRENTLY, watchpg_stat_progress_create_index, checkindisvalid, thenADD CONSTRAINT ... UNIQUE USING INDEX. - MySQL:
ALGORITHM=INPLACE, LOCK=NONEwith a smalllock_wait_timeout, or gh-ost; check for long transactions first. - Watch replication lag.
Useful phrases for interviews
- “Internal nodes only hold keys, so the fan-out is over a thousand and twenty million rows fit in three levels.”
- “In InnoDB the table is the clustered index, so every secondary index carries a copy of the primary key.”
- “Postgres pays on the write side: a non-HOT update has to touch every index on the table.”
- “We lowered the fillfactor to leave room for HOT updates on that hot table.”
- “Random UUIDs split pages all over the tree; a time-ordered UUIDv7 keeps inserts on the rightmost leaf.”
- “The tree wasn’t unbalanced, it was bloated; leaf density was down to nine percent.”
- “
key_lensays both columns, but the second one only positions the start of the range.” - “Comparing a varchar column to a number forces an implicit conversion on every row, so the index is useless.”
- “Before an online DDL I check for long-running transactions, otherwise the metadata lock queues every query.”
Notes based on the Advanced Backend course (Ronin Engineer), rewritten in my own words.