B-tree, GIN, BRIN Indexes & How the Planner picks the Index

In the previous blog, we explored the Query Pipeline and how PostgreSQL picks the best plans. Now let's go under the hood of indexes like how they're built, how PostgreSQL chooses between them, and when they help (or don't).

Part 1: The Index Abstraction - `pg_am`

PostgreSQL treats every index type as a pluggable module. You can even write your own.

Each index type is registered as an Access Method in a system table called pg_am. Think of pg_am as a registry, whenever you create an index, PostgreSQL looks up the right handler here.

SELECT amname, amtype, amhandler
FROM pg_am
WHERE amtype = 'i'; -- 'i' = index

-- amname | amtype |  amhandler
--------+--------+-------------
-- btree  | i      | bthandler
-- hash   | i      | hashhandler
-- gist   | i      | gisthandler
-- gin    | i      | ginhandler
-- spgist | i      | spghandler
-- brin   | i      | brinhandler

Each handler implements a fixed contract i.e., a C struct called IndexAmRoutine defined in include/access/amapi.h. It has function slots like:

ambuild : Build the index from scratch
aminsert : Insert a new entry
amgettuple : Fetch the next matching tuple during a scan
amcostestimate Tell the planner how expensive a scan will be
amcanunique Whether this index type can enforce uniqueness

Key insight: All index types B-tree, GIN, BRIN follow this same interface. That's why the planner can reason about them uniformly.

Part 2: B-tree Index (The Default)

Every PRIMARY KEY, UNIQUE, and plain CREATE INDEX uses a B-tree by default.

B-tree vs B+ tree

PostgreSQL actually uses a B+ tree variant (Lehman-Yao algorithm). Here's the key difference the B-tree and B+ tree:

--------------------------------------------------
Where is data stored?
- B-tree stores data in All nodes (internal + leaf)
- B+ tree stores in leaf nodes ONLY

--------------------------------------------------
Internal nodes contain?
- B-tree's internal nodes contains "Keys + data"
- B+ tree's internal nodes contains "Keys only" used for routing

--------------------------------------------------
Leaf Node
B+ tree leaf nodes uses the doubly-linked list

The doubly-linked leaf list is why range scans are fast, because once you find the start of a range, you just walk the list forward. No need to go back up the tree.

B-tree Page Format

Every B-tree page is 8 KB. Here's what lives inside it:

[PageHeaderData — 24 bytes]
  pd_lsn, pd_lower, pd_upper, pd_special

[BTPageOpaqueData — 16 bytes, at the end of the page]
  btpo_prev    → left sibling page number
  btpo_next    → right sibling page number
  btpo_level   → 0 = leaf, 1+ = internal
  btpo_flags   → BTP_LEAF, BTP_ROOT, BTP_DELETED

[ItemId array — line pointers]
  [0] = high key (max key on this page)
  [1] = first real entry
  ...

[FREE SPACE]

[IndexTuple entries — stored from bottom up]
  t_tid  → pointer to the heap tuple (the actual row)
  t_info → length + flags
  key data → the indexed value

What's BTPageOpaqueData? It's the metadata in the "special space" at the end of the page. This is what distinguishes a B-tree page from a heap page. Heap pages have empty special space.

Inspecting a Live B-tree Page

CREATE EXTENSION pageinspect;
CREATE TABLE btree_demo (id int, name text);
CREATE INDEX idx_btree_demo_id ON btree_demo(id);
INSERT INTO btree_demo SELECT g, 'name_'||g FROM generate_series(1,10000) g;

-- Meta page (always page 0)
SELECT magic, version, root, level FROM bt_metap('idx_btree_demo_id');
-- root=3 means the root is page 3; level=1 means 2 levels total

-- Root page stats
SELECT * FROM bt_page_stats('idx_btree_demo_id', 3);
-- type='r' means root

-- Leaf entries
SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('idx_btree_demo_id', 1)
LIMIT 5;

Page Split: What Happens When a Page Is Full

When a page runs out of space, PostgreSQL splits it into two. This is the most critical write operation in B-tree maintenance.

Step 1: Allocate a new page (right sibling)

Step 2: Find the split point
   Random inserts   → split 50/50
   Sequential inserts → split 90/10
   (90% stays on old page, new entry goes to new page)
   Why? Avoids 50% wasted space on append-heavy workloads!

Step 3: Copy right half to the new page

Step 4: Update sibling links
   old_page.btpo_next = new_page
   new_page.btpo_prev = old_page

Step 5: Insert a "downlink" into the parent page
   Parent gets: (split_key → new_page)
   If parent is full too → parent splits recursively

Step 6: WAL-log everything (entire operation is atomic)

The Fastpath Optimization for Sequential Inserts

For sequential inserts (e.g., an auto-increment primary key), PostgreSQL caches the rightmost leaf page. Instead of walking the tree every time, it goes directly to the last page.

/* From nbtinsert.c */
if (likely(FastPathLockRelationForInsert(rel, &stack)))
    return BTInsertFastPath(...);

This turns what would be O(log N) per insert into O(1) for the common case. That's why inserting rows with a BIGSERIAL primary key is so fast.

Part 3: B-tree Scan Variants

The planner can use a B-tree index in three different ways depending on how many rows match and what you're selecting.

1. Index Scan (fetch one row at a time)

EXPLAIN SELECT * FROM orders WHERE id = 42;
-- Index Scan using orders_pkey

Flow:

Walk down the B-tree: root → internal pages → leaf
Read the TID (heap row pointer) from the leaf entry
Do a random read to that heap page
Check MVCC visibility
Return the tuple

When chosen: High selectivity that is, very few rows match (e.g., looking up by primary key).

2. Index Only Scan (no heap access at all)

CREATE INDEX idx_orders_status_amount ON orders(status, amount);

EXPLAIN SELECT status, amount FROM orders WHERE status = 'pending';
-- Index Only Scan

The index leaf entry already contains (status, amount, TID) , every column you need is right there. So PostgreSQL skips the heap entirely.

One catch: It needs to verify visibility. It checks the visibility map (_vm file):

If the page is marked all_visible → return data straight from index leaf
If not → fetch from heap just to check visibility, but still use index data

-- After VACUUM sets the all_visible bits:
VACUUM orders;
EXPLAIN (ANALYZE, BUFFERS) SELECT status, amount FROM orders WHERE status = 'pending';
-- Heap Fetches: 0 ← pure index-only scan

Requirement: Every column in SELECT and WHERE must be in the index.

3. Bitmap Index Scan (bulk fetch, sorted I/O)

EXPLAIN SELECT * FROM orders WHERE status = 'pending';
-- Bitmap Heap Scan
--   → Bitmap Index Scan

This is a two-phase process:

Phase 1: Build the bitmap

Walk the B-tree and collect ALL matching TIDs into an in-memory bitmap
The bitmap is page-granular: it records which heap pages contain matches
If the bitmap grows beyond work_mem → switches to "lossy" mode (marks whole pages, must recheck later)

Phase 2: Fetch from heap

Sort the page numbers from the bitmap
Read heap pages in physical order (near-sequential I/O)
Apply MVCC visibility check
Return matching tuples

Bonus: combining two indexes with BitmapAnd:

CREATE INDEX idx_status ON orders(status);
CREATE INDEX idx_region ON orders(region);

EXPLAIN SELECT * FROM orders WHERE status = 'pending' AND region = 'US';
-- BitmapAnd
--   → Bitmap Index Scan on idx_status   (bitmap A)
--   → Bitmap Index Scan on idx_region   (bitmap B)
-- Bitmap Heap Scan on BitmapAnd(A, B)

PostgreSQL can combine two partial indexes instead of requiring one composite index. The bitmaps are ANDed at the page level.

Part 4: Multi-Column Indexes

CREATE INDEX idx_orders_composite ON orders(status, region, created_at);

The B-tree sorts entries by (status, region, created_at) together. This means you can only use the index if you're filtering on leading columns.

-- Uses all 3 columns
WHERE status = 'pending' AND region = 'US' AND created_at > '2024-01-01'

-- Uses first 2 columns
WHERE status = 'pending' AND region = 'US'

-- Uses first column only
WHERE status = 'pending'

-- Skips first column — can't use this index
WHERE region = 'US'

-- Skips first column — can't use this index
WHERE region = 'US' AND created_at > '2024-01-01'

Why? B-tree lookup starts from the leftmost key. If you skip a column, the tree has no starting point to navigate from.

Exception - ORDER BY on a trailing column:

-- Index: (status, created_at)
SELECT * FROM orders
WHERE status = 'pending'      -- equality on status (leading col)
ORDER BY created_at;          -- index already sorted by created_at here
-- → Index Scan — no Sort node needed!

Once status is pinned to a single value, the remaining entries are already sorted by created_at in the B-tree.

Part 5: Partial Indexes

A partial index only covers rows that match a WHERE clause. The result is a smaller, faster index for selective queries.

-- 99% of orders are 'delivered'. Only 1% are 'pending'.
-- Why index all rows when you only query pending ones?

CREATE INDEX idx_pending_orders ON orders(created_at)
WHERE status = 'pending';

-- Serves this query perfectly, at ~1% the size:
SELECT * FROM orders
WHERE status = 'pending' AND created_at > '2024-01-01';

Also useful for sparse unique constraints:

-- Allow multiple NULLs, but enforce uniqueness for non-NULL emails:
CREATE UNIQUE INDEX idx_unique_email ON users(email)
WHERE email IS NOT NULL;

Part 6: Expression Indexes

Index the result of an expression, not just a raw column.

CREATE INDEX idx_lower_name ON customers(lower(name));

-- This query uses the index:
SELECT * FROM customers WHERE lower(name) = 'john doe';

-- This does NOT (different expression):
SELECT * FROM customers WHERE name = 'john doe';

The expression is computed at INSERT/UPDATE time and stored like any other index entry. At query time, PostgreSQL evaluates lower(name) for the predicate and checks if it matches the stored index expression.

Part 7: GIN - Generalized Inverted Index

GIN is designed for multi-valued data, where a single row can contribute many index keys. Think: full-text search, arrays, JSONB.

How GIN is Structured

Instead of mapping key → one row, GIN maps key → list of rows:

For a text document "the quick brown fox":
  'brown' → {row 1, row 37, row 72}
  'fox'   → {row 1, row 24}
  'quick' → {row 1, row 37}

For an integer array {1, 3, 7}:
  1 → {row 1}
  3 → {row 1}
  7 → {row 1}

Each key has a posting list - a sorted list of TIDs (row pointers).

-- Full-text search:
CREATE INDEX idx_fts ON articles USING gin(to_tsvector('english', body));

SELECT title FROM articles
WHERE to_tsvector('english', body) @@ to_tsquery('english', 'postgres & index');

-- Array containment:
CREATE INDEX idx_tags ON posts USING gin(tags);
SELECT * FROM posts WHERE tags @> ARRAY['postgresql', 'performance'];

-- JSONB:
CREATE INDEX idx_metadata ON orders USING gin(metadata);
SELECT * FROM orders WHERE metadata @> '{"region": "US", "priority": "high"}';

The Pending List - GIN's Write Buffer

Inserting into GIN is expensive (you must find and update the posting list for every key in the document). To avoid this on every write, GIN uses a pending list:

INSERT → appended to pending list (fast)
         ↓
Cleanup happens when:
  - Pending list hits gin_pending_list_limit (default 4MB)
  - VACUUM runs
  - You call gin_clean_pending_list() manually

Trade-off:

fastupdate=on (default): Writes are fast, but reads may need to merge the pending list.
fastupdate=off: Consistent read speed, but slower writes

CREATE INDEX idx_tags ON posts USING gin(tags) WITH (fastupdate=off);

Part 8: BRIN - Block Range Index

BRIN is the smallest possible index. Instead of indexing every row, it stores only a summary (min/max) per range of heap pages.

How BRIN Works

Imagine a table of sensor readings inserted in time order:

Heap pages   0–127  → recorded_at range: [2024-01-01 … 2024-01-08]
Heap pages 128–255  → recorded_at range: [2024-01-08 … 2024-01-15]
Heap pages 256–383  → recorded_at range: [2024-01-15 … 2024-01-22]

BRIN stores just:

range 0: {min: 2024-01-01, max: 2024-01-08}
range 1: {min: 2024-01-08, max: 2024-01-15}
range 2: {min: 2024-01-15, max: 2024-01-22}

For a query WHERE recorded_at BETWEEN '2024-01-14' AND '2024-01-16':

Range 0: max < 2024-01-14 → SKIP
Range 1: overlaps → READ pages 128–255
Range 2: min ≤ 2024-01-16 → READ pages 256–383
Range 3: min > 2024-01-16 → SKIP

CREATE INDEX idx_readings_brin ON sensor_readings
    USING brin(recorded_at) WITH (pages_per_range=128);

-- Size comparison:
SELECT
    pg_size_pretty(pg_relation_size('sensor_readings')) AS table,
    pg_size_pretty(pg_relation_size('idx_readings_brin')) AS brin_index;
-- table: 4096 MB
-- brin:     48 kB  ← ~100,000x smaller than a B-tree!

When BRIN is Useless

BRIN only works if the data is physically ordered on disk i.e., rows with nearby values are on nearby pages.

-- Check correlation:
SELECT correlation FROM pg_stats
WHERE tablename = 'sensor_readings' AND attname = 'recorded_at';
-- correlation = 0.99 → BRIN is perfect
-- correlation = 0.05 → BRIN is useless, every range overlaps

Part 9: Hash Index

CREATE INDEX idx_orders_hash ON orders USING hash(customer_id);

Hash indexes are slightly smaller and faster than B-trees for pure equality lookups. But they have major limitations:

Hash v/s B-tree
----------------------------------------------
Equality(=) → Works with both Hash & B-tree
Range >, <, BETWEEN → Only B-tree
ORDER BY → Only B-tree
Multi-column → Only B-tree
UNIQUE constraints → Only B-tree

Verdict: In practice, B-tree handles equality just as well plus everything else. Hash indexes are rarely worth it.

Part 10: Index Bloat and Maintenance

Why Indexes Bloat

PostgreSQL uses MVCC (Multi-Version Concurrency Control). When you UPDATE a row, it doesn't modify the existing row in place. It:

Inserts a new version of the row (and a new index entry pointing to it)
Marks the old row as dead, but leaves it there.

Over time, dead index entries accumulate. This is index bloat.

-- Measure index bloat:
SELECT
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
    idx_scan,
    idx_tup_read
FROM pg_stat_user_indexes
WHERE relname = 'orders'
ORDER BY pg_relation_size(indexrelid) DESC;

VACUUM Cleans Dead Entries

-- Standard VACUUM: marks dead entries for reuse
VACUUM orders;

-- VACUUM FULL: rewrites the index entirely (locks the table!)
VACUUM FULL orders;

-- REINDEX CONCURRENTLY: rebuild without locking reads (PG 12+)
REINDEX INDEX CONCURRENTLY idx_orders_status;
REINDEX TABLE CONCURRENTLY orders;

Part 11: How the Planner Chooses a Scan Type

The planner estimates the cost of each scan option based on selectivity (how many rows match) and page access patterns.

-- Case 1: Highly selective → Index Scan
SELECT * FROM orders WHERE id = 42;
-- ~1 row out of 1M. Random read cost for 1 page << seqscan of 10000 pages.
-- → Index Scan

-- Case 2: Low selectivity → Seq Scan
SELECT * FROM orders WHERE status = 'delivered';
-- ~50% of rows. 500K random reads >> one sequential pass.
-- → Seq Scan (even with an index on status!)

-- Case 3: Medium selectivity → Bitmap Heap Scan
SELECT * FROM orders WHERE status = 'pending';
-- ~10% of rows. Bitmap sorts TIDs → near-sequential heap I/O.
-- → Bitmap Heap Scan

-- Case 4: ORDER BY matches index → no Sort node
SELECT * FROM orders WHERE status = 'pending' ORDER BY created_at LIMIT 10;
-- Composite index (status, created_at) gives sorted output.
-- Limit stops after 10 entries — reads only 10 index entries total.
-- → Index Scan (extremely cheap)

When to Create an Index (and When Not To)

-- GOOD: high-cardinality column, frequent lookups
CREATE INDEX ON orders(customer_id);
CREATE INDEX ON orders(created_at);

-- GOOD: foreign key columns (prevents lock escalation on DELETE)
CREATE INDEX ON order_items(order_id);

-- GOOD: covering index (store extra columns to enable Index Only Scan)
CREATE INDEX ON orders(status, created_at)
    INCLUDE (amount, customer_id);  -- extra columns, not part of sort key

-- BAD: low-cardinality column alone (only 2 values → planner prefers seqscan anyway)
-- CREATE INDEX ON orders(is_deleted);

-- BAD: append-only table rarely queried by this column
-- CREATE INDEX ON audit_log(event_type);

-- DETECT unused indexes:
SELECT indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE relname = 'orders'
  AND idx_scan = 0;
-- idx_scan = 0 → never used → candidate for dropping

Part 12: Hands-On Lab

1. Explore a B-tree's structure

CREATE TABLE lab_btree (id bigserial primary key, val text, score int);
INSERT INTO lab_btree(val, score)
SELECT md5(random()::text), (random()*1000)::int
FROM generate_series(1, 100000);

SELECT * FROM bt_metap('lab_btree_pkey');

-- Root page stats:
SELECT * FROM bt_page_stats('lab_btree_pkey',
    (SELECT root FROM bt_metap('lab_btree_pkey')));

-- Walk leaf pages 1–10:
SELECT blkno, type, live_items, dead_items, free_size
FROM generate_series(1, 10) blkno,
     bt_page_stats('lab_btree_pkey', blkno);

2. Watch a page split happen

CREATE TABLE split_test (id int);
CREATE INDEX idx_split ON split_test(id);

SELECT bt_metap('idx_split');  -- root=1, single page
INSERT INTO split_test SELECT generate_series(1, 500);
SELECT * FROM bt_metap('idx_split');  -- root may have changed

INSERT INTO split_test SELECT generate_series(501, 5000);
SELECT * FROM bt_metap('idx_split');  -- now multiple levels!

3. Compare all three scan types

CREATE TABLE scan_compare (
    id bigserial,
    status text,
    region text,
    amount numeric,
    created_at timestamptz DEFAULT now()
);
INSERT INTO scan_compare(status, region, amount, created_at)
SELECT
    CASE (random()*3)::int
        WHEN 0 THEN 'pending'
        WHEN 1 THEN 'delivered'
        ELSE 'cancelled' END,
    CASE (random()*3)::int
        WHEN 0 THEN 'US'
        WHEN 1 THEN 'EU'
        ELSE 'APAC' END,
    (random()*1000)::numeric(10,2),
    now() - ((random()*365)::int || ' days')::interval
FROM generate_series(1, 500000);

CREATE INDEX ON scan_compare(status);
CREATE INDEX ON scan_compare(region);
CREATE INDEX ON scan_compare(status, region);
VACUUM ANALYZE scan_compare;

-- Seq Scan (low selectivity):
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM scan_compare WHERE status='delivered';

-- Bitmap Heap Scan (medium selectivity):
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM scan_compare WHERE status='pending';

-- BitmapAnd (two indexes):
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM scan_compare WHERE status='pending' AND region='US';

-- Index Only Scan (after VACUUM, Heap Fetches should be 0):
EXPLAIN (ANALYZE, BUFFERS)
SELECT status, region FROM scan_compare WHERE status='pending';

4. BRIN effectiveness

CREATE TABLE brin_test (id bigserial, recorded_at timestamptz, value numeric);

-- Insert in time order (high correlation):
INSERT INTO brin_test(recorded_at, value)
SELECT now() - ((1000000-g)||' seconds')::interval, random()*100
FROM generate_series(1, 1000000) g;

CREATE INDEX idx_brin ON brin_test USING brin(recorded_at);
VACUUM ANALYZE brin_test;

-- Verify correlation:
SELECT correlation FROM pg_stats
WHERE tablename='brin_test' AND attname='recorded_at';
-- Should be near 1.0

-- Compare sizes:
SELECT
    pg_size_pretty(pg_relation_size('brin_test')) AS table,
    pg_size_pretty(pg_relation_size('idx_brin')) AS brin;

-- Use it:
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM brin_test
WHERE recorded_at BETWEEN now()-interval'1 hour' AND now();

5. Partial vs full index

CREATE INDEX idx_partial_pending ON scan_compare(created_at)
WHERE status = 'pending';

SELECT
    pg_size_pretty(pg_relation_size('idx_partial_pending')) AS partial,
    pg_size_pretty(pg_relation_size('scan_compare_created_at_idx')) AS full;
-- Partial is ~3x smaller

EXPLAIN SELECT * FROM scan_compare
WHERE status = 'pending' AND created_at > now() - interval '7 days';
-- Uses idx_partial_pending

6. Index deduplication

CREATE TABLE dedup_test (status text, amount int);
CREATE INDEX idx_dedup ON dedup_test(status);

INSERT INTO dedup_test
SELECT CASE WHEN random()<0.5 THEN 'active' ELSE 'inactive' END,
       (random()*1000)::int
FROM generate_series(1, 1000000);

SELECT pg_size_pretty(pg_relation_size('idx_dedup')) AS with_dedup;

-- Compare against dedup disabled:
CREATE INDEX idx_no_dedup ON dedup_test(status) WITH (deduplicate_items=off);
SELECT pg_size_pretty(pg_relation_size('idx_no_dedup')) AS without_dedup;

7. Find unused indexes

SELECT pg_stat_reset();  -- reset stats first, run your workload, then:

SELECT
    schemaname,
    tablename,
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS size,
    idx_scan AS scans_since_reset
FROM pg_stat_user_indexes
JOIN pg_index ON pg_index.indexrelid = pg_stat_user_indexes.indexrelid
WHERE idx_scan = 0
  AND NOT pg_index.indisprimary
  AND NOT pg_index.indisunique
ORDER BY pg_relation_size(indexrelid) DESC;
-- These are candidates for dropping

Conclusion

In this module, we went from the top-level abstraction down to the bytes on disk:

Every index type is a pluggable Access Method registered in pg_am
PostgreSQL uses a B+ tree variant - data only in leaves, leaves linked for range scans
The planner picks between Index Scan, Bitmap Heap Scan, and Seq Scan based on estimated row count
Index Only Scans avoid the heap entirely when the index covers all needed columns and the visibility map is up to date
GIN is for multi-valued types (arrays, full-text, JSONB). It's an inverted index
BRIN is for physically-ordered data, tiny size, but useless if correlation is low
Every UPDATE leaves dead index entries behind, VACUUM is what keeps them from accumulating

What's Next → Module 7: Vacuuming

You now know that every UPDATE leaves a dead heap tuple and a dead index entry. Module 7 answers: what exactly cleans them up, and what happens when it falls behind?

We'll cover how VACUUM walks the heap, reclaims dead tuples, cleans dead index entries, updates the free space map, sets all_visible bits, and freezes old XIDs to prevent transaction ID wraparound. We'll also tune autovacuum and diagnose real table bloat using pgstattuple and pg_freespacemap.

Part 1: The Index Abstraction - `pg_am`

PostgreSQL treats every index type as a pluggable module. You can even write your own.

Each index type is registered as an Access Method in a system table called pg_am. Think of pg_am as a registry, whenever you create an index, PostgreSQL looks up the right handler here.

SELECT amname, amtype, amhandler
FROM pg_am
WHERE amtype = 'i'; -- 'i' = index

-- amname | amtype |  amhandler
--------+--------+-------------
-- btree  | i      | bthandler
-- hash   | i      | hashhandler
-- gist   | i      | gisthandler
-- gin    | i      | ginhandler
-- spgist | i      | spghandler
-- brin   | i      | brinhandler

Each handler implements a fixed contract i.e., a C struct called IndexAmRoutine defined in include/access/amapi.h. It has function slots like:

ambuild : Build the index from scratch
aminsert : Insert a new entry
amgettuple : Fetch the next matching tuple during a scan
amcostestimate Tell the planner how expensive a scan will be
amcanunique Whether this index type can enforce uniqueness

Key insight: All index types B-tree, GIN, BRIN follow this same interface. That's why the planner can reason about them uniformly.

Part 2: B-tree Index (The Default)

Every PRIMARY KEY, UNIQUE, and plain CREATE INDEX uses a B-tree by default.

B-tree vs B+ tree

PostgreSQL actually uses a B+ tree variant (Lehman-Yao algorithm). Here's the key difference the B-tree and B+ tree:

--------------------------------------------------
Where is data stored?
- B-tree stores data in All nodes (internal + leaf)
- B+ tree stores in leaf nodes ONLY

--------------------------------------------------
Internal nodes contain?
- B-tree's internal nodes contains "Keys + data"
- B+ tree's internal nodes contains "Keys only" used for routing

--------------------------------------------------
Leaf Node
B+ tree leaf nodes uses the doubly-linked list

The doubly-linked leaf list is why range scans are fast, because once you find the start of a range, you just walk the list forward. No need to go back up the tree.

B-tree Page Format

Every B-tree page is 8 KB. Here's what lives inside it:

[PageHeaderData — 24 bytes]
  pd_lsn, pd_lower, pd_upper, pd_special

[BTPageOpaqueData — 16 bytes, at the end of the page]
  btpo_prev    → left sibling page number
  btpo_next    → right sibling page number
  btpo_level   → 0 = leaf, 1+ = internal
  btpo_flags   → BTP_LEAF, BTP_ROOT, BTP_DELETED

[ItemId array — line pointers]
  [0] = high key (max key on this page)
  [1] = first real entry
  ...

[FREE SPACE]

[IndexTuple entries — stored from bottom up]
  t_tid  → pointer to the heap tuple (the actual row)
  t_info → length + flags
  key data → the indexed value

What's BTPageOpaqueData? It's the metadata in the "special space" at the end of the page. This is what distinguishes a B-tree page from a heap page. Heap pages have empty special space.

Inspecting a Live B-tree Page

CREATE EXTENSION pageinspect;
CREATE TABLE btree_demo (id int, name text);
CREATE INDEX idx_btree_demo_id ON btree_demo(id);
INSERT INTO btree_demo SELECT g, 'name_'||g FROM generate_series(1,10000) g;

-- Meta page (always page 0)
SELECT magic, version, root, level FROM bt_metap('idx_btree_demo_id');
-- root=3 means the root is page 3; level=1 means 2 levels total

-- Root page stats
SELECT * FROM bt_page_stats('idx_btree_demo_id', 3);
-- type='r' means root

-- Leaf entries
SELECT itemoffset, ctid, itemlen, data
FROM bt_page_items('idx_btree_demo_id', 1)
LIMIT 5;

Page Split: What Happens When a Page Is Full

When a page runs out of space, PostgreSQL splits it into two. This is the most critical write operation in B-tree maintenance.

Step 1: Allocate a new page (right sibling)

Step 2: Find the split point
   Random inserts   → split 50/50
   Sequential inserts → split 90/10
   (90% stays on old page, new entry goes to new page)
   Why? Avoids 50% wasted space on append-heavy workloads!

Step 3: Copy right half to the new page

Step 4: Update sibling links
   old_page.btpo_next = new_page
   new_page.btpo_prev = old_page

Step 5: Insert a "downlink" into the parent page
   Parent gets: (split_key → new_page)
   If parent is full too → parent splits recursively

Step 6: WAL-log everything (entire operation is atomic)

The Fastpath Optimization for Sequential Inserts

For sequential inserts (e.g., an auto-increment primary key), PostgreSQL caches the rightmost leaf page. Instead of walking the tree every time, it goes directly to the last page.

/* From nbtinsert.c */
if (likely(FastPathLockRelationForInsert(rel, &stack)))
    return BTInsertFastPath(...);

This turns what would be O(log N) per insert into O(1) for the common case. That's why inserting rows with a BIGSERIAL primary key is so fast.

Part 3: B-tree Scan Variants

The planner can use a B-tree index in three different ways depending on how many rows match and what you're selecting.

1. Index Scan (fetch one row at a time)

EXPLAIN SELECT * FROM orders WHERE id = 42;
-- Index Scan using orders_pkey

Flow:

Walk down the B-tree: root → internal pages → leaf
Read the TID (heap row pointer) from the leaf entry
Do a random read to that heap page
Check MVCC visibility
Return the tuple

When chosen: High selectivity that is, very few rows match (e.g., looking up by primary key).

2. Index Only Scan (no heap access at all)

CREATE INDEX idx_orders_status_amount ON orders(status, amount);

EXPLAIN SELECT status, amount FROM orders WHERE status = 'pending';
-- Index Only Scan

The index leaf entry already contains (status, amount, TID) , every column you need is right there. So PostgreSQL skips the heap entirely.

One catch: It needs to verify visibility. It checks the visibility map (_vm file):

If the page is marked all_visible → return data straight from index leaf
If not → fetch from heap just to check visibility, but still use index data

-- After VACUUM sets the all_visible bits:
VACUUM orders;
EXPLAIN (ANALYZE, BUFFERS) SELECT status, amount FROM orders WHERE status = 'pending';
-- Heap Fetches: 0 ← pure index-only scan

Requirement: Every column in SELECT and WHERE must be in the index.

3. Bitmap Index Scan (bulk fetch, sorted I/O)

EXPLAIN SELECT * FROM orders WHERE status = 'pending';
-- Bitmap Heap Scan
--   → Bitmap Index Scan

This is a two-phase process:

Phase 1: Build the bitmap

Walk the B-tree and collect ALL matching TIDs into an in-memory bitmap
The bitmap is page-granular: it records which heap pages contain matches
If the bitmap grows beyond work_mem → switches to "lossy" mode (marks whole pages, must recheck later)

Phase 2: Fetch from heap

Sort the page numbers from the bitmap
Read heap pages in physical order (near-sequential I/O)
Apply MVCC visibility check
Return matching tuples

Bonus: combining two indexes with BitmapAnd:

CREATE INDEX idx_status ON orders(status);
CREATE INDEX idx_region ON orders(region);

EXPLAIN SELECT * FROM orders WHERE status = 'pending' AND region = 'US';
-- BitmapAnd
--   → Bitmap Index Scan on idx_status   (bitmap A)
--   → Bitmap Index Scan on idx_region   (bitmap B)
-- Bitmap Heap Scan on BitmapAnd(A, B)

PostgreSQL can combine two partial indexes instead of requiring one composite index. The bitmaps are ANDed at the page level.

Part 4: Multi-Column Indexes

CREATE INDEX idx_orders_composite ON orders(status, region, created_at);

The B-tree sorts entries by (status, region, created_at) together. This means you can only use the index if you're filtering on leading columns.

-- Uses all 3 columns
WHERE status = 'pending' AND region = 'US' AND created_at > '2024-01-01'

-- Uses first 2 columns
WHERE status = 'pending' AND region = 'US'

-- Uses first column only
WHERE status = 'pending'

-- Skips first column — can't use this index
WHERE region = 'US'

-- Skips first column — can't use this index
WHERE region = 'US' AND created_at > '2024-01-01'

Why? B-tree lookup starts from the leftmost key. If you skip a column, the tree has no starting point to navigate from.

Exception - ORDER BY on a trailing column:

-- Index: (status, created_at)
SELECT * FROM orders
WHERE status = 'pending'      -- equality on status (leading col)
ORDER BY created_at;          -- index already sorted by created_at here
-- → Index Scan — no Sort node needed!

Once status is pinned to a single value, the remaining entries are already sorted by created_at in the B-tree.

Part 5: Partial Indexes

A partial index only covers rows that match a WHERE clause. The result is a smaller, faster index for selective queries.

-- 99% of orders are 'delivered'. Only 1% are 'pending'.
-- Why index all rows when you only query pending ones?

CREATE INDEX idx_pending_orders ON orders(created_at)
WHERE status = 'pending';

-- Serves this query perfectly, at ~1% the size:
SELECT * FROM orders
WHERE status = 'pending' AND created_at > '2024-01-01';

Also useful for sparse unique constraints:

-- Allow multiple NULLs, but enforce uniqueness for non-NULL emails:
CREATE UNIQUE INDEX idx_unique_email ON users(email)
WHERE email IS NOT NULL;

Part 6: Expression Indexes

Index the result of an expression, not just a raw column.

CREATE INDEX idx_lower_name ON customers(lower(name));

-- This query uses the index:
SELECT * FROM customers WHERE lower(name) = 'john doe';

-- This does NOT (different expression):
SELECT * FROM customers WHERE name = 'john doe';

Part 7: GIN - Generalized Inverted Index

GIN is designed for multi-valued data, where a single row can contribute many index keys. Think: full-text search, arrays, JSONB.

How GIN is Structured

Instead of mapping key → one row, GIN maps key → list of rows:

For a text document "the quick brown fox":
  'brown' → {row 1, row 37, row 72}
  'fox'   → {row 1, row 24}
  'quick' → {row 1, row 37}

For an integer array {1, 3, 7}:
  1 → {row 1}
  3 → {row 1}
  7 → {row 1}

Each key has a posting list - a sorted list of TIDs (row pointers).

-- Full-text search:
CREATE INDEX idx_fts ON articles USING gin(to_tsvector('english', body));

SELECT title FROM articles
WHERE to_tsvector('english', body) @@ to_tsquery('english', 'postgres & index');

-- Array containment:
CREATE INDEX idx_tags ON posts USING gin(tags);
SELECT * FROM posts WHERE tags @> ARRAY['postgresql', 'performance'];

-- JSONB:
CREATE INDEX idx_metadata ON orders USING gin(metadata);
SELECT * FROM orders WHERE metadata @> '{"region": "US", "priority": "high"}';

The Pending List - GIN's Write Buffer

Inserting into GIN is expensive (you must find and update the posting list for every key in the document). To avoid this on every write, GIN uses a pending list:

INSERT → appended to pending list (fast)
         ↓
Cleanup happens when:
  - Pending list hits gin_pending_list_limit (default 4MB)
  - VACUUM runs
  - You call gin_clean_pending_list() manually

Trade-off:

fastupdate=on (default): Writes are fast, but reads may need to merge the pending list.
fastupdate=off: Consistent read speed, but slower writes

CREATE INDEX idx_tags ON posts USING gin(tags) WITH (fastupdate=off);

Part 8: BRIN - Block Range Index

BRIN is the smallest possible index. Instead of indexing every row, it stores only a summary (min/max) per range of heap pages.

How BRIN Works

Imagine a table of sensor readings inserted in time order:

Heap pages   0–127  → recorded_at range: [2024-01-01 … 2024-01-08]
Heap pages 128–255  → recorded_at range: [2024-01-08 … 2024-01-15]
Heap pages 256–383  → recorded_at range: [2024-01-15 … 2024-01-22]

BRIN stores just:

range 0: {min: 2024-01-01, max: 2024-01-08}
range 1: {min: 2024-01-08, max: 2024-01-15}
range 2: {min: 2024-01-15, max: 2024-01-22}

For a query WHERE recorded_at BETWEEN '2024-01-14' AND '2024-01-16':

Range 0: max < 2024-01-14 → SKIP
Range 1: overlaps → READ pages 128–255
Range 2: min ≤ 2024-01-16 → READ pages 256–383
Range 3: min > 2024-01-16 → SKIP

CREATE INDEX idx_readings_brin ON sensor_readings
    USING brin(recorded_at) WITH (pages_per_range=128);

-- Size comparison:
SELECT
    pg_size_pretty(pg_relation_size('sensor_readings')) AS table,
    pg_size_pretty(pg_relation_size('idx_readings_brin')) AS brin_index;
-- table: 4096 MB
-- brin:     48 kB  ← ~100,000x smaller than a B-tree!

When BRIN is Useless

BRIN only works if the data is physically ordered on disk i.e., rows with nearby values are on nearby pages.

-- Check correlation:
SELECT correlation FROM pg_stats
WHERE tablename = 'sensor_readings' AND attname = 'recorded_at';
-- correlation = 0.99 → BRIN is perfect
-- correlation = 0.05 → BRIN is useless, every range overlaps

Part 9: Hash Index

CREATE INDEX idx_orders_hash ON orders USING hash(customer_id);

Hash indexes are slightly smaller and faster than B-trees for pure equality lookups. But they have major limitations:

Hash v/s B-tree
----------------------------------------------
Equality(=) → Works with both Hash & B-tree
Range >, <, BETWEEN → Only B-tree
ORDER BY → Only B-tree
Multi-column → Only B-tree
UNIQUE constraints → Only B-tree

Verdict: In practice, B-tree handles equality just as well plus everything else. Hash indexes are rarely worth it.

Part 10: Index Bloat and Maintenance

Why Indexes Bloat

PostgreSQL uses MVCC (Multi-Version Concurrency Control). When you UPDATE a row, it doesn't modify the existing row in place. It:

Inserts a new version of the row (and a new index entry pointing to it)
Marks the old row as dead, but leaves it there.

Over time, dead index entries accumulate. This is index bloat.

-- Measure index bloat:
SELECT
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS index_size,
    idx_scan,
    idx_tup_read
FROM pg_stat_user_indexes
WHERE relname = 'orders'
ORDER BY pg_relation_size(indexrelid) DESC;

VACUUM Cleans Dead Entries

-- Standard VACUUM: marks dead entries for reuse
VACUUM orders;

-- VACUUM FULL: rewrites the index entirely (locks the table!)
VACUUM FULL orders;

-- REINDEX CONCURRENTLY: rebuild without locking reads (PG 12+)
REINDEX INDEX CONCURRENTLY idx_orders_status;
REINDEX TABLE CONCURRENTLY orders;

Part 11: How the Planner Chooses a Scan Type

The planner estimates the cost of each scan option based on selectivity (how many rows match) and page access patterns.

-- Case 1: Highly selective → Index Scan
SELECT * FROM orders WHERE id = 42;
-- ~1 row out of 1M. Random read cost for 1 page << seqscan of 10000 pages.
-- → Index Scan

-- Case 2: Low selectivity → Seq Scan
SELECT * FROM orders WHERE status = 'delivered';
-- ~50% of rows. 500K random reads >> one sequential pass.
-- → Seq Scan (even with an index on status!)

-- Case 3: Medium selectivity → Bitmap Heap Scan
SELECT * FROM orders WHERE status = 'pending';
-- ~10% of rows. Bitmap sorts TIDs → near-sequential heap I/O.
-- → Bitmap Heap Scan

-- Case 4: ORDER BY matches index → no Sort node
SELECT * FROM orders WHERE status = 'pending' ORDER BY created_at LIMIT 10;
-- Composite index (status, created_at) gives sorted output.
-- Limit stops after 10 entries — reads only 10 index entries total.
-- → Index Scan (extremely cheap)

When to Create an Index (and When Not To)

-- GOOD: high-cardinality column, frequent lookups
CREATE INDEX ON orders(customer_id);
CREATE INDEX ON orders(created_at);

-- GOOD: foreign key columns (prevents lock escalation on DELETE)
CREATE INDEX ON order_items(order_id);

-- GOOD: covering index (store extra columns to enable Index Only Scan)
CREATE INDEX ON orders(status, created_at)
    INCLUDE (amount, customer_id);  -- extra columns, not part of sort key

-- BAD: low-cardinality column alone (only 2 values → planner prefers seqscan anyway)
-- CREATE INDEX ON orders(is_deleted);

-- BAD: append-only table rarely queried by this column
-- CREATE INDEX ON audit_log(event_type);

-- DETECT unused indexes:
SELECT indexrelname, idx_scan
FROM pg_stat_user_indexes
WHERE relname = 'orders'
  AND idx_scan = 0;
-- idx_scan = 0 → never used → candidate for dropping

Part 12: Hands-On Lab

1. Explore a B-tree's structure

CREATE TABLE lab_btree (id bigserial primary key, val text, score int);
INSERT INTO lab_btree(val, score)
SELECT md5(random()::text), (random()*1000)::int
FROM generate_series(1, 100000);

SELECT * FROM bt_metap('lab_btree_pkey');

-- Root page stats:
SELECT * FROM bt_page_stats('lab_btree_pkey',
    (SELECT root FROM bt_metap('lab_btree_pkey')));

-- Walk leaf pages 1–10:
SELECT blkno, type, live_items, dead_items, free_size
FROM generate_series(1, 10) blkno,
     bt_page_stats('lab_btree_pkey', blkno);

2. Watch a page split happen

CREATE TABLE split_test (id int);
CREATE INDEX idx_split ON split_test(id);

SELECT bt_metap('idx_split');  -- root=1, single page
INSERT INTO split_test SELECT generate_series(1, 500);
SELECT * FROM bt_metap('idx_split');  -- root may have changed

INSERT INTO split_test SELECT generate_series(501, 5000);
SELECT * FROM bt_metap('idx_split');  -- now multiple levels!

3. Compare all three scan types

CREATE TABLE scan_compare (
    id bigserial,
    status text,
    region text,
    amount numeric,
    created_at timestamptz DEFAULT now()
);
INSERT INTO scan_compare(status, region, amount, created_at)
SELECT
    CASE (random()*3)::int
        WHEN 0 THEN 'pending'
        WHEN 1 THEN 'delivered'
        ELSE 'cancelled' END,
    CASE (random()*3)::int
        WHEN 0 THEN 'US'
        WHEN 1 THEN 'EU'
        ELSE 'APAC' END,
    (random()*1000)::numeric(10,2),
    now() - ((random()*365)::int || ' days')::interval
FROM generate_series(1, 500000);

CREATE INDEX ON scan_compare(status);
CREATE INDEX ON scan_compare(region);
CREATE INDEX ON scan_compare(status, region);
VACUUM ANALYZE scan_compare;

-- Seq Scan (low selectivity):
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM scan_compare WHERE status='delivered';

-- Bitmap Heap Scan (medium selectivity):
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM scan_compare WHERE status='pending';

-- BitmapAnd (two indexes):
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM scan_compare WHERE status='pending' AND region='US';

-- Index Only Scan (after VACUUM, Heap Fetches should be 0):
EXPLAIN (ANALYZE, BUFFERS)
SELECT status, region FROM scan_compare WHERE status='pending';

4. BRIN effectiveness

CREATE TABLE brin_test (id bigserial, recorded_at timestamptz, value numeric);

-- Insert in time order (high correlation):
INSERT INTO brin_test(recorded_at, value)
SELECT now() - ((1000000-g)||' seconds')::interval, random()*100
FROM generate_series(1, 1000000) g;

CREATE INDEX idx_brin ON brin_test USING brin(recorded_at);
VACUUM ANALYZE brin_test;

-- Verify correlation:
SELECT correlation FROM pg_stats
WHERE tablename='brin_test' AND attname='recorded_at';
-- Should be near 1.0

-- Compare sizes:
SELECT
    pg_size_pretty(pg_relation_size('brin_test')) AS table,
    pg_size_pretty(pg_relation_size('idx_brin')) AS brin;

-- Use it:
EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM brin_test
WHERE recorded_at BETWEEN now()-interval'1 hour' AND now();

5. Partial vs full index

CREATE INDEX idx_partial_pending ON scan_compare(created_at)
WHERE status = 'pending';

SELECT
    pg_size_pretty(pg_relation_size('idx_partial_pending')) AS partial,
    pg_size_pretty(pg_relation_size('scan_compare_created_at_idx')) AS full;
-- Partial is ~3x smaller

EXPLAIN SELECT * FROM scan_compare
WHERE status = 'pending' AND created_at > now() - interval '7 days';
-- Uses idx_partial_pending

6. Index deduplication

CREATE TABLE dedup_test (status text, amount int);
CREATE INDEX idx_dedup ON dedup_test(status);

INSERT INTO dedup_test
SELECT CASE WHEN random()<0.5 THEN 'active' ELSE 'inactive' END,
       (random()*1000)::int
FROM generate_series(1, 1000000);

SELECT pg_size_pretty(pg_relation_size('idx_dedup')) AS with_dedup;

-- Compare against dedup disabled:
CREATE INDEX idx_no_dedup ON dedup_test(status) WITH (deduplicate_items=off);
SELECT pg_size_pretty(pg_relation_size('idx_no_dedup')) AS without_dedup;

7. Find unused indexes

SELECT pg_stat_reset();  -- reset stats first, run your workload, then:

SELECT
    schemaname,
    tablename,
    indexrelname,
    pg_size_pretty(pg_relation_size(indexrelid)) AS size,
    idx_scan AS scans_since_reset
FROM pg_stat_user_indexes
JOIN pg_index ON pg_index.indexrelid = pg_stat_user_indexes.indexrelid
WHERE idx_scan = 0
  AND NOT pg_index.indisprimary
  AND NOT pg_index.indisunique
ORDER BY pg_relation_size(indexrelid) DESC;
-- These are candidates for dropping

Conclusion

In this module, we went from the top-level abstraction down to the bytes on disk:

Every index type is a pluggable Access Method registered in pg_am
PostgreSQL uses a B+ tree variant - data only in leaves, leaves linked for range scans
The planner picks between Index Scan, Bitmap Heap Scan, and Seq Scan based on estimated row count
Index Only Scans avoid the heap entirely when the index covers all needed columns and the visibility map is up to date
GIN is for multi-valued types (arrays, full-text, JSONB). It's an inverted index
BRIN is for physically-ordered data, tiny size, but useless if correlation is low
Every UPDATE leaves dead index entries behind, VACUUM is what keeps them from accumulating

What's Next → Module 7: Vacuuming

You now know that every UPDATE leaves a dead heap tuple and a dead index entry. Module 7 answers: what exactly cleans them up, and what happens when it falls behind?

Part 1: The Index Abstraction - pg_am

Part 2: B-tree Index (The Default)

B-tree vs B+ tree

B-tree Page Format

Inspecting a Live B-tree Page

Page Split: What Happens When a Page Is Full

The Fastpath Optimization for Sequential Inserts

Part 3: B-tree Scan Variants

1. Index Scan (fetch one row at a time)

2. Index Only Scan (no heap access at all)

3. Bitmap Index Scan (bulk fetch, sorted I/O)

Part 4: Multi-Column Indexes

Part 5: Partial Indexes

Part 6: Expression Indexes

Part 7: GIN - Generalized Inverted Index

How GIN is Structured

The Pending List - GIN's Write Buffer

Part 8: BRIN - Block Range Index

How BRIN Works

When BRIN is Useless

Part 9: Hash Index

Part 10: Index Bloat and Maintenance

Why Indexes Bloat

VACUUM Cleans Dead Entries

Part 11: How the Planner Chooses a Scan Type

When to Create an Index (and When Not To)

Part 12: Hands-On Lab

1. Explore a B-tree's structure

2. Watch a page split happen

3. Compare all three scan types

4. BRIN effectiveness

5. Partial vs full index

6. Index deduplication

7. Find unused indexes

Conclusion

What's Next → Module 7: Vacuuming

Enjoyed this post?

Related Posts

PostgreSQL Internals - Module 1: Process & Memory Architecture

PostgreSQL Internals - Module 2: Page Layout & Storage Internals

PostgreSQL Internals - Module 4: Write-Ahead Logging, Checkpoints and Crash Recovery

Comments

Leave a comment

Part 1: The Index Abstraction - pg_am

Part 2: B-tree Index (The Default)

B-tree vs B+ tree

B-tree Page Format

Inspecting a Live B-tree Page

Page Split: What Happens When a Page Is Full

The Fastpath Optimization for Sequential Inserts

Part 3: B-tree Scan Variants

1. Index Scan (fetch one row at a time)

2. Index Only Scan (no heap access at all)

3. Bitmap Index Scan (bulk fetch, sorted I/O)

Part 4: Multi-Column Indexes

Part 5: Partial Indexes

Part 6: Expression Indexes

Part 7: GIN - Generalized Inverted Index

How GIN is Structured

The Pending List - GIN's Write Buffer

Part 8: BRIN - Block Range Index

How BRIN Works

When BRIN is Useless

Part 9: Hash Index

Part 10: Index Bloat and Maintenance

Why Indexes Bloat

VACUUM Cleans Dead Entries

Part 11: How the Planner Chooses a Scan Type

When to Create an Index (and When Not To)

Part 12: Hands-On Lab

1. Explore a B-tree's structure

2. Watch a page split happen

3. Compare all three scan types

4. BRIN effectiveness

5. Partial vs full index

6. Index deduplication

7. Find unused indexes

Conclusion

What's Next → Module 7: Vacuuming

Enjoyed this post?

Part 1: The Index Abstraction - `pg_am`

Part 1: The Index Abstraction - `pg_am`