Database Indexing (B-Tree) Visualization
Walk through how a B+ tree database index routes point lookups, supports range scans through leaf links, handles page splits, uses the buffer pool, and competes with sequential scans.
Continue with the guided workspace
Use the paired workspace to connect this guide's mental model with live component state, visible signals, and the outcome each step or scenario is meant to prove.
Mental Model
A database table without an index is a heap: an unordered collection of data pages. Searching for a specific record requires a Sequential Scan, reading every page from disk. An index acts as a structured search pathway to bypass this linear cost.
The B+ tree index is the foundation of relational database retrieval. It organizes sorted keys into a hierarchy of pages. Traversal starts at a single Root Page and follows separator keys through intermediate Internal Pages, narrowing the search space at each level. At the bottom, Leaf Pages store sorted keys alongside row pointers to the Heap Pages (the actual table storage). Leaf pages are also linked horizontally, allowing the database to execute range queries by descending to the first match and scanning sideways without re-traversing the tree.
For parameter-driven experiments, the B-Tree Indexing simulator sandbox is also available.
Components and Why They Exist
SQL Query and Planner
The SQL query describes the developer’s data request, while the planner estimates the cheapest path to execute it. The planner decides whether to use a Sequential Scan, an Index Scan, or an Index-Only Scan based on statistics like key cardinality and index coverage. Depending on the SELECT predicate selectivity, the planner card switches between an index-driven traversal and a full sequential heap sweep.
Root and Internal Pages
The root and internal pages guide index traversal efficiently from the top of the tree down to the leaves. They store separator keys that act as range boundaries, routing each read request to the appropriate child page without storing actual table rows. Search keys step down from the root through internal nodes as boundary comparisons narrow the active branch at each level.
Leaf Pages
The leaf pages store sorted index keys alongside Tuple ID (TID) pointers to the actual table rows. Sibling pointers connect adjacent leaf pages horizontally, permitting sequential sideways traversal during range scans. Once a range query lands on the starting leaf key, traversal follows the horizontal leaf-to-leaf links without climbing back up to the root or internal nodes.
Heap Pages
The heap pages serve as the primary storage location for the table’s complete, unordered row contents. The storage engine retrieves specific heap blocks via random lookups using the row identifiers found in index leaf entries. After a leaf lookup resolves a Tuple ID, a targeted fetch arrow jumps to the corresponding heap block to read the full row payload.
Buffer Pool
The buffer pool acts as an in-memory cache for frequently accessed index and table pages. It caches disk pages in RAM, turning physical disk reads into fast memory hits and accelerating index traversal. Hot upper-tree nodes like the root page stay resident in the buffer pool card, scoring memory hits that skip slow disk-fetch animations.
Page Split Path
The page split path handles new inserts when a target leaf or internal node exceeds its key capacity while preserving sorted B+ tree invariants. The storage engine splits an over-full page into two sibling pages, updates their horizontal links, and promotes a separator key into the parent page. Inserting into a full leaf splits the node in two and pushes a middle separator key upward into the parent page.
Edge Cases and Misconceptions
- B-tree Indexes Are Not Always Faster: For broad ranges or low-selectivity queries, scanning through the index and performing random I/O heap fetches is more expensive than sequentially reading the table. In such cases, the planner will choose a Sequential Scan.
- Index-Only Scan Limitations: While an Index-Only Scan is faster because it avoids heap reads, it is not always possible. The index must cover all columns in the SELECT clause, and the database must verify row visibility using the table’s visibility map.
- Cascading splits: A leaf page split is usually cheap, but if parent internal pages are also full, the split cascades upward. In extreme cases, a split at the bottom can cascade all the way to the root, increasing the height of the entire tree.
- Page bloat and fragmentation: Deleting rows does not automatically shrink index files. Instead, it leaves empty slots (bloat) in leaf pages. Over time, frequent updates and splits lead to index fragmentation, which reduces scan efficiency.
Common Questions
Why do databases still choose sequential scans sometimes?
For broad ranges or low-selectivity predicates, many random heap fetches through an index can cost more than a sequential sweep of heap pages.
What happens during a B-tree page split?
When a page exceeds its capacity limit during an insert, the database splits it into two sorted sibling pages, moves half of the keys to the new page, and inserts the middle key as a separator key in the parent index page. If the parent page is also full, this split cascades upwards, potentially creating a new root page.
Why does a B+ tree store user data only in leaf pages, unlike a standard B-tree?
Storing data or row pointers only in the leaves (and only separator keys in the internal pages) increases the fanout of internal pages. This allows the tree to remain very shallow (typically 3-4 levels for millions of rows) and enables fast horizontal range scans through linked leaf pages.
What is the difference between an Index Scan and an Index-Only Scan?
An Index Scan locates row pointers in the index and must fetch the remaining columns from the heap (table) pages. An Index-Only Scan retrieves all requested columns directly from the index keys, skipping the heap fetch entirely, though it must still consult a visibility map to ensure transaction isolation.
How does the buffer pool affect database index performance?
Traversing a B+ tree requires reading multiple index pages. The buffer pool caches these hot pages (like the root and upper internal nodes) in memory, converting slow disk reads into fast memory access and ensuring that traversal does not saturate storage I/O.