10203040
IndexesFree lessonSource-grounded1 real lab transcript
B-Tree Indexes: Ordered Leaves, Right-Links, and Index-Only Scans
A B-tree keeps keys ordered so one structure can support equality, ranges, sorted output, and optional uniqueness.
Sideways links keep a search on course while pages split. A covering index can skip the heap only for candidate pages marked all-visible; otherwise the same Index Only Scan fetches from the heap.
Follow the ordered path
Descend once. Move sideways safely.
A B-tree turns one sorted structure into equality, range, order, and uniqueness. Its high keys and sibling links keep that path correct while pages split.
01 / Find key 42
Routing pages lead to ordered leaves.
Play the lookup or select a level. The highlighted path narrows a key range, then continues sideways for a range scan.
Step 1
The root chooses a key range.
Search key 42 is greater than separator 30, so descent follows the right downlink.
leaf A · level 0102029
Remember: internal pages route; leaves hold ordered entries; sibling links carry ranges forward.
02 / Race a split
The high key is the recovery sign.
A split updates more than one page. Watch a search remain correct even while its parent downlink is briefly stale.
Beat 1
The target leaf has no room.
A new key 35 belongs between 30 and 40, but the page is full.
parent downlinkleft only
303540
search 35 land left → compare high key → move right
03 / Ask about visibility
“Index only” is decided one heap page at a time.
Coverage puts the needed columns in the index. The visibility-map bit decides whether this candidate page still needs a heap visit.
INCLUDE total_amount = 89.00Heap Fetches: 1The node stays an Index Only Scan, but it visits the heap to check this tuple's visibility.
04 / Prove it yourself
Inspect the real pages, then read the chosen plan.
The promoted pageinspect and EXPLAIN lab is shown once. It proves page level and occupancy, then keeps Bitmap Heap Scan distinct from index-only access.
Lab-verified · correctedOpen the psql proof
Run in psql
CREATE EXTENSION IF NOT EXISTS pageinspect;
SELECT btpo_level, type, live_items, dead_items
FROM bt_page_stats('idx_orders_cust', 1);
SELECT * FROM bt_metap('idx_orders_cust');
EXPLAIN (ANALYZE, BUFFERS)
SELECT total_amount FROM orders WHERE customer_id = 42;Real output PostgreSQL 17.10
btpo_level | type | live_items | dead_items
------------+------+------------+------------
0 | l | 262 | 0
(1 row)
magic | version | root | level | fastroot | fastlevel | last_cleanup_num_delpages | last_cleanup_num_tuples | allequalimage
--------+---------+------+-------+----------+-----------+---------------------------+-------------------------+---------------
340322 | 4 | 211 | 2 | 211 | 2 | 0 | -1 | f
(1 row)
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
Bitmap Heap Scan on orders (cost=11.52..519.25 rows=400 width=16) (actual time=0.062..0.206 rows=41 loops=1)
Recheck Cond: (customer_id = 42)
Heap Blocks: exact=39
Buffers: shared hit=39 read=3
-> Bitmap Index Scan on idx_orders_cust (cost=0.00..11.42 rows=400 width=0) (actual time=0.045..0.045 rows=41 loops=1)
Index Cond: (customer_id = 42)
Buffers: shared read=3
Planning Time: 1.502 ms
Execution Time: 0.221 ms
(11 rows)Payoff: bt_metap reports a zero-based root level; bt_page_stats exposes a real leaf. The captured Bitmap Heap Scan is evidence of heap access, not index-only success.
Source trailUnder the hood
01
_bt_first
nbtsearch.cBuilds the boundary key and positions an index scan at its first matching leaf item.
02
_bt_search
nbtsearch.cDescends pivot downlinks and invokes _bt_moveright at each level.
03
_bt_split
nbtinsert.cCreates the right half, installs the new high key, and updates sibling links.
04
IndexOnlyNext
nodeIndexonlyscan.cChecks VM_ALL_VISIBLE for each candidate heap page and heap-fetches when needed.
Source-level guardrails
- A right-link field is not always a next page. Rightmost pages carry P_NONE; non-rightmost pages use btpo_next with a high key. BTPageOpaqueData
- Split recovery is not lock-free magic. PostgreSQL uses buffer locks while high keys and right-links let searches recover from stale downlinks. _bt_search
- Coverage is necessary, not sufficient. All-visible is checked per candidate page; one Index Only Scan may still report Heap Fetches. IndexOnlyNext
nbtree separates navigation from visibility. It finds ordered index entries; the executor and visibility map decide whether the corresponding heap page must still be consulted.
What to remember
nbtree is a balanced ordered Lehman-Yao tree: _bt_search descent, high keys and right-links for concurrent splits, leaf order for ranges and ORDER BY. Design composites with the leftmost-prefix rule. Treat index-only scans as “covering columns and all-visible heap pages,” and verify with EXPLAIN, not with hope.
Say it out loud
Close the page and explain this to someone who has not read it.
Can you explain nbtree as ordered leaves plus concurrent split machinery, and why index-only scan still depends on the visibility map, without stopping at "B-tree is a sorted tree"?
Then compare with a full answer
nbtree stores ordered leaf entries under routing pages and links siblings for range scans. During a split, a non-rightmost page's high key and btpo_next let _bt_moveright recover from a stale parent route; PostgreSQL still uses buffer locks, so this is not lock-free magic. Leaf entries identify heap TIDs but do not carry heap MVCC visibility. An Index Only Scan checks the visibility map for each candidate heap page and may perform heap fetches without becoming a different node. Design leading composite columns around real access patterns, then verify the chosen node and Heap Fetches with EXPLAIN (ANALYZE).
It has to connect
- Ordered leaf pages + sibling links: equality, ranges, ordered scans, and unique checks share one nbtree structure, not four index types.
- Split concurrency: Lehman-Yao-style high key + right-link lets a search recover when a page splits under it (_bt_split / _bt_search story), concurrency is not "locks make it simple."
- Index entries point at heap TIDs; they do not carry full MVCC visibility the way heap tuple headers do.
- Index-only scan needs the visibility map (all-visible pages) to skip heap fetches; covering INCLUDE is necessary but not sufficient if VM bits are not set.
- Bitmap Heap Scan can still win: many matching TIDs, need heap visibility checks, or planner cost model prefers bitmap + heap over pure IOS.
- Design: leading equalities and the first inequality usually bound the contiguous scan range; later columns can still be checked through the index. Match column order to real WHERE and ORDER BY patterns.
Where it usually stops short
"B-tree is a sorted tree for fast lookups." True and empty. No split/right-link story, no heap TID + visibility map constraint, no reason Bitmap Heap Scan still appears with a covering index.
Push further
- Why can one B-tree structure serve equality, range predicates, ORDER BY, and uniqueness checks?
- What do high keys and right-links buy you during a concurrent page split, and what fails if you ignore them in the story?
- EXPLAIN shows Bitmap Heap Scan (or heap fetches) even though INCLUDE columns cover the SELECT list, why might that still be correct?
Read the written reference6 sections · ~380 words · 1 runnable queryOne thing firstStructure (nbtree)Lehman-Yao concurrency: high key + right-linkWhen a B-tree wins (and when it does not)Index-only scans need the visibility mapDesigning composite keys that get used
One thing first
A B-tree wins because keys stay sorted on linked leaf pages, equality, ranges, ORDER BY, and uniqueness are all uses of that order. Composite indexes add the leftmost-prefix rule. Index-only scans add a second requirement: heap visibility, not only covering columns.
Structure (nbtree)
Implementation lives under src/backend/access/nbtree/. Descent starts in _bt_search; leaf scans continue with _bt_first / _bt_next. Each page ends with BTPageOpaqueData (sibling links, level, flags) in the page special space.
- Internal pages, separator keys and downlinks that route a search toward a leaf.
- Leaf pages, sorted keys with TIDs into the heap; siblings linked for range walks without returning to the root.
- Balance, height grows slowly;
bt_metaplevel is the concrete O(log n) depth.
Lehman-Yao concurrency: high key + right-link
nbtree follows Lehman and Yao: non-rightmost pages carry a high key, and every page has a right-link (btpo_next in BTPageOpaqueData). A search never needs to hold a parent latch while locking a child. If a concurrent _bt_split moved the target key rightward, the searcher compares against the high key and follows the right-link. That is how readers and inserters share the same index with little blocking, the design is documented in src/backend/access/nbtree/README.
When a B-tree wins (and when it does not)
- Wins: selective equality, range predicates, ORDER BY/LIMIT along the key, uniqueness.
- Composite order: leading equalities and the first inequality usually determine the tight contiguous scan range; later columns can still be checked through the index.
- Consider alternatives: GIN/GiST for containment or overlap, BRIN for large physically correlated tables, and a sequential scan for broad filters can be cheaper than nbtree.
Index-only scans need the visibility map
If every column the query needs is in the index (keys and optional INCLUDE payloads), the planner may choose Index Only Scan. The index still does not store MVCC visibility, so the executor checks the visibility map. All-visible heap pages skip the heap fetch; otherwise you pay heap access (shown as Heap Fetches) or the planner may pick another shape entirely.
ReferenceDDL pattern. Whether the planner chooses Index Only Scan depends on stats, cost, and visibility map, prove with EXPLAIN (ANALYZE).
SQL
-- Covering index: lookup key + non-key payload
CREATE INDEX idx_orders_cust ON orders (customer_id) INCLUDE (total_amount);
-- SELECT total_amount WHERE customer_id = $1 *can* become Index Only Scan after VACUUM sets all-visible bits.Designing composite keys that get used
- Composite column order, design leading columns around real equality/range/sort patterns; later keys may filter but often cannot narrow the initial range as much.
- INCLUDE, covering payloads without widening the sort key.
- VACUUM currency, keeps IOS honest via the visibility map.
- Validate before dropping,
idx_scan = 0only covers the current statistics window, and constraint indexes may be essential. Check dependencies and a representative workload first. - CREATE INDEX CONCURRENTLY on busy tables (separate lesson).
Check it against the source3 citations in postgres/postgres · file, symbol and line verified on REL_17_STABLE
src/backend/access/nbtree/nbtsearch.cVerified · REL_17_STABLE
Primary symbol: _bt_search · line 96
src/backend/access/nbtree/nbtinsert.cVerified · REL_17_STABLE
Primary symbol: _bt_split · line 1467
src/include/access/nbtree.hVerified · REL_17_STABLE
Primary symbol: BTPageOpaqueData · line 62
Anchored to postgres/postgres on REL_17_STABLE and cross-checked against the manual for PostgreSQL 15–18. Every query here was run and its output captured on a throwaway PostgreSQL 17.10 lab; corrections are noted inline. Ch. 67 B-Tree Indexes in the official docs →
Connected
Where this lesson sits
What comes before, after, and alongside it.
Part of these pathways
Same learning track
Finished a free lesson?
Pro opens the rest of the engine course
You felt one mechanism. Pro is the full bodies, interview depth, and the tracks that build on this session.