Unique IDs and B-Tree Indexes

The choice of ID is not only an application decision. Almost every relational database stores its primary key in a B-tree index, and the kind of ID you insert decides how hard that index has to work. This topic explains why time-ordered IDs are kinder to a database than random ones, and how to change an ID scheme, or rebuild an index, on a live system without the application going down.

How a B-tree index stores IDs

A B-tree keeps keys in sorted order, split across fixed-size pages (typically 8 KB in PostgreSQL). A lookup walks from the top of the tree down to the one page that holds the key, which is why finding a row by its ID stays fast even with billions of rows.

When a new row is inserted, its ID must go into the page where it belongs in sorted order. If that page is full, the database splits it into two half-full pages. Where new IDs land therefore matters a great deal.

Time-ordered IDs versus random IDs

• Time-ordered IDs (auto-increment, Snowflake, UUIDv7) are always larger than the previous one, so every insert goes to the last page. That one page stays in memory, earlier pages fill up completely and are never touched again, and the index stays compact.
• Random IDs (UUID version 4) can belong anywhere in the sorted order. Each insert lands on an effectively random page, which must be read into memory if it is not there already, and full pages are split and left half empty. As the table grows, the index becomes larger than it needs to be, and inserts need far more memory and disk reads.

The UUID standard itself states the problem plainly. RFC 9562 explains that random UUIDs "have poor database-index locality", that "new values created in succession are not close to each other in the index", and that the effects on B-trees "can be dramatic". This was a main reason the standard added the time-ordered UUIDv7.

How much does it matter?

It depends on size. On a table with thousands or a few million rows, the whole index fits in memory and the difference is barely measurable. Systema itself uses random version 4 UUIDs for its primary keys, which is a perfectly reasonable choice at its current size. The effect becomes significant when an index grows larger than the memory available to cache it, typically tens or hundreds of millions of rows with heavy inserts.

So the practical rule is: for new large, insert-heavy tables, prefer time-ordered IDs (UUIDv7, or a Snowflake-style 64-bit ID). For an existing system, change only when measurements show the index is the problem.

Keeping an index healthy: rebuilding without downtime

Over time an index can become bloated with half-empty pages, especially after many random inserts or deletes. Rebuilding it packs the pages again. The catch is that a plain rebuild blocks writes: in PostgreSQL's words, "a standard index rebuild locks out writes (but not reads) on the table until it's done". On a busy table, that is an outage.

PostgreSQL offers a concurrent rebuild:

REINDEX INDEX CONCURRENTLY orders_pkey;

With CONCURRENTLY, PostgreSQL "will rebuild the index without taking any locks that prevent concurrent inserts, updates, or deletes on the table". The trade-offs, from the same documentation:

• It takes longer and does more work, because it must "perform two scans of the table for each index".
• If it fails, it can leave behind a new index marked invalid alongside the old one; drop the invalid one and run the command again.
• It cannot run inside a transaction block, and only one concurrent index build can run on a table at a time.

Because it still uses extra CPU and disk, schedule it for the quietest hours.

Changing the ID scheme on a live system

Switching a large table from random UUIDs to time-ordered IDs, or from 32-bit to 64-bit integers, cannot be done in one step without stopping the application. The safe pattern is expand, migrate, contract: add the new alongside the old, move gradually, and remove the old only at the end.

1. Back up. Take a full backup and confirm it can be restored. Every later step depends on having a way back.

2. Expand. Add the new column, allowed to be empty at first, and change the application so that every new row fills both the old and the new ID. Adding an empty column is a quick change in modern PostgreSQL.

3. Backfill. Fill the new column for existing rows in small batches, for example 10,000 rows at a time with a short pause between batches, during low-traffic hours. Small batches keep each transaction short so normal traffic is never blocked for long.

4. Index. Build the new index without blocking writes:

   CREATE INDEX CONCURRENTLY orders_new_id_idx ON orders (new_id);
   

   PostgreSQL documents that it "supports building indexes without locking out writes" in this mode, at the cost of two table scans and waiting for running transactions to finish.

5. Switch. Change the application to look up, join and sort by the new column. Keep writing both columns, so switching back is still possible if anything goes wrong.

6. Contract. Only after the new column has served production traffic safely for a while, stop writing the old one and drop it. This is the only step that cannot be undone, which is why it comes last.

Rules for the maintenance window

• Pick the quietest hours from your traffic graphs, and announce the window even if no downtime is expected.
• Set a lock timeout before schema changes (for example SET lock_timeout = '5s'; in PostgreSQL). If a change cannot get its lock quickly, it gives up instead of queueing behind long-running queries and blocking everyone else.
• Watch as you go: error rate, response times, replication lag and disk space. Pause the backfill if any of them move.
• Rehearse on a copy of production first, so the timings and any failures are known in advance.
• Keep the old path working until the new one is proven. Every step except the last should be reversible.

How to use this in an interview

When a design has a large, write-heavy table, mention that its primary key should be time-ordered (Snowflake or UUIDv7) to keep the B-tree index compact. If asked how to change something on a live database, describe expand, migrate, contract, with concurrent index builds and small batches during low traffic.

Implementing it in your project

• Check index health in PostgreSQL. The pgstattuple extension's pgstatindex('index_name') reports, among other things, how full the index's leaf pages are. Low density after heavy random inserts or deletes suggests a rebuild.
• Rebuild without blocking writes: REINDEX INDEX CONCURRENTLY index_name; in the quietest hours. Note that it cannot run inside a transaction, and many migration tools wrap each migration in one, so check your tool's option to run a migration outside a transaction.
• Create new indexes the same way: CREATE INDEX CONCURRENTLY, with SET lock_timeout = '5s'; first so a blocked change gives up instead of stalling other queries.
• Never edit an applied migration. For an ID change, write each expand, backfill and contract step as its own new migration, deployed separately, with the application change between them.
• Rehearse on a restored copy of the production database to learn how long each step takes.

---

Sources and credibility

Everything above is written from scratch; the quotes come from the sources below, attributed where used.

Primary (highest confidence)

• RFC 9562: Universally Unique IDentifiers (UUIDs), IETF, 2024, section 2.1. Source of the quotes on index locality and B-tree performance.
• REINDEX, PostgreSQL documentation. Source of the quotes on standard and concurrent rebuilds and their caveats.
• CREATE INDEX, PostgreSQL documentation, "Building Indexes Concurrently". Source of the quote on building indexes without locking out writes.

Method

• The expand, migrate, contract sequence is a widely used pattern for zero-downtime schema changes; the steps and the maintenance rules above are our own summary of it.

On copyright: the diagrams on this page were drawn for this article, and the explanations are original. Quoted phrases are short and attributed.