Skip to content
notes.vinhnq.com

Search

Database & ORMSenior27 min read

Inside an index: B-trees, B+trees, clustered tables, heaps and choosing a primary key

Review 22 cards
On this page

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, BIGINT PK: 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 bigint PK index on 1 million rows has 2,733 leaf pages (~366 entries per leaf) and tree_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 INDEX blocks all writes for the whole build. In production use CREATE 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 used pt-online-schema-change (shadow table + triggers) or gh-ost (binlog-based). ALTER algorithms 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) or sys.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 serve ORDER BY on the full column, and a UNIQUE prefix 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 bigint as 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 as uuid.

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 on a: does b really 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 fillfactor and 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, watch pg_stat_progress_create_index, check indisvalid, then ADD CONSTRAINT ... UNIQUE USING INDEX.
  • MySQL: ALGORITHM=INPLACE, LOCK=NONE with a small lock_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_len says 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.