DELETE & UPDATE Execution
Implementing row modification and removal in a fixed-layout B+Tree
Implement the DELETE and UPDATE SQL statements by navigating the B+Tree to the target row, shifting elements to remove records, or mutating the payload in-place.
Core Concepts
- Extending the Query Planner to support DeleteNode and UpdateNode.
- Removing cells from a B+Tree leaf node and using memmove to shift the remaining cells left, closing the gap.
- Updating the payload (name, email) of a fixed-size row directly in memory.
- Updating the root cell count when a deletion occurs.
Completing the CRUD Cycle
So far, our database supports Create (INSERT) and Read (SELECT). In this stage, we will implement the final pieces of the puzzle: Update and Delete.
Because we are doing this before introducing variable-length strings and slotted pages (which happen in Part 2), our implementation will be surprisingly simple! Since every row in our database currently takes exactly 508 bytes, and each cell (key + row) takes exactly 512 bytes, we can manipulate them like a standard array in memory.
DELETE: Shifting Cells
When a user executes DELETE FROM users WHERE id = 3, the engine performs the following steps:
- Find: Use our existing
btree_find(3)function to locate the exact leaf page and cell index. - Shift: Remove the cell by sliding all subsequent cells to the left.
- Decrement: Update the
num_cellscounter in the leaf page header.
Rendering diagram...
In C, this left-shift is accomplished efficiently using memmove, which safely copies overlapping memory regions.
[!NOTE] What about B-Tree Underflow? In a complete B-Tree implementation, if a node's occupancy drops below 50% after a deletion, it should be merged with a sibling node (Underflow). However, in many real-world databases (like PostgreSQL), nodes are rarely merged immediately because doing so is computationally expensive and locks large portions of the tree. Instead, they rely on background processes (like
VACUUM) to reclaim space later. To keep things simple, we will skip node merging for now.
UPDATE: In-Place Mutation
When a user executes UPDATE users SET name = 'bob' WHERE id = 3, the process is even simpler. Because our rows are fixed-size, the new data is guaranteed to fit in the exact same slot as the old data.
- Find: Locate the cell using
btree_find(3). - Deserialize: Read the existing row data into memory.
- Modify: Change the
namefield. - Serialize: Write the modified row back to the exact same byte offset in the leaf page.
By executing this in-place, the B-Tree structure is completely unaffected. No cells need to shift, and no nodes need to split!
The Volcano Integration
Remember the Volcano Model we implemented in Stage 11? DELETE and UPDATE fit perfectly into this architecture. The Query Planner simply generates a DeleteNode or UpdateNode instead of an IndexScan or SeqScan.
When the executor loop runs plan->next(), these modification nodes will locate the target row, perform the mutation, and return the modified row (or a success indicator) to the user.
Conceptual Execution Algorithms
DELETE Execution
To delete a row, the engine must find its exact position in the B-Tree leaf and remove it.
- [1]The Volcano Executor receives a DeleteNode with the target id.
- [2]Call btree_find(id) to obtain a cursor pointing to the exact leaf page and cell_num.
- [3]If the key is not found, return a "Row not found" error.
- [4]Calculate the byte offset of the cell to delete.
- [5]Use memmove to shift all cells from (cell_num + 1) to (num_cells - 1) left by one cell width (ROW_SIZE + 4).
- [6]Decrement num_cells in the leaf node header.
- [7]Flush the modified page to disk.
UPDATE Execution
To update a row's data without changing its primary key, the engine modifies the payload in-place.
- [1]The Volcano Executor receives an UpdateNode with the target id and the new values.
- [2]Call btree_find(id) to obtain a cursor to the target cell.
- [3]Deserialize the current row from the cell.
- [4]Overwrite the requested fields (e.g., name or email) with the new values.
- [5]Serialize the row back into the exact same memory location on the leaf page.
- [6]Flush the modified page to disk.