Many databases use B+tree indexes, but they all differ. It's a sorted structure. The leaf pages are logically sorted so that a specific key value belongs to one page. A lookup by value reaches a single leaf page and either directly finds an entry for that value or immediately knows there's no entry with that key. When a page becomes full, it is split into two pages, each covering its own dedicated range. To find the right page, an internal page holds the range of values for the pages below. This internal page can become full, and a new level is added above it. Finally, at the highest level, there's a single internal page that is the root. A lookup always starts at the root and goes down to the leaves, following the branches of internal pages. In a traditional B+tree lookup, the cost is proportional to the height of the tree because the search starts at the root and descends to a leaf:
- 1 page to read when all fits in one leaf that is also the root (0 levels of internal pages, total height is 1). With small keys, this level can typically index hundreds of rows.
- 2 pages to read when there's one root that can list all leaf pages (1 level of internal page, total height is 2). With small keys, this level can typically index tens or hundreds of thousands of rows.
- 3 pages to read when there's one level of branches under the root (so 2 levels of internal pages, total height is 3). With small keys, this level can typically index millions of rows.
This means that finding one key within ten million rows may require traversing 3 index pages, where most of them are probably in cache given the small number of branches compared to the leaves. For a given index size, whatever the value you are looking for, it's always the same number of pages to read because the index is balanced (the commonly accepted meaning of the B in B+tree). This property is maintained because any page can split, but only splitting the root adds another level.
I've described how the height of an index can increase, impacting the cost of the lookup, as data grows, but do you know if your database can reduce the height of the B+tree when data is deleted?
I've been working with Oracle Database for a long time, and the answer is easy: the height of the B+tree index never decreases, even if you delete all rows, even if you coalesce the index, even if you shrink the index, until you completely rebuild it. Then I worked with PostgreSQL, which is famous for index bloat, and realized that the effective B+tree height can decrease even without a rebuild.
Oracle Database: reclaim levels with rebuild
I created a table with five million rows and an index on the ID, using a random 16-byte UUID:
drop table if exists bloat;
create table bloat ( id raw(16) constraint bloat_pkey primary key);
insert into bloat select uuid() from xmltable('1 to 5000000');
commit;
exec dbms_stats.gather_table_stats(user,'bloat');
I collect statistics on the logical structure of the index:
analyze index bloat_pkey validate structure;
select height-1 blevel, blocks pages, lf_blks leaf_pages, br_blks internal_pages from index_stats;
The result shows two levels of branches, with 40 internal pages including the root. There's one root at level 0 and 39 branches at level 1, addressing 24837 leaves:
BLEVEL PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
2 25728 24837 40
This means that finding a key in the index requires reading 3 pages. I can verify this with the execution plan:
set linesize 200
alter session set statistics_level=all;
select * from bloat where id = uuid_to_raw('00000000000000000000000000000000');
select * from dbms_xplan.display_cursor(format=>'allstats last');
This confirms that three buffers were read before determining that the key does not exist:
PLAN_TABLE_OUTPUT
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
SQL_ID 7jxrrzwtd7aqd, child number 0
-------------------------------------
select * from bloat where id = uuid_to_raw('00000000000000000000000000000000')
Plan hash value: 1755540699
------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers |
------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 0 |00:00:00.01 | 3 |
|* 1 | INDEX UNIQUE SCAN| BLOAT_PKEY | 1 | 1 | 0 |00:00:00.01 | 3 |
------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - access("ID"=UUID_TO_RAW('00000000000000000000000000000000'))
I delete all rows with an intermediate commit because undo is limited:
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
delete from bloat where rownum<=1e6;
commit;
The lookup still traverses three levels of logically empty pages:
------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers |
------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 0 |00:00:00.01 | 3 |
|* 1 | INDEX UNIQUE SCAN| BLOAT_PKEY | 1 | 1 | 0 |00:00:00.01 | 3 |
------------------------------------------------------------------------------------------
The B-tree index didn't change after the delete - same height and same number of pages:
BLEVEL PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
2 25728 24837 40
Oracle can merge adjacent pages with a coalesce command:
alter index bloat_pkey coalesce;
This reduced the number of leaf and internal pages to the minimum possible while preserving the existing tree structure: one leaf page, one branch page, and the root page. The number of levels doesn't change, and the cost of the lookup remains the same:
BLEVEL PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
2 25728 1 2
------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers |
------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 0 |00:00:00.01 | 3 |
|* 1 | INDEX UNIQUE SCAN| BLOAT_PKEY | 1 | 1 | 0 |00:00:00.01 | 3 |
------------------------------------------------------------------------------------------
Oracle can shrink the allocated blocks:
alter index bloat_pkey shrink space;
This didn't reduce anything further:
BLEVEL PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
2 25728 1 2
------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers |
------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 0 |00:00:00.01 | 3 |
|* 1 | INDEX UNIQUE SCAN| BLOAT_PKEY | 1 | 1 | 0 |00:00:00.01 | 3 |
------------------------------------------------------------------------------------------
Finally, I need to rebuild the index to get one with a height that corresponds to an empty table:
alter index bloat_pkey rebuild online;
This is the correct size of an index with no rows - a single page that serves as both the root and the leaf:
BLEVEL PAGES LEAF_PAGES INTERNAL_PAGES
---------- ---------- ---------- --------------
0 8 1 0
------------------------------------------------------------------------------------------
| Id | Operation | Name | Starts | E-Rows | A-Rows | A-Time | Buffers |
------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT | | 1 | | 0 |00:00:00.01 | 1 |
|* 1 | INDEX UNIQUE SCAN| BLOAT_PKEY | 1 | 1 | 0 |00:00:00.01 | 1 |
------------------------------------------------------------------------------------------
Oracle Database indexes can increase in height, but the height does not decrease automatically after deletions. Reclaiming levels requires an index rebuild. When a large amount of data is deleted, the cost of an index scan from the root to the leaf remains high until the index is rebuilt.
PostgreSQL
Here is a similar table containing five million rows:
drop table if exists bloat;
create table bloat ( id uuid constraint bloat_pkey primary key);
insert into bloat select uuidv4() from generate_series(1,5000000);
vacuum analyze bloat;
I use pgstattuple to collect and aggregate the index statistics:
create extension if not exists pgstattuple;
select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');
The result shows two levels of branches, with 111 internal pages including the root. There's one root at level 0 and 110 branches at level 1, addressing 24607 leaves:
blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
2 | 24719 | 24607 | 111
EXPLAIN ANALYZE shows an Index Only Scan that reads 3 pages, the root, one branch, and the leaf:
postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';
QUERY PLAN
----------------------------------------------------------------------------------------
Index Only Scan using bloat_pkey on bloat (actual time=0.019..0.020 rows=0.00 loops=1)
Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=3
Planning Time: 0.065 ms
Execution Time: 0.034 ms
(7 rows)
I delete all rows and run the same:
postgres=# delete from bloat;
DELETE 5000000
postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';
QUERY PLAN
----------------------------------------------------------------------------------------
Index Only Scan using bloat_pkey on bloat (actual time=0.018..0.018 rows=0.00 loops=1)
Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=3
Planning Time: 0.066 ms
Execution Time: 0.032 ms
(7 rows)
postgres=# select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');
blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
2 | 24719 | 24607 | 111
The B-tree size and level remain the same after a delete because MVCC information is still present for transactions that may read a previous snapshot. After a while, autovacuum removes the dead index entries that are no longer visible to any transaction (you can also run VACUUM manually).
The PostgreSQL planner may prefer a sequential scan on an empty table, so I force an index scan to count how many index pages are read to find a key:
postgres=# set enable_seqscan to off;
SET
postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';
QUERY PLAN
----------------------------------------------------------------------------------------
Index Only Scan using bloat_pkey on bloat (actual time=0.013..0.013 rows=0.00 loops=1)
Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=1
Planning Time: 0.158 ms
Execution Time: 0.027 ms
(7 rows)
Only one page is read because a single root is sufficient to list the index entries of an empty table. No rebuild is required: regular autovacuum is sufficient.
If I check the index statistics, they still show two levels, with one root, one leaf, and a branch between them:
postgres=# select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');
blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
2 | 24719 | 1 | 2
(1 row)
You don't need a COALESCE command, as in Oracle, to merge adjacent blocks in a level. PostgreSQL did this after the regular VACUUM. However, similar to Oracle Database, the B-tree's height didn't decrease. Only its width at each level was reduced, with each level maintaining at least one page.
However, PostgreSQL can avoid traversing redundant upper levels. The purpose of internal pages is to determine which page to read at the lower level. If there's only one page at the level under the root, there's no need to read the root. We can start the scan at the highest level that has a single page. PostgreSQL keeps track of it as the "fast root". I can verify this from the index metadata, which I can read with the pageinspect extension:
postgres=# create extension if not exists pageinspect;
CREATE EXTENSION
postgres=# select * from bt_metap('bloat_pkey');
magic | version | root | level | fastroot | fastlevel | last_cleanup_num_delpages | last_cleanup_num_tuples | allequalimage
--------+---------+------+-------+----------+-----------+---------------------------+-------------------------+---------------
340322 | 4 | 295 | 2 | 14512 | 0 | 24715 | -1 | t
(1 row)
The physical number of levels is "level," and the true root is at block 295, but there's another root, "fastroot," with a different address, 14512. It was one of the internal pages when the table was full, or even a leaf in our case. As data was deleted, it remained alone at its level, and the levels above, up to the root, had a single entry, in a single page.
PostgreSQL records this page as the fast root and can start searches from it, bypassing upper levels that contain only a single pointer. Because the table is now empty, this page effectively serves as a leaf page. That's how an Index Scan reads only one page. The logical level, or "fastlevel," is recorded in the index's metadata page so that the query planner can evaluate the cost correctly.
I don't need to rebuild this index, but I can:
postgres=# reindex index concurrently bloat_pkey ;
REINDEX
postgres=# select * from bt_metap('bloat_pkey');
magic | version | root | level | fastroot | fastlevel | last_cleanup_num_delpages | last_cleanup_num_tuples | allequalimage
--------+---------+------+-------+----------+-----------+---------------------------+-------------------------+---------------
340322 | 4 | 0 | 0 | 0 | 0 | 0 | -1 | t
(1 row)
postgres=# select tree_level blevel, index_size/8192 pages, leaf_pages, internal_pages from pgstatindex('bloat_pkey');
blevel | pages | leaf_pages | internal_pages
--------+-------+------------+----------------
0 | 1 | 0 | 0
(1 row)
After the rebuild, all statistics show that the B-tree has a single page.
postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';
QUERY PLAN
----------------------------------------------------------------------------------------
Index Only Scan using bloat_pkey on bloat (actual time=0.005..0.005 rows=0.00 loops=1)
Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=2
Planning:
Buffers: shared hit=1
Planning Time: 0.067 ms
Execution Time: 0.021 ms
(9 rows)
You may wonder why two pages are read during execution. A clue is that one page is read during planning, even if you run it many times.
This is due to the rebuild with no DML to read and cache the metapage. Let's insert one row:
postgres=# insert into bloat select uuidv4();
INSERT 0 1
postgres=# explain (analyze, buffers, costs off) select * from bloat where id = '00000000000000000000000000000000';
QUERY PLAN
----------------------------------------------------------------------------------------
Index Only Scan using bloat_pkey on bloat (actual time=0.010..0.010 rows=0.00 loops=1)
Index Cond: (id = '00000000-0000-0000-0000-000000000000'::uuid)
Heap Fetches: 0
Index Searches: 1
Buffers: shared hit=1
Planning:
Buffers: shared hit=1
Planning Time: 0.069 ms
Execution Time: 0.024 ms
(9 rows)
postgres=#
During the planning phase, the system reads the index metapage (1 buffer) to obtain accurate statistics for cost estimation. In contrast, during execution, it relies on the relcache (rd_amcache) when available to prevent repeated metapage fetches. When REINDEX occurs, the relcache becomes invalid, requiring execution to read the index page again, increasing buffer usage to 2. After an INSERT, the relcache is updated with valid metadata, enabling execution to access the cached root location without extra buffer reads, keeping total buffer usage at 1.
Conclusion
The behavior of B+tree indexes after large deletions differs significantly between database engines.
PostgreSQL preserves the physical height of the B+tree after deletions, but VACUUM can reduce its effective traversal depth through a sophisticated fast root optimization. The index metadata page maintains two root pointers: the true root representing the physical tree height, and the fast root pointing to the lowest single-page level. This design, based on Lanin and Shasha's approach, allows PostgreSQL to bypass redundant upper levels that contain only a single pointer and start searches closer to the leaves.
The fast root pointer is adjusted atomically during page splits and deletions. When a page that is alone on its level splits, or when the next-to-last page on a level is deleted, PostgreSQL updates the fast root pointer as part of the atomic operation, with the metapage locked last to avoid deadlocks. The query planner uses the fast root level for cost estimation, ensuring accurate planning based on effective rather than physical height.
PostgreSQL also caches metadata in the relation cache to avoid fetching the metapage for every search, with validation checks to handle stale cached pointers. The physical tree remains unchanged, but lookups require fewer page accesses without any rebuild.
Oracle Database also preserves the physical structure of the index. Pages can be merged, and space can be reclaimed, but the height of the B+tree remains unchanged until the index is rebuilt. As a result, lookups continue to traverse the same number of levels even when the index contains few or no entries. A possible reason for the lack of a fast root optimization is Oracle's MVCC, where the root depends on the read snapshot, unlike PostgreSQL, where the index contains entries for all versions.
In both databases, a rebuild produces the smallest possible B+tree after a delete, according to the PCTFREE (Oracle) or FILLFACTOR (PostgreSQL) defined. The difference is that PostgreSQL can often recover most of the lookup efficiency automatically through regular vacuuming by maintaining a fast root, whereas Oracle requires an explicit rebuild to reclaim those levels. This applies only to deletions where you don't anticipate inserting the same amount, in which case it's better to retain the currently allocated structure and avoid future splits.
Top comments (0)