PostgreSQL B-Tree Indexes: Internal Structure, Index Scans, and Bloat

Most developers know indexes make queries faster. Fewer people understand why they are fast, what PostgreSQL actually stores inside an index page, or why an index can grow much larger than expected over time.

Once I started reading query plans and database internals, I realized that understanding the structure of a PostgreSQL B-Tree index makes performance tuning significantly easier.

B-Tree vs B+ Tree

When PostgreSQL documentation talks about a B-Tree index, it is referring to its primary indexing access method. Internally, however, the implementation behaves much closer to a B+ Tree.

The key difference is that internal pages only contain separator values and pointers to child pages. Actual row references live in leaf pages.

Because leaf pages are linked together, PostgreSQL can efficiently perform range scans by walking through neighboring leaf pages instead of traversing the tree repeatedly.

PostgreSQL calls it a B-Tree, but its implementation has many characteristics commonly associated with a B+ Tree.

Internal Structure of a B-Tree Index

A PostgreSQL B-Tree index is organized into fixed-size pages. By default, each page is 8 KB.

At a high level, the tree consists of:

• Root page
• Internal pages
• Leaf pages

Root Page

Every index starts from a single root page.

When PostgreSQL needs to locate a value, it begins at the root and determines which branch should contain the target key.

Think of the root page as a routing table rather than a storage location.

Internal Pages

Internal pages contain:

• Key boundaries
• Child page pointers

They do not store actual row references.

Their job is simply to narrow the search space as quickly as possible.

For example, an internal page might contain separators like:

[100] [500] [1000]

A lookup for 750 would immediately follow the branch between 500 and 1000.

Leaf Pages

Leaf pages are where the useful data lives.

Each leaf entry contains:

• Indexed value
• Heap tuple identifier (TID)

Example:

email = 'alice@example.com'
TID   = (245,7)

The TID points to the exact row location inside the table heap.

PostgreSQL can use this reference to fetch the actual row when necessary.

How an Index Scan Works

Consider the following query:

SELECT *
FROM users
WHERE email = 'alice@example.com';

Assume an index exists:

CREATE INDEX idx_users_email
ON users(email);

The execution flow looks like this:

1. Start at the root page
2. Traverse internal pages
3. Reach the appropriate leaf page
4. Locate the matching key
5. Read the TID
6. Fetch the row from the heap

Visually:

Root -> Internal -> Leaf -> TID -> Heap Row

The important observation is that PostgreSQL is usually not reading the entire table. Instead, it follows a small path through the tree whose depth is typically only a few levels.

Why Range Queries Are Fast

B-Tree indexes are especially powerful for ordered data access.

Consider:

SELECT *
FROM orders
WHERE amount BETWEEN 1000 AND 5000;

The database performs:

• One tree traversal to find the starting key
• Sequential movement across neighboring leaf pages

Because leaf pages are linked together, PostgreSQL avoids repeatedly traversing from the root.

This is one of the reasons B-Tree indexes perform extremely well for:

• <
• >
• BETWEEN
• ORDER BY
• Prefix searches

For example:

WHERE name LIKE 'chir%'

can often use a B-Tree index efficiently.

Index-Only Scans

Sometimes PostgreSQL can avoid touching the table entirely.

Consider:

SELECT email
FROM users
WHERE email = 'alice@example.com';

If all required columns already exist inside the index and PostgreSQL confirms row visibility through the visibility map, it can perform an Index Only Scan.

Benefits include:

• Fewer disk reads
• Reduced heap access
• Lower latency

When reading execution plans, seeing an Index Only Scan is usually a positive sign.

Page Splits and Tree Growth

Indexes are not static structures.

As new rows are inserted, PostgreSQL needs to place new entries into the correct leaf page.

Eventually a page becomes full.

When that happens, PostgreSQL performs a page split.

The process looks roughly like this:

Before

[10 20 30 40 50]

After

[10 20 30]
[40 50 60]

A separator key is propagated upward so the tree remains balanced.

This balancing operation ensures lookups remain efficient even as tables grow into millions of rows.

Why Index Bloat Happens

One of the most common production issues is index bloat.

Developers often assume that deleting rows immediately shrinks an index.

That is not how PostgreSQL works.

When rows are updated or deleted:

• Old index entries become obsolete
• Space is marked reusable
• Physical pages are usually not returned to the operating system

Over time, repeated updates and deletes create unused space inside the index.

The result is:

• Larger index size
• More pages to scan
• Poor cache efficiency
• Slower queries

A bloated index can be significantly larger than the amount of live data it contains.

Detecting Index Bloat

A simple starting point is checking index sizes:

SELECT
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid))
FROM pg_stat_user_indexes;

Large indexes on frequently updated tables are often good candidates for investigation.

You can also compare table growth against index growth to identify disproportionate expansion.

Monitoring index size over time is often more useful than looking at a single snapshot.

Fixing Index Bloat

PostgreSQL provides several options.

REINDEX

The most direct approach is rebuilding the index.

REINDEX INDEX idx_users_email;

This creates a fresh compact version of the index.

REINDEX CONCURRENTLY

For production systems:

REINDEX INDEX CONCURRENTLY idx_users_email;

This minimizes blocking while rebuilding the structure.

Vacuum

Regular vacuuming helps reclaim dead tuples and maintain healthy indexes.

VACUUM ANALYZE users;

While vacuum does not fully eliminate bloat, it plays an important role in preventing excessive growth.

What I Take Away From This

Before learning database internals, I treated indexes as a black box that magically made queries faster.

Understanding the structure changed how I read execution plans. When I see an Index Scan, Bitmap Index Scan, or Index Only Scan, I can now visualize the path PostgreSQL is taking through the tree.

The biggest lesson is that indexes are not free. They speed up reads, but they also consume storage, require maintenance, and can become bloated over time. Knowing how PostgreSQL organizes and navigates a B-Tree index helps explain many of the performance characteristics we observe in real production systems.