Skip to content

016-btree-implementation.md

Latest commit

 

History

History
44 lines (30 loc) · 4.2 KB

016-btree-implementation.md

File metadata and controls

44 lines (30 loc) · 4.2 KB
Raw

Entry 16: B+-Tree Implementation - Search and Insert

Objective

To implement a fully functional B+-Tree index from scratch. This is the core component of Phase 4, designed to provide fast, O(log N) access to tuples, avoiding slow sequential scans. This implementation includes the logic for searching, inserting, and the complex mechanics of node splitting and tree balancing.

Key Concepts & Design Decisions

B+-Tree Architecture

The B+-Tree is a self-balancing tree data structure optimized for disk-based storage. Our implementation is built upon the existing storage layer (Page, BufferPoolManager).

  • Node-as-Page: Every node in the tree is a single 4KB Page, ensuring all I/O is page-aligned and managed by the BufferPoolManager. This provides automatic caching of "hot" tree nodes, like the root.
  • High Fanout: By packing hundreds of keys and pointers into each page, the tree remains exceptionally "short and fat." A tree of height 4-5 can index hundreds of millions of records, meaning most lookups require only 4-5 disk I/Os in the worst case.
  • Internal vs. Leaf Nodes:
    • Internal Nodes act as "signposts," containing only keys to guide the search and pointers (page IDs) to child nodes.
    • Leaf Nodes store the actual index entries: (Key, Value) pairs. In our system, the value is the TupleID (physical address) of the row. All data resides exclusively in the leaves.
  • Sibling Pointers: All leaf nodes are connected in a doubly-linked list, which is essential for enabling efficient range scans in the future.

The Insertion Algorithm and Balancing

The most complex part of the implementation is the insertion logic, which guarantees the tree remains perfectly balanced.

  • Recursive Traversal: Insertion is handled via a recursive insertInto method. The function traverses down the tree to find the correct leaf for the new key.
  • Node Splitting: When an attempt is made to insert into a full node (either leaf or internal), a split operation is triggered:
    1. A new page is allocated for a sibling node.
    2. The keys (and pointers/values) from the full node, plus the new key, are distributed evenly between the original node and the new sibling. We standardized on a symmetric split (mid = size / 2) for both node types for consistency.
    3. A key is promoted up to the parent node to act as a new signpost.
  • Recursive Promotion: This promotion is handled on the way back up the recursion. If inserting the promoted key causes the parent to be full, the parent also splits, promoting a key to its parent. This can cascade all the way to the root.
  • Tree Growth: If the root node itself splits, a new root is created, and the tree's height increases by one. The insert method handles this special case.

Implementation and Testing Insights

  • Node Abstraction: BTreeNode, BTreeInternalNode, and BTreeLeafNode classes were created to provide a clean API over the raw byte layout of a Page, handling all offset calculations.
  • Constants for Testing: The node capacities (MAX_LEAF_KEYS, MAX_INTERNAL_KEYS) were set to a small, public constant (10). This is an artificial limit that makes it feasible to trigger and test the complex splitting logic with a small number of insertions.
  • White-Box Testing: A comprehensive BTreeTest was crucial. A simple "black-box" test that only checked if search worked was insufficient. The final test suite uses a "white-box" approach, inspecting the internal state of the tree (e.g., checking if the root is an internal node, checking the tree height) to provide high confidence that the splitting and balancing logic is correct.

Next Steps

With search and insert implemented, the B+-Tree is now functional. The next steps for our indexing phase are:

  1. Deletion: Implement the delete logic, which involves handling underfull nodes by either borrowing from a sibling or merging with one.
  2. IndexScanExecutor: Build a new executor that can use the B+-Tree's search method to perform fast point lookups.
  3. Planner Integration: Enhance the Planner to be "cost-aware," allowing it to choose between a SeqScan and an IndexScan to execute a query.