--- title: "PostgreSQL Internals - Module 6: Indexing Internals" description: "Deep dive into index internals: B-tree page format, split algorithm, GIN posting lists, BRIN range summaries, and how the planner picks between the Indexes." author: "Samba Siva" published: 2026-05-02T08:53:26.204Z updated: 2026-11-07T10:00:29.255Z tags: - "PostgreSQL" - "Technical" - "PGInternals" url: "https://sambasivareddy.in/blog/postgresql-internals-module-6-indexing-internals" --- # PostgreSQL Internals - Module 6: Indexing Internals 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. ```sql 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: ```markdown -------------------------------------------------- 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: ```markdown [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 ```sql 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. ```markdown 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. ```c /* 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) ```sql EXPLAIN SELECT * FROM orders WHERE id = 42; -- Index Scan using orders_pkey ``` **Flow:** 1. Walk down the B-tree: root → internal pages → leaf 2. Read the TID (heap row pointer) from the leaf entry 3. Do a random read to that heap page 4. Check MVCC visibility 5. 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) ```sql 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 ```sql -- 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) ```sql 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:** ```sql 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 ```sql 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**. ```sql -- 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:** ```sql -- 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. ```sql -- 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: ```sql -- 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. ```sql 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**: ```markdown 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). ```sql -- 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**: ```markdown 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 ```sql 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** ```sql 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. ```sql -- 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 ```sql 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: ```markdown 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: 1. Inserts a **new version** of the row (and a new index entry pointing to it) 2. Marks the **old row** as dead, but leaves it there. Over time, dead index entries accumulate. This is index bloat. ```sql -- 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 ```sql -- 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. ```sql -- 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) ```sql -- 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 ```sql 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 ```sql 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 ```sql 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 ```sql 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 ```sql 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 ```sql 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 ```sql 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`.