Postgres Indexes Under the Hood: B-Trees, Page Splits, and Why the Query Planner Ignores You

You run CREATE INDEX idx_orders_status ON orders(status);, verify it exists in \d orders, and fire off your query with high hopes:

EXPLAIN ANALYZE 
SELECT * FROM orders WHERE status = 'shipped';

Then you look at the plan:

Seq Scan on orders  (cost=0.00..3420.00 rows=45000 width=128) (actual time=0.015..12.450 rows=45120 loops=1)
  Filter: (status = 'shipped'::text)
  Rows Removed by Filter: 54880
Planning Time: 0.120 ms
Execution Time: 14.210 ms

Postgres ignored your index entirely. It opted to scan all 100,000 rows across every single disk block instead.

When this happens, developers often assume the database engine is broken or try to force an index scan by tweaking session flags. But PostgreSQL's cost-based optimizer is rarely being foolish. It understands the physics of physical disk blocks, random I/O penalties, and the internal structure of disk pages better than we do.

To write queries that scale and design indexes that actually get used, we need to peel back the abstraction layer. Let's look at what an index looks like on disk, how Lehman-Yao trees avoid global locks, what really happens during a page split, and how the planner decides whether to use your index.

---

1. Anatomy of an 8KB B-Tree Disk Page

In PostgreSQL, both table data (the heap) and B-tree indexes are divided into fixed-size 8KB disk blocks (pages). An index is not an abstract sorted array in memory; it is a multi-level hierarchy of physical 8KB pages saved in your database cluster's storage directory.

Every 8KB index block follows a strict memory layout defined in the PostgreSQL source code:

+-------------------------------------------------------------------+
| PageHeaderData (24 bytes)                                         |
| pd_lsn (WAL tracking) | pd_checksum | pd_lower | pd_upper | ...    |
+-------------------------------------------------------------------+
| ItemIdData Array (Line Pointers, 4 bytes each)                    |
| [ Item 1 ] -> [ Item 2 ] -> [ Item 3 ] ... (grows downward v)     |
+-------------------------------------------------------------------+
|                     FREE SPACE GAP                                |
|                                                                   |
+-------------------------------------------------------------------+
| Index Tuples (Data & TIDs) (grows upward ^)                       |
| [ Tuple 3: "shipped", (Block 42, Offset 1) ]                      |
| [ Tuple 2: "processing", (Block 12, Offset 8) ]                   |
| [ Tuple 1: "delivered", (Block 9, Offset 3) ]                     |
+-------------------------------------------------------------------+
| BTPageOpaqueData (Special Space at block end, 16 bytes)           |
| btpo_prev | btpo_next | btpo_level | btpo_flags                   |
+-------------------------------------------------------------------+

The Squeeze Strategy

PostgreSQL manages free space inside an 8KB page by using two converging pointers:

• pd_lower: Points to the end of the line pointer array. As new index entries are added, line pointers are appended downwards.
• pd_upper: Points to the start of the latest index tuple payload. Index tuples are added from the bottom of the page upwards.

The remaining unallocated space is simply pd_upper - pd_lower.

What Is Stored Inside an Index Tuple?

A leaf-level B-tree tuple contains two pieces of information:

1. The Key Value: The indexed column data (for example, the integer 42 or string 'shipped').
2. The Heap Item Pointer (ctid / TID): A 6-byte identifier consisting of (BlockNumber, OffsetNumber). This tells PostgreSQL the exact 8KB table heap page and line pointer slot where the row lives.

If you have PostgreSQL 13 or newer, duplicate keys are automatically compressed into Posting Lists. Instead of storing duplicate key strings repeatedly, Postgres stores the key value once followed by a packed array of up to 100+ TIDs, saving substantial disk space.

---

2. Concurrency and Lehman & Yao B-Link Trees

A classical B-tree algorithm requires lock coupling during traversals: you must hold a read lock on the parent node until you acquire a lock on the child node. During an insert that causes a page split, you would need to lock the parent, child, and neighbor nodes simultaneously to maintain tree consistency. In a database handling 10,000 queries per second, this creates severe concurrency bottlenecks.

PostgreSQL solves this using the Lehman & Yao B-Link Tree algorithm.

Level 1 (Root):          [  Page A (High Key: 50)  ] 
                               /               \
                              v                 v
Level 0 (Leaves): [ Page B (Keys 1..50) ] ---> [ Page C (Keys 51..100) ]
                        (btpo_next)              (btpo_next = 0)

In a B-link tree:

1. Right-Links (btpo_next): Every page contains a pointer to its right-hand sibling on the same level.
2. The High Key: The very first tuple on any non-rightmost page acts as a strict upper bound. It defines the maximum value permitted on that page.

Why This Matters for Concurrency

When a query traverses down the tree to find key 45, it reads Page B. If Page B is concurrently split in half by a background writer, key 45 might move to a new sibling page before the parent node can be updated.

Instead of crashing or needing a global lock, the reader notices that the search key (45) is greater than Page B's new High Key (40). The reader follows the btpo_next right-link directly to the sibling page, finding the key without having to restart the search from the root.

Traversals can run with shared read locks and zero parent lock coupling.

---

3. The Physics of Page Splits and Write Amplification

What happens when an 8KB index page runs out of free space (pd_upper - pd_lower < tuple_size)?

Postgres must perform an Index Page Split:

Before Split (Page 12 is 100% full):
[ Item 1 | Item 2 | Item 3 | Item 4 | Item 5 | Item 6 ]

Insert Item 7 causes Split:
1. Allocate new 8KB block (Page 89).
2. Move half the items (Items 4, 5, 6, 7) to Page 89.
3. Set Page 12's High Key = Item 3.
4. Link Page 12 btpo_next -> Page 89.
5. Insert downlink for Page 89 into Parent Page.

50/50 Splits vs. The Right-Split Optimization

• Random Inserts (50/50 Split): When keys are inserted randomly (such as UUIDv4 strings), Postgres splits the page down the middle. Both the old and new pages end up ~50% empty. If insertions remain random, index bloat climbs rapidly because pages never fill up completely before splitting again.
• Monotonic Appends (Right-Split): When inserting sequential data (like auto-incrementing BIGSERIAL IDs or created_at timestamps), PostgreSQL notices that the incoming key is larger than all existing keys on the page. Instead of a 50/50 split, it creates an empty new page and moves only the new tuple over. The original page remains 90%+ packed.

The Hidden Cost: WAL Amplification

Page splits are expensive not just in CPU and I/O, but also in Write-Ahead Logging (WAL).

Under PostgreSQL's crash recovery model, the first modification to an 8KB page after a checkpoint requires writing a Full Page Image (FPI) to the WAL stream. When a single insert triggers a page split, Postgres writes:

• The full 8KB image of the newly allocated page.
• The full 8KB image of the split page.
• The updated parent page.

A single 50-byte record insert can instantly produce over 24KB of WAL traffic.

---

4. The Cost Model Math: Why the Planner Ignores Your Index

Now we can understand why the query planner rejected our index in the opening example.

PostgreSQL uses a cost-based optimizer that calculates an abstract cost score for every possible execution path (Sequential Scan, Bitmap Index Scan, Index Scan, Index-Only Scan). The path with the lowest numerical cost wins.

The default planner configuration includes these key cost constants:

Parameter	Default Cost	Meaning
seq_page_cost	1.0	Cost to read an 8KB page sequentially from disk/OS cache
random_page_cost	4.0	Cost to read an 8KB page via random disk seek
cpu_tuple_cost	0.01	CPU cost to process one table tuple
cpu_index_tuple_cost	0.005	CPU cost to process one index entry
cpu_operator_cost	0.0025	CPU cost to execute an operator function (WHERE clause)

The Math: 100,000 Rows, 1,000 Pages

Let us calculate the cost for a table with 100,000 rows stored across 1,000 heap pages (100 rows per page):

Plan A: Sequential Scan

A sequential scan reads the 1,000 pages in sequential order and tests the filter on each row.

$$\text{Cost} = (1000 \times \text{seq_page_cost}) + (100000 \times (\text{cpu_tuple_cost} + \text{cpu_operator_cost}))$$
$$\text{Cost} = (1000 \times 1.0) + (100000 \times 0.0125) = 1000 + 1250 = \mathbf{2250.0}$$

Plan B: Index Scan (Query Matches 15,000 Rows / 15% Selectivity)

An index scan first searches the B-tree leaf pages, collects the 15,000 TIDs, and then visits the heap for each row.

Because table rows matching status = 'shipped' are scattered across the table, each row lookup represents a random page fetch into the heap:

$$\text{Cost} = (\text{Index Pages} \times 4.0) + (15000 \times \text{cpu_index_tuple_cost}) + (15000 \times \text{random_page_cost}) + (15000 \times \text{cpu_tuple_cost})$$
$$\text{Cost} \approx 60 + 75 + (15000 \times 4.0) + (15000 \times 0.01) \approx 60 + 75 + 60000 + 150 = \mathbf{60285.0}$$

60,285 vs 2,250. The index scan is estimated to be 26 times slower than scanning the entire table from front to back!

The Tipping Point

When a query selects more than roughly 5% to 15% of the total rows in a table (depending on row width and physical clustering), random I/O thrashing makes index lookups slower than streaming the entire table sequentially. Sequential reads take advantage of OS readahead caching and kernel prefetching.

SSD Tuning Tip: The default random_page_cost = 4.0 was designed for spinning mechanical hard drives where head seeks take milliseconds. On modern NVMe SSDs, random reads are nearly as fast as sequential reads. Setting random_page_cost between 1.1 and 1.5 in postgresql.conf allows the planner to choose indexes much more reasonably.

---

5. The MVCC Blindspot and The Visibility Map

You might ask: "What if my query only selects columns that are inside the index? Can't Postgres skip the table heap entirely?"

This is called an Index-Only Scan. But there is a catch: PostgreSQL indexes do not store MVCC (Multi-Version Concurrency Control) transaction visibility flags.

In the heap, every row header contains xmin (creating transaction ID) and xmax (deleting/updating transaction ID). When a transaction queries a row, it inspects these flags against its active snapshot to determine if the row is visible.

Index tuples contain zero visibility metadata. If an index scan finds a matching key, how does it know whether that row was deleted five milliseconds ago by an uncommitted transaction?

The Solution: The Visibility Map (.vm Fork)

To prevent every single index read from having to visit the heap just to check visibility, PostgreSQL maintains an auxiliary file for every table: the Visibility Map.

Table File (heap):       [ Block 0 ] [ Block 1 ] [ Block 2 ] [ Block 3 ] ...
Visibility Map (.vm):    [ Bit 1=1 ] [ Bit 2=0 ] [ Bit 3=1 ] [ Bit 4=1 ] ...
                                         |
                                         v
                         Block 1 has modified/unvacuumed rows!
                         Index-Only Scan MUST fetch heap page 1.

For every 8KB heap page, the visibility map stores two bits:

• All-Visible Bit: Set to 1 if all tuples on that heap page are older than the oldest running transaction (meaning every active transaction can see them without checking tuple headers).
• All-Frozen Bit: Set to 1 if all tuples have been frozen by VACUUM.

When executing an Index-Only Scan:

1. Postgres retrieves the TID from the index leaf.
2. It checks the visibility map bit for that heap block.
3. If Bit = 1: It returns the column value directly from the index without touching the heap.
4. If Bit = 0: It must perform a Heap Fetch from disk to read the raw tuple header.

You can inspect this behavior using EXPLAIN (ANALYZE, BUFFERS):

Index Only Scan using idx_users_email on users  (cost=0.42..28.50 rows=10 width=32) (actual rows=10)
  Heap Fetches: 10
  Buffers: shared hit=14

If Heap Fetches is high, your table has unvacuumed churn, turning your fast Index-Only Scan into a standard random-access heap scan. Running VACUUM ANALYZE users; updates the visibility map and brings Heap Fetches down to 0.

---

6. Hands-On: Inspecting Your Index with pageinspect

PostgreSQL includes a built-in extension named pageinspect that lets you look inside actual index disk pages.

You can enable it in any database:

CREATE EXTENSION IF NOT EXISTS pageinspect;

Inspecting B-Tree Metadata

To see the depth of your tree, the root page block number, and the number of leaf pages:

SELECT * FROM bt_metap('idx_orders_status');

Output:

-[ RECORD 1 ]-------------+-------
magic                     | 3405705
version                   | 4
root                      | 3
level                     | 1
fastroot                  | 3
fastlevel                 | 1
last_cleanup_num_delpages | 0
last_cleanup_num_tuples   | 100000
allequalimage             | 1

Here, level = 1 means the B-tree has a root page and leaf pages (depth 2).

Inspecting Page Statistics and Free Space

To inspect the fill rate and free space of block 1:

SELECT * FROM bt_page_stats('idx_orders_status', 1);

Output:

-[ RECORD 1 ]-+-----
blkno         | 1
type          | l      -- 'l' = leaf page, 'r' = root, 'i' = internal
live_items    | 367
dead_items    | 0
avg_item_size | 16
page_size     | 8192
free_size     | 1840   -- Remaining unallocated bytes in this 8KB page
btpo_prev     | 0
btpo_next     | 2      -- Lehman-Yao right-link to block 2
btpo_level    | 0
btpo_flags    | 1

Reading Raw Index Tuples

You can dump the exact tuples, high keys, and heap TIDs stored inside a block:

SELECT itemoffset, ctid, itemlen, data 
FROM bt_page_items('idx_orders_status', 1) 
LIMIT 5;

Output:

 itemoffset |   ctid    | itemlen |           data            
------------+-----------+---------+---------------------------
          1 | (2,1)     |      16 | 73 68 69 70 70 65 64 00   -- High Key (Upper bound)
          2 | (0,1)     |      16 | 63 61 6e 63 65 6c 65 64   -- "canceled" -> Heap Block 0, Slot 1
          3 | (0,2)     |      16 | 63 61 6e 63 65 6c 65 64   -- "canceled" -> Heap Block 0, Slot 2
          4 | (0,3)     |      16 | 64 65 6c 69 76 65 72 65   -- "delivered" -> Heap Block 0, Slot 3

Notice itemoffset 1 is the High Key: it does not point to a row in the heap, but defines the maximum value stored in block 1.

---

7. Beyond B-Tree: Practical Index Architectures

B-trees are general-purpose workhorses, but choosing the wrong index type or structure leads to massive storage overhead and poor performance.

A. Covering Indexes with INCLUDE

If you frequently query:

SELECT user_id, email, status FROM users WHERE email = '[e-mail]';

A standard index on (email) requires reading the index and then jumping to the heap for user_id and status.

Instead of indexing all three columns (which bloats B-tree branch nodes with sorting overhead), use INCLUDE:

CREATE UNIQUE INDEX idx_users_email_covering 
ON users (email) 
INCLUDE (user_id, status);

The B-tree sort structure is built solely on email. The payload columns user_id and status are stored only in the leaf nodes, enabling full Index-Only Scans with minimal index footprint.

B. Partial Indexes for Skewed Data

If 98% of rows have status = 'completed' and you only query active jobs:

-- Bad: Indexes 10,000,000 rows (9.8 million never queried)
CREATE INDEX idx_jobs_status ON jobs(status);

-- Good: Indexes only the 200,000 active rows (98% smaller, fits in RAM)
CREATE INDEX idx_jobs_active ON jobs(created_at) 
WHERE status IN ('queued', 'running');

C. BRIN (Block Range Index) for Append-Only Time Series

For audit logs, sensor readings, and event streams where rows are inserted chronologically:

CREATE INDEX idx_events_created_brin 
ON event_logs USING BRIN (created_at);

Instead of recording every row pointer, BRIN stores the minimum and maximum timestamp for physical ranges of 128 heap blocks (1MB chunks).

• Storage difference on 50 million rows: B-Tree is ~1.2 GB; BRIN is ~64 KB.
• When querying WHERE created_at >= '2026-09-01', the engine reads the tiny BRIN summary, skips non-matching 1MB file segments, and scans only the relevant disk blocks.

---

Summary Mental Model

When designing database schemas and diagnosing slow queries, keep these four physical realities in mind:

1. Indexes are 8KB disk pages: They suffer from fragmentation, lock contention, and page splits just like tables.
2. Sequential reads are fast, random reads are penalized: If your query matches more than 10-15% of a table, a Seq Scan is usually intentional and faster than an index scan.
3. Index-Only Scans need VACUUM: If the visibility map is dirty, the engine must visit the table heap on every row anyway.
4. Right tool for the data: Use standard B-trees for high-cardinality lookups, INCLUDE for covering queries, Partial indexes for skewed flags, and BRIN for chronological append logs.

Understanding the mechanics beneath EXPLAIN turns query optimization from guesswork into predictable engineering.