B-Tree Indexing Enhanced Simulator
Test database B-Tree indexing as explicit runtime components with parent-owned input ports, child injection, routed connector messages, buffer pool caching, and query planning.
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
Modern database systems rely on page-based architectures where data is moved between storage and memory in fixed-size blocks (pages). Evaluating index performance requires tracking the flow of physical and logical page reads across multiple runtime actors.
The core mental model is a message-routing pipeline. A client’s SQL query is evaluated by a Planner, which consults the Buffer Pool Cache. If requested pages are cached in memory (cache hit), reads are completed instantly. If not (cache miss), page read requests are sent to disk. Traversing the B+ Tree Index Parent requires stepping through internal page children using separator keys until reaching a leaf page, which contains pointers to the actual table blocks inside the Heap Store Parent.
Components and Why They Exist
Query Client
Represents the application context making database calls and receiving result rows. Submits SELECT or INSERT messages into the query planner and handles the final response payloads. In the demo, watch the in-flight query messages emitted by the client to begin lookup, range scan, or insert operations.
Query Planner & Buffer Pool
Acts as the control center, choosing the cheapest execution path and caching hot data pages. Evaluates query predicates, checks the Least Recently Used (LRU) buffer pool for pages, and coordinates reads to the index or heap. In the demo, observe buffer pool hit/miss metrics update in real time as pages are fetched, and watch hot pages move to the head of the cache list.
B+ Tree Index Parent
Provides a logarithmic routing structure to bypass scanning the entire table. Receives lookup requests and traverses internal nodes (root, intermediate) using separator keys to find target leaf pages. In the demo, watch key traversal descend through child index pages, and see page split animations when insertions exceed leaf capacities.
Heap Store Parent
Manages physical table pages (heap blocks) where actual row data is stored. Handles sequential scans across all heap pages, or performs point lookups using row identifiers fetched from index leaf nodes. In the demo, watch heap pages being read sequentially during table scans, or accessed randomly on index fetches.
Edge Cases and Misconceptions
- Index Bloat and Fragmentation: A common misconception is that deleting rows automatically shrinks index files. Relational databases do not shrink pages on deletion; instead, they leave empty slots (bloat). Frequent inserts and deletes lead to page splits, resulting in fragmented, low-occupancy nodes that degrade range scan performance.
- Buffer Pool Thrashing: When the active database working set exceeds the buffer pool’s cache capacity, the cache repeatedly evicts and re-reads pages from disk. This condition, called thrashing, causes query latencies to spike dramatically.
- Sequential Scans Can Beat Index Scans: If a query requests a large portion of a table’s rows, using an index scan can be slower than a sequential scan. This is because the sequential scan performs fast, contiguous sequential reads, whereas the index scan must perform slow, random page reads for each record.
- Page Splits Cascade Upward: Page splits are not isolated to leaves. If a leaf split promotes a separator key to a parent page that is also full, the parent splits as well. This cascading split can propagate all the way to the root page, which increases the height of the entire index tree.
Common Questions
How does the Buffer Pool Cache operate?
The buffer pool maintains a cache of hot index and heap pages in memory using an eviction policy like Least Recently Used (LRU). When a query requests a page, the database first checks the buffer pool. A cache hit avoids disk I/O, while a cache miss requires reading the page from disk and loading it into the buffer pool, potentially evicting another page.
Why do B-tree inserts cause cascading splits?
When a B+ tree node reaches its maximum key capacity during an insertion, it must split to maintain sorted order and leaf size invariants. The split requires promoting a separator key to the parent node. If the parent node is also at capacity, it splits and promotes a key to its parent, cascading upward and potentially splitting the root to increase tree height.
When are sequential scans faster than index scans?
Sequential scans are faster when a query retrieves a large portion of the table rows (low selectivity). Under an index scan, every matching record requires a random look-up to fetch the row from the heap, which is slower than sequentially reading contiguous heap pages from disk.
What is the role of separator keys in a B+ tree?
Separator keys are stored in the internal (non-leaf) pages of a B+ tree. They serve as routing guides, defining the range of keys stored in lower-level child pages. Because internal pages only store separator keys and child pointers (no actual data rows or row pointers), they achieve high fanout, keeping the tree shallow.
How does the tree order (fanout) affect database index lookup and write costs?
A larger tree order (fanout) allows each page to hold more keys, which reduces the height of the tree and requires fewer page lookups to reach a leaf. However, larger pages increase the CPU cost of searching within a page and make page splits more expensive due to the larger memory copy operations.