Database Indexing (B-Tree) Visualization

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 query describes the developer’s request, while the planner estimates the cost of executing 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. In the demo, observe the planner choosing between index-driven paths and sequential heap sweeps depending on the select query parameters.

Root and Internal Pages

To guide the index traversal efficiently from the top down. Store separator keys that act as range markers. Traversing these pages routes the read request to the correct lower-level page without storing actual table records. In the demo, notice that follow the search keys down the tree, watching how comparison checks narrow the routing path at each index page.

Leaf Pages

To store the sorted keys alongside pointers to the actual table rows. Keep keys in sorted order. Sibling links connect adjacent leaf pages, permitting sequential sideways traversal for range scans. In the demo, watch range scans follow leaf-to-leaf sibling pointers without having to return to root/internal pages.

Heap Pages

The primary storage location for the table’s complete row contents. Store unordered database rows. They are retrieved via random lookups using the row identifiers found in index leaf entries. In the demo, watch the index fetch operation access the heap pages to read the full rows after locating their references in the leaf.

Buffer Pool

To act as an in-memory cache for frequently used index and table pages. Caches disk pages in RAM, turning physical disk reads into logical memory hits and improving traversal speeds. In the demo, observe how hot pages (like the root page) score cache hits in the buffer pool, preventing disk fetch animations.

Page Split Path

To handle new inserts while maintaining the sorted B+ tree invariants. Splits an over-full page into two, updates sibling pointers, and inserts a separator key into the parent page. In the demo, observe how an insert triggers page splitting and how separator updates cascade back up the parent nodes.

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.