B+Tree Search & SELECT Execution
Implementing logarithmic leaf node search, sorted primary key insertion, and cursor-driven table scans
Upgrade B+Tree leaf nodes to enforce strictly sorted primary key insertion via binary search, catch duplicate key violations, and implement cursor-driven SELECT scan iteration.
Core Concepts
- Executing logarithmic O(log N) binary search across tightly packed leaf node cells in RAM
- Enforcing sorted cell ordering by dynamically shifting overlapping memory structures
- Detecting and gracefully rejecting duplicate primary key insertion attempts
- Designing the Table Cursor abstraction to drive sequential pull-based SELECT query executions
Why Sorted Insertion is Critical for B+Trees
In our previous stage, incoming cells were appended directly to the end of the leaf page in the chronological order of arrival. While fast for initial writing, unsorted pages degrade table searches into linear O(N) scans. Furthermore, when an overflowing B+Tree leaf node must split in two during Stage 8, calculating a clean median dividing line is impossible unless cells are maintained in strictly sorted numerical order!
When inserting an out-of-order key (for example, inserting Key 2 into a page currently holding Key 1 and Key 3), our engine utilizes binary search to locate Index #1 as the insertion target. It then safely shifts all cells from Index #1 onward to Index #2, opening a pristine, gapless 64-byte insertion slot:
BEFORE INSERTING KEY 2 (Unshifted Page Memory):
┌──────────┬───────────┬───────────┬────────────────────────────────────┐
│ HEADER │ CELL #0: │ CELL #1: │ (Unoccupied free memory space) │
│ cells=2 │ Key = 1 │ Key = 3 │ │
└──────────┴───────────┴───────────┴────────────────────────────────────┘
│
▼ (Memory shift rightwards by 1 cell / 64 bytes)
AFTER MEMORY SHIFT & INSERTION (Sorted Page Memory):
┌──────────┬───────────┬───────────┬───────────┬────────────────────────┐
│ HEADER │ CELL #0: │ CELL #1: │ CELL #2: │ (Remaining free space) │
│ cells=3 │ Key = 1 │ Key = 2 │ Key = 3 │ │
└──────────┴───────────┴───────────┴───────────┴────────────────────────┘
Declarative Mermaid Memory Shift View
Rendering diagram...
The Table Cursor Abstraction
To cleanly divorce high-level query planning from low-level page math, relational database engines utilize an abstraction called a Table Cursor. Rather than letting the SELECT execution loop directly tamper with raw Buffer Pool pointers, a Cursor acts as a logical navigator pointing to a distinct record position:
- Start of Table: Positioned at Page #0, Cell #0.
- Cursor Advance: Moves forward by incrementing the cell index. In future stages, when a cursor reaches the final cell of a leaf page, it automatically follows the node's sibling pointer to transition smoothly onto the next sequential leaf!
- End of Table Detection: Reaches completion when the cursor attempts to read a cell index matching the total number of valid records in the active table or node.
Using cursors guarantees that your SELECT * FROM users; implementation remains perfectly stable and decoupled from internal memory layouts, even as your B+Tree begins expanding across hundreds of interconnected memory pages!
Conceptual Execution Algorithms
Logarithmic Binary Search & Duplicate Detection
To locate an existing primary key or determine the precise insertion slot for a new row without checking every cell linearly, execute binary search within the leaf page.
- [1]Establish search bounds with left index initialized to 0 and right index initialized to num_cells - 1.
- [2]While left index is less than or equal to right index, compute the midpoint cell index (left + (right - left) / 2).
- [3]Extract the 32-bit primary key stored at the midpoint cell offset inside the leaf node buffer.
- [4]If the target key equals the midpoint key, the key is found! Return this exact cell index (or flag an ERROR if trying to insert a duplicate).
- [5]If the target key is less than the midpoint key, narrow the search window by shifting the right boundary to midpoint - 1.
- [6]If the target key is greater than the midpoint key, advance the left boundary to midpoint + 1.
- [7]When loop terminates without a match, the current left boundary index represents the exact sequential insertion point where the new key belongs!
Sorted Cell Insertion via Memory Shift
When inserting a primary key that belongs somewhere in the middle of existing cells (e.g., inserting key 2 when keys 1 and 3 already exist), existing cells must shift rightwards.
- [1]Execute binary search on the target leaf node to determine the destined cell index for the incoming row.
- [2]If the target index already contains the exact same key, abort immediately and report a duplicate primary key error.
- [3]If the insertion index is strictly less than the current num_cells, calculate the total number of bytes currently occupied by all subsequent cells to the right.
- [4]Shift those subsequent cells rightward by exactly one full cell dimension (64 bytes) using an overlapping memory move operation.
- [5]Deposit the new 4-byte primary key and 60-byte serialized row payload into the newly vacated sequential cell slot and increment num_cells.
Table Cursor & SELECT Query Scanning
When evaluating a 'SELECT * FROM users;' query, the executor iterates sequentially over table records without exposing raw page pointers directly to the SQL engine.
- [1]Initialize a table Cursor struct positioned at the very first record (Page 0, Cell Index 0).
- [2]Evaluate if the cursor has reached the end of table condition (when current cell index equals the node's num_cells).
- [3]While the end-of-table flag is false, fetch the pointer to the current cell via the Pager.
- [4]Pass the payload section of the current cell to Row Deserialization (Stage 4) to reconstruct logical text fields.
- [5]Print the formatted table header, output the reconstructed row attributes, advance cursor index by +1, and print total row counts at termination.