Radim Marek: B-tree pages, sorted and sparse

So far, the storage internals series has focused on heap pages. We began by opening the 8KB page, then traced MVCC visibility through xmin, xmax, and snapshots. Next we observed HOT updates evade index maintenance, and finally tracked VACUUM as it went through its phases. Each time an index came up, the explanation stopped at either "the index points to the heap via ctid" or "index cleanup removes the dead entries". This chapter is about what lies at the other end of that pointer.

B-tree pages use the same 8KB skeleton (24-byte header, line pointers, tuples packed from the bottom up), but where a heap page is an unordered bag of row versions, a B-tree page is sorted and linked to its siblings at the same level. VACUUM cannot undo index bloat for that reason; the operational side of this issue is covered in VACUUM Is a Lie. Index bloat is a recurring topic and source of question during my talk "Postgres Storage Internals Visualized", and this is my attempt to address it better.

Setup

We need pageinspect for reading raw B-tree pages and pgstattuple for index-level statistics. By default, both require a superuser, but on managed instance, only pgstattuple can be granted because pageinspect checks for a superuser inside every function. All of the following was captured on PostgreSQL 18.6 (the postgres:18 image) in a single session; page numbers and item counts are from that run.

CREATE EXTENSION IF NOT EXISTS pageinspect; CREATE EXTENSION IF NOT EXISTS pgstattuple;  CREATE TABLE idx_demo (  id integer GENERATED ALWAYS AS IDENTITY PRIMARY KEY,  value integer NOT NULL );  INSERT INTO idx_demo (value) SELECT (i * 7919) % 100003 FROM generate_series(1, 100000) AS i;  CREATE INDEX idx_demo_value ON idx_demo (value);

value holds each number only once, in no particular order: 100003 is a prime number, so multiplying by 7919 never gives the same remainder twice and all 100,000 values are distinct, resulting in a jumbled order like unique integer key would have.

SELECT count(DISTINCT value), min(value), max(value) FROM idx_demo;

 count | min | max --------+-----+--------  100000 | 1 | 100002 (1 row)

Delete 80% and VACUUM

Measure the index, delete 80% of the rows and run a VACUUM. Then measure again.

SELECT pg_relation_size('idx_demo') AS heap_size,  pg_relation_size('idx_demo_value') AS index_size;  SELECT * FROM pgstatindex('idx_demo_value');

 heap_size | index_size -----------+------------  3629056 | 2260992 (1 row)   version | tree_level | index_size | root_block_no | internal_pages | leaf_pages | empty_pages | deleted_pages | avg_leaf_density | leaf_fragmentation ---------+------------+------------+---------------+----------------+------------+-------------+---------------+------------------+--------------------  4 | 1 | 2260992 | 3 | 1 | 274 | 0 | 0 | 89.78 | 0 (1 row)

The index is 276 pages: the metapage, the root, and 274 leaves.

DELETE FROM idx_demo WHERE id % 5 != 0;

DELETE 80000

The heap now contains 80,000 dead tuples and the index contains 80,000 entries that point to them. At the moment of deletion, nothing in the index changes: a DELETE operation stamps xmax on the heap tuple and never touches the index.

VACUUM (VERBOSE) idx_demo;

INFO: finished vacuuming "postgres.public.idx_demo": index scans: 1 pages: 0 removed, 443 remain, 443 scanned (100.00% of total), 0 eagerly scanned tuples: 80000 removed, 20000 remain, 0 are dead but not yet removable ... index scan needed: 443 pages from table (100.00% of total) had 80000 dead item identifiers removed index "idx_demo_pkey": pages: 276 in total, 0 newly deleted, 0 currently deleted, 0 reusable index "idx_demo_value": pages: 276 in total, 0 newly deleted, 0 currently deleted, 0 reusable

This is phase 2 from VACUUM at the Page Level: a single pass over every index to remove each entry whose TID is in the dead list. The per-index lines count pages.

SELECT pg_relation_size('idx_demo') AS heap_size,  pg_relation_size('idx_demo_value') AS index_size;  SELECT * FROM pgstatindex('idx_demo_value');

 heap_size | index_size -----------+------------  3629056 | 2260992 (1 row)   version | tree_level | index_size | root_block_no | internal_pages | leaf_pages | empty_pages | deleted_pages | avg_leaf_density | leaf_fragmentation ---------+------------+------------+---------------+----------------+------------+-------------+---------------+------------------+--------------------  4 | 1 | 2260992 | 3 | 1 | 274 | 0 | 0 | 18.15 | 0 (1 row)

VACUUM removed the dead entries and left the pages where they were. The heap is the same size as well, but the free space inside a heap page and the free space inside a leaf page do not behave in the same way.

One leaf, before and after

Page 1 is the leftmost leaf. This is how it looked before the DELETE:

SELECT blkno, live_items, dead_items, free_size FROM bt_page_stats('idx_demo_value', 1);

 blkno | live_items | dead_items | free_size -------+------------+------------+-----------  1 | 367 | 0 | 808 (1 row)

808 bytes is about 10% of the page: CREATE INDEX fills each leaf to 90% and leaves the rest for later inserts.

SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('idx_demo_value', 1) LIMIT 10;

 itemoffset | ctid | itemlen | data ------------+-----------+---------+-------------------------  1 | (288,1) | 16 | 6f 01 00 00 00 00 00 00  2 | (209,84) | 16 | 01 00 00 00 00 00 00 00  3 | (418,168) | 16 | 02 00 00 00 00 00 00 00  4 | (185,141) | 16 | 03 00 00 00 00 00 00 00  5 | (394,225) | 16 | 04 00 00 00 00 00 00 00  6 | (161,198) | 16 | 05 00 00 00 00 00 00 00  7 | (371,56) | 16 | 06 00 00 00 00 00 00 00  8 | (138,29) | 16 | 07 00 00 00 00 00 00 00  9 | (347,113) | 16 | 08 00 00 00 00 00 00 00  10 | (114,86) | 16 | 09 00 00 00 00 00 00 00 (10 rows)

From item 2 onwards, each entry is a key and a pointer to a row in the heap. The first four bytes of data are the key: 01 00 00 00 is 1, 02 00 00 00 is 2, and so on up the page. The other four are padding, because every item is rounded up to a multiple of 8 bytes. The ctid says where the row lives, so (209,84) means line pointer 84 on heap page 209. That is all an entry holds. There is no xmin or xmax here, because the index knows nothing about visibility and leaves it to the heap.

Item 1 is the odd one out. Its key is 6f 01, which is 367, larger than every other key on the page, and yet it comes first. This is the high key, and there is no row behind it. It marks the upper limit of the page: everything on page 1 is below 367, and 367 itself is the first entry on page 2.

SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('idx_demo_value', 2) LIMIT 3;

 itemoffset | ctid | itemlen | data ------------+----------+---------+-------------------------  1 | (367,1) | 16 | dd 02 00 00 00 00 00 00  2 | (288,99) | 16 | 6f 01 00 00 00 00 00 00  3 | (55,72) | 16 | 70 01 00 00 00 00 00 00 (3 rows)

Page 2 starts with a high key of its own, dd 02 or 733, followed by the real entry for 367. So a leaf has 366 entries and one high key, and the high key says where the leaf ends.

The same page after the DELETE and the VACUUM:

SELECT blkno, live_items, dead_items, free_size FROM bt_page_stats('idx_demo_value', 1);  SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('idx_demo_value', 1) LIMIT 6;

 blkno | live_items | dead_items | free_size -------+------------+------------+-----------  1 | 72 | 0 | 6708 (1 row)   itemoffset | ctid | itemlen | data ------------+-----------+---------+-------------------------  1 | (288,1) | 16 | 6f 01 00 00 00 00 00 00  2 | (347,113) | 16 | 08 00 00 00 00 00 00 00  3 | (114,86) | 16 | 09 00 00 00 00 00 00 00  4 | (228,172) | 16 | 12 00 00 00 00 00 00 00  5 | (343,32) | 16 | 1b 00 00 00 00 00 00 00  6 | (110,5) | 16 | 1c 00 00 00 00 00 00 00 (6 rows)

The high key has not moved. The page still owns every key below 367 and just holds a fifth of the entries it had.

Which leaf a key belongs to

The level above the leaves is built from the high keys. Here is the whole index as it was first built, drawn from its page dumps.

Each leaf holds one unbroken run of keys. Block 1 has every key below 367, block 2 has the keys from 367 up to 733, and so on. The root, block 3, is the list of where each run starts:

SELECT itemoffset, ctid, itemlen, data FROM bt_page_items('idx_demo_value', 3) LIMIT 5;

 itemoffset | ctid | itemlen | data ------------+-------+---------+-------------------------  1 | (1,0) | 8 |  2 | (2,1) | 16 | 6f 01 00 00 00 00 00 00  3 | (4,1) | 16 | dd 02 00 00 00 00 00 00  4 | (5,1) | 16 | 4b 04 00 00 00 00 00 00  5 | (6,1) | 16 | b9 05 00 00 00 00 00 00 (5 rows)

Here the block number in the ctid is a leaf, not a heap page. Item 2 says that the keys from 367 upwards are on block 2, and item 3 that the keys from 733 upwards are on block 4. Item 1 has no key and takes everything below 367. The root has 274 items like these, one for each leaf.

The root is found through page 0, the metapage. It is not part of the tree and only records where the root is (block 3) and how many levels sit above the leaves (one).

A lookup for value = 5 starts at the root, finds that 5 falls under item 1, goes to block 1 and searches the entries there. That is two index pages and then the heap. A range scan such as WHERE value BETWEEN 100 AND 500 finds its first leaf in the same way and then follows btpo_next, the link each leaf keeps to its right-hand neighbour, without going back up.

An INSERT goes down the tree in exactly the same way to find its page. So a new key has one leaf it can go to, the one whose range contains it, however much room the other leaves have.

Where new keys go

A heap page with space can accept any new row, so the next 80,000 inserts will refill the heap without extending it. However, leaf page with room only accepts the keys that sort into its range. Page 1 will only accept new values between 1 and 366, so unless the workload re-inserts the same key ranges that were deleted, the 6,708 bytes will remain free.

First, put back 40,000 of the deleted values. These sort into ranges that the existing leaves still own.

INSERT INTO idx_demo (value) SELECT (i * 7919) % 100003 FROM generate_series(1, 100000) AS i WHERE i % 5 IN (1, 2);  SELECT * FROM pgstatindex('idx_demo_value');

INSERT 0 40000   version | tree_level | index_size | root_block_no | internal_pages | leaf_pages | empty_pages | deleted_pages | avg_leaf_density | leaf_fragmentation ---------+------------+------------+---------------+----------------+------------+-------------+---------------+------------------+--------------------  4 | 1 | 2260992 | 3 | 1 | 274 | 0 | 0 | 53.97 | 0 (1 row)

The entries went into the space that VACUUM had left behind.

Next, 40,000 values that are all higher than anything the index has seen, in the same way that a sequence or a timestamp would produce them.

INSERT INTO idx_demo (value) SELECT 100003 + i FROM generate_series(1, 40000) AS i;  SELECT pg_relation_size('idx_demo') AS heap_size,  pg_relation_size('idx_demo_value') AS index_size;  SELECT * FROM pgstatindex('idx_demo_value');

INSERT 0 40000   heap_size | index_size -----------+------------  3629056 | 3153920 (1 row)   version | tree_level | index_size | root_block_no | internal_pages | leaf_pages | empty_pages | deleted_pages | avg_leaf_density | leaf_fragmentation ---------+------------+------------+---------------+----------------+------------+-------------+---------------+------------------+--------------------  4 | 1 | 3153920 | 3 | 1 | 383 | 0 | 0 | 64.3 | 0 (1 row)

The table is back to 100,000 rows and the heap is still the 443 pages it started with, because all 80,000 inserts went into the space freed by VACUUM. The index has grown from 276 pages to 385. Every one of the new keys sorts above 100002, so they all belonged to the rightmost leaf, and the 273 leaves to its left could not take any of them, even though they were half empty.

I first tried this with 60,000 rows, which was enough to split the root and add a third level to the tree, so the numbers here use 40,000 to keep it at two.

What decides this is where the new keys fall, and that depends on the kind of key. A key that only ever goes up, such as an ID from a sequence or a creation time, always lands on the last leaf, so the gaps left behind are never filled. A key with no order to it, such as an email address or a random UUID, lands anywhere in the index, so the gaps fill up again over time.

When the leaf that a key belongs to is full, PostgreSQL performs a page split. It allocates a new page, moves about half of the entries to it, links it into the sibling chain and adds a downlink for it to the parent. The rightmost leaf is the exception: a split there leaves the old page 90% full and starts the new one nearly empty, which is how a sequential key, such as the primary key, keeps its pages full. The 109 new leaves are these splits, 366 keys at a time.

When a leaf empties completely

VACUUM's index cleanup removes dead entries and that's all it does to a leaf. It won't merge two half-empty siblings since this would involve moving entries between pages, rewriting the parent's downlinks and relinking the sibling chain, and nbtree implements none of that. B-tree files are never truncated either. The only other thing it can do is delete a page that has become completely empty by unlinking it from its siblings and removing its downlink from the parent.

The first DELETE never emptied a page, because its survivors were spread evenly across the leaves, with roughly 70 per leaf. A DELETE of a whole key range is different.

DELETE FROM idx_demo WHERE value BETWEEN 20000 AND 39999;  VACUUM (VERBOSE) idx_demo;

DELETE 12000  INFO: finished vacuuming "postgres.public.idx_demo": index scans: 1 ... index "idx_demo_pkey": pages: 496 in total, 0 newly deleted, 0 currently deleted, 0 reusable index "idx_demo_value": pages: 385 in total, 54 newly deleted, 54 currently deleted, 0 reusable

The primary key index has grown from 276 pages to 496 over the same inserts, for the same reason: its keys only ever go up.

SELECT blkno, type, live_items, free_size, btpo_prev, btpo_next, btpo_flags FROM bt_multi_page_stats('idx_demo_value', 1, -1) WHERE blkno IN (56, 57, 110, 111);

 blkno | type | live_items | free_size | btpo_prev | btpo_next | btpo_flags -------+------+------------+-----------+-----------+-----------+------------  56 | l | 139 | 5368 | 55 | 111 | 1  57 | d | 0 | 8140 | 56 | 58 | 261  110 | d | 0 | 8140 | 56 | 111 | 261  111 | l | 159 | 4968 | 56 | 112 | 1 (4 rows)

Block 56 is the last leaf below the deleted range and block 111 is the first one above it. They now link directly to each other, and the root has lost the 54 downlinks in between. Blocks 57 to 110 have the type d for deleted, where a leaf has l, and hold no entries, but they are still in the file, which is the same 385 pages as before. A deleted page keeps its link to the right so that a scan which was already on its way there can still move on.

The deleted pages are not reusable yet either, which is the 0 reusable in the VACUUM output. A deleted page is only handed back to the index once no scan can still be on its way to it. A second VACUUM straight afterwards still reported 0 reusable; it took one more transaction before the pages were released. Until then, the 54 pages wait in the file.

Rebuilding

Available since PostgreSQL 12, REINDEX CONCURRENTLY builds a fresh copy of the index next to the old one without blocking reads or writes and then swaps them.

REINDEX INDEX CONCURRENTLY idx_demo_value;  SELECT * FROM pgstatindex('idx_demo_value');

 version | tree_level | index_size | root_block_no | internal_pages | leaf_pages | empty_pages | deleted_pages | avg_leaf_density | leaf_fragmentation ---------+------------+------------+---------------+----------------+------------+-------------+---------------+------------------+--------------------  4 | 1 | 1990656 | 3 | 1 | 241 | 0 | 0 | 89.83 | 0 (1 row)

As it is a bulk build, the rebuild packs the leaves back to the fillfactor. The 88,000 rows that are left fit into 243 pages, down from 385.

The cost is disk space. The new index exists alongside the old one until the swap, so a rebuild requires space for the rebuilt index (i.e. the compacted size, not the bloated one), as well as space for the temporary sort required to build it. A plain REINDEX is faster, but it takes an ACCESS EXCLUSIVE lock on the index, which means that queries that would use it are blocked, as well as locking the table, which blocks writes for the duration. This is the trade-off made during a maintenance window. VACUUM FULL does the same for the heap and every index at once under an exclusive lock and is usually the wrong tool when the bloat is in one index.