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 requires stepping through internal pages using separator keys until reaching a leaf page, which contains pointers to the actual table blocks inside the Heap Store.
Components and Why They Exist
Query Client
The query client represents the application context making database calls and receiving result rows. It submits SELECT or INSERT messages into the query planner and processes the returned payloads. Each lookup, range scan, or insert operation begins as an in-flight query particle leaving the client port.
Query Planner & Buffer Pool
The query planner and buffer pool act as the execution control center, choosing the cheapest access path and caching hot data pages in memory. Together, they evaluate query predicates, check the Least Recently Used (LRU) buffer pool for cached pages, and coordinate reads to the index or heap. Real-time hit and miss counters update on the buffer pool card as hot pages move to the head of the LRU cache list.
B+ Tree Index
The B+ tree index provides a logarithmic routing structure so queries can locate keys without scanning the entire table. It receives lookup requests and traverses internal nodes (root and intermediate pages) using separator keys to reach target leaf pages. Search particles descend through the internal index pages, and insertions that exceed leaf capacity trigger visible page-split animations.
Heap Store
The heap store manages the physical table pages (heap blocks) where actual row data is stored on disk. It executes sequential scans across all heap pages or performs point lookups using row identifiers fetched from index leaf nodes. Full table scans sweep sequentially across every heap block, whereas index-backed queries jump directly to the referenced heap page.
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.