vibesql-storage 0.2.0

Storage engine for vibesql SQL database
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

//! B+ Tree Node Structures
//!
//! This module defines the core data structures for B+ tree nodes:
//! - Type aliases for keys and row IDs
//! - Internal node structure
//! - Leaf node structure

use vibesql_types::SqlValue;

use super::super::NULL_PAGE_ID;
use crate::page::PageId;

/// Type alias for multi-column keys (compatible with existing IndexData)
pub type Key = Vec<SqlValue>;

/// Type alias for row identifiers (row index in table)
pub type RowId = usize;

/// Internal node in the B+ tree
///
/// Internal nodes store keys and page IDs pointing to child nodes.
/// They do not store actual data values, only routing information.
#[derive(Debug, Clone)]
pub struct InternalNode {
    /// Page ID of this node
    pub page_id: PageId,
    /// Separator keys (length = num_children - 1)
    pub keys: Vec<Key>,
    /// Child page IDs (length = num_children)
    pub children: Vec<PageId>,
}

impl InternalNode {
    /// Create a new internal node
    pub fn new(page_id: PageId) -> Self {
        InternalNode { page_id, keys: Vec::new(), children: Vec::new() }
    }

    /// Check if the node is full (needs splitting)
    ///
    /// This method will be used in Part 2b for tree-level insert operations
    #[allow(dead_code)]
    pub fn is_full(&self, degree: usize) -> bool {
        self.children.len() >= degree
    }
}

/// Leaf node in the B+ tree
///
/// Leaf nodes store the actual key-value pairs (key -> Vec<row_id>).
/// Each key can map to multiple row IDs to support non-unique indexes.
/// They maintain a doubly-linked list structure via next_leaf and prev_leaf
/// for efficient forward and reverse range scans.
#[derive(Debug, Clone)]
pub struct LeafNode {
    /// Page ID of this node
    pub page_id: PageId,
    /// Key-value entries (sorted by key), supporting multiple row_ids per key for non-unique
    /// indexes
    pub entries: Vec<(Key, Vec<RowId>)>,
    /// Page ID of next leaf node (for forward range scans), or NULL_PAGE_ID
    pub next_leaf: PageId,
    /// Page ID of previous leaf node (for reverse range scans), or NULL_PAGE_ID
    pub prev_leaf: PageId,
}

impl LeafNode {
    /// Create a new leaf node
    pub fn new(page_id: PageId) -> Self {
        LeafNode { page_id, entries: Vec::new(), next_leaf: NULL_PAGE_ID, prev_leaf: NULL_PAGE_ID }
    }

    /// Check if the node is full (needs splitting)
    ///
    /// This method will be used in Part 2b for tree-level insert operations
    #[allow(dead_code)]
    pub fn is_full(&self, degree: usize) -> bool {
        self.entries.len() >= degree
    }

    /// Check if node is underfull (needs merging)
    ///
    /// This method will be used in Part 2b for tree-level delete operations
    #[allow(dead_code)]
    pub fn is_underfull(&self, degree: usize) -> bool {
        self.entries.len() < degree / 2
    }
}