UUID Index Bloat Explained: B-Trees, Page Splits, and What to Do About It

"Random UUIDs fragment your indexes" is repeated often enough to be common knowledge, but the mechanism — why a B-tree specifically suffers from random insert order, and what "bloat" concretely means in terms of pages, fill factor, and vacuum/rebuild cost — is usually skipped. This post goes through the B-tree mechanics directly, then covers the concrete mitigations with working code.

B-Tree Refresher: Why Insert Order Matters

A B-tree index stores keys in sorted order across a tree of fixed-size pages (8 KB in Postgres, 16 KB in InnoDB by default). Each leaf page holds many keys; when a page fills up and a new key needs to be inserted into it, the database performs a page split: it allocates a new page and moves roughly half the entries into it.

The cost of this depends entirely on where new keys land relative to existing ones:

• Sequential insert (e.g., BIGSERIAL): every new key is larger than every existing key. It's always appended to the rightmost leaf page. When that page fills, the split is a clean append of a new page at the end — no existing page has to be reorganized in the middle of the tree.
• Random insert (e.g., UUIDv4): every new key lands at a uniformly random position in the existing key range. Splits happen constantly, scattered across the entire tree, and — critically — pages that have already been split and partially filled get split again later, sometimes while still well under capacity.

Sequential inserts:  [1][2][3][4] -> [5] appended -> new page only at the tail
Random inserts:      [a][f][k][z] -> insert 'm' -> splits a page in the MIDDLE of the tree
                                   -> insert '3' -> splits ANOTHER page elsewhere

What "Bloat" Actually Means

The direct consequence of scattered splits is lower average page fill factor — pages end up half-full more often, because a split immediately after insertion leaves both resulting pages roughly 50% full instead of the ~90% a sequentially-filled page achieves before splitting. More pages holding the same number of keys means:

1. More total disk space for the same logical data (the "bloat").
2. Lower buffer cache hit rate, since the working set no longer fits as efficiently in memory — the same number of keys now spans more physical pages.
3. More I/O per range scan, since a scan touching N keys now touches more, less densely packed pages to get them.

Measuring Fill Factor Directly (Postgres)

CREATE EXTENSION IF NOT EXISTS pgstattuple;

SELECT
    avg_leaf_density,
    leaf_pages,
    empty_pages,
    deleted_pages
FROM pgstatindex('orders_pkey');

avg_leaf_density is the number to watch. A healthy, sequentially-built B-tree typically sits in the high 80s to low 90s (percent). A B-tree built from years of random UUIDv4 inserts commonly drops into the 60s or lower — meaning 30–40% of the index's allocated space holds no data at all, purely as a byproduct of split geometry.

Reproducing the Effect

CREATE TABLE bench_sequential (
    id BIGINT GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    payload TEXT DEFAULT 'x'
);

CREATE TABLE bench_random_uuid (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid(),
    payload TEXT DEFAULT 'x'
);

INSERT INTO bench_sequential (payload)
SELECT 'x' FROM generate_series(1, 3_000_000);

INSERT INTO bench_random_uuid (payload)
SELECT 'x' FROM generate_series(1, 3_000_000);

SELECT 'bench_sequential' AS tbl, avg_leaf_density, leaf_pages
FROM pgstatindex('bench_sequential_pkey')
UNION ALL
SELECT 'bench_random_uuid', avg_leaf_density, leaf_pages
FROM pgstatindex('bench_random_uuid_pkey');

Representative output:

The random-UUID index needs roughly 68% more leaf pages to store the same 3 million keys, purely due to the fill-factor effect — the keys themselves are the same width in this comparison (both fixed-length), so this gap is insertion-order geometry, not byte-size difference.

Why This Also Costs You on Reads, Not Just Storage

A common misconception is that this is purely a disk-space problem. It also degrades read performance for two reasons:

1. Range scans touch more pages. SELECT * FROM orders WHERE id BETWEEN 'a' AND 'b' (rare for UUIDs, but the mechanism generalizes to any range-bound query on a bloated index) has to traverse more, sparser pages to cover the same key range.
2. Buffer cache pressure increases across the whole database. Every extra, mostly-empty page competing for the buffer cache is a page not available for other tables' hot data. This is a system-wide cost, not one isolated to the bloated table.

What to Do About It

1. Switch to a Time-Ordered UUID (UUIDv7)

The most direct fix: stop generating random keys. UUIDv7 places a millisecond-resolution timestamp in the leading bits, making new values sort near each other in generation order — the same append-mostly pattern that makes sequential integers cheap.

-- Postgres 18+: native
SELECT uuidv7();

-- Earlier versions: via extension, or generate in the application

// .NET 9+ has Guid.CreateVersion7()
var id = Guid.CreateVersion7();

// Node.js: no built-in v7 as of writing; use a small, well-audited library
const { v7: uuidv7 } = require('uuid');
const id = uuidv7();

This doesn't reduce storage per key (still 16 bytes) but restores the sequential-insert page-fill pattern, closing most of the density gap measured above.

2. Rebuild the Index Periodically (Mitigation, Not a Fix)

If migrating key generation isn't immediately feasible, periodically rebuilding the index reclaims the wasted space — but doesn't stop it from re-accumulating, since new random inserts continue the same pattern.

-- Postgres: rebuild without holding a long exclusive lock
REINDEX INDEX CONCURRENTLY orders_pkey;

-- MySQL: OPTIMIZE TABLE rebuilds the clustered index (and all secondary indexes)
OPTIMIZE TABLE orders;

Treat this as maintenance, not a solution — scheduling REINDEX CONCURRENTLY on a cadence buys back space and density temporarily; it doesn't change the underlying insert pattern causing the bloat.

3. Use a Non-Clustered/Non-PK Design Where Random UUIDs Stay, But Off the Hot Path

If the UUID must remain random for a real reason (e.g., existing external references, security requirements against v7's timestamp leakage), one mitigation is to not cluster the table by it. This is Postgres's default behavior already (heap-organized, not clustered), so this concern is specific to MySQL/InnoDB:

-- Instead of using the random UUID as the clustered InnoDB primary key directly,
-- use a surrogate BIGINT as the clustered key and keep the UUID as a unique
-- secondary column for external reference.
CREATE TABLE orders (
    internal_id BIGINT AUTO_INCREMENT PRIMARY KEY,
    external_id BINARY(16) NOT NULL,
    tenant_id INT NOT NULL,
    UNIQUE KEY uq_external_id (external_id)
);

This keeps the clustered index sequential (cheap, dense) while still exposing a UUID as the externally-visible identifier. The tradeoff: joins and lookups by external_id now go through a secondary index lookup rather than being the primary access path, and the table carries two identifier columns instead of one.

4. Lower the Fillfactor Proactively (Postgres-Specific)

For tables that must use a random UUID as the primary key and can't switch strategies, deliberately reducing fillfactor leaves headroom in each page at build time, reducing (not eliminating) the frequency of splits on subsequent inserts:

CREATE TABLE orders (
    id UUID PRIMARY KEY DEFAULT gen_random_uuid()
) WITH (fillfactor = 70);

CREATE INDEX orders_pkey ON orders (id) WITH (fillfactor = 70);

This trades a known, fixed amount of extra space at creation time for fewer, less disruptive splits later — a deliberate version of the bloat you'd otherwise get by accident, sized to your workload rather than left to chance.

Comparison of Mitigations

Conclusion

Index bloat from random UUID primary keys isn't a vague performance folklore claim — it's a direct, measurable consequence of how B-trees split pages under non-sequential insert order, visible in avg_leaf_density and leaf page counts. The most effective fix is generational: switch to UUIDv7 (or an equivalent time-ordered scheme) so new keys append near the end of the tree, the same way sequential integers do. Where that isn't possible, REINDEX/OPTIMIZE TABLE on a schedule and a deliberately reduced fillfactor are legitimate mitigations — but they manage the symptom, not the cause, and the bloat will continue accumulating as long as key generation stays random.

---

Tools and Versions

Need some UUIDs for testing? Try our tools for generating UUIDv4   UUIDv7   ULID   NanoID and decoding validating.
For a detailed comparison of UUID versions, visit our Complete Guide to UUID Versions.