Struct stellar_sql::index::btree::BPlusTree

pub struct BPlusTree<T> {
    pid: u32,
    node_type: NodeType,
    key_type: DataType,
    capacity: usize,
    ptr_size: usize,
    key_size: usize,
    row_ptr_size: Option<usize>,
    ptrs: Vec<u32>,
    keys: Vec<T>,
    rows: Option<Vec<(u32, usize)>>,
    nodes: Vec<Box<Self>>,
    height: u32,
}

B+ Tree

Internal Node

+---------------------------+
|P0|K1||P1|K1|| ...  ||Pn|Kn|
+---------------------------+
K: Key Value
P(n-1): Pointer to the page with Kn-1 <= Value < Kn

Leaf Node

+-----------------------------------+
|P0||R0|K0||R1|K1|| ...  ||Rn|Kn||P1|
+-----------------------------------+
K: Key Value
R: Record pointer
P0: Previous page pointer
P1: Next page pointer

Fields

pid: u32

node_type: NodeType

key_type: DataType

capacity: usize

ptr_size: usize

key_size: usize

row_ptr_size: Option<usize>

ptrs: Vec<u32>

keys: Vec<T>

rows: Option<Vec<(u32, usize)>>

nodes: Vec<Box<Self>>

height: u32

Methods

impl<T: PartialOrd> BPlusTree<T>

fn node_type(&self) -> &NodeType

fn find_ptr(arr: &Vec<T>, left: usize, right: usize, val: T) -> usize

find_ptr: upper-bounded binary searching the key to find the page

Internal Node:

+-------------+
|P0| Key=2 |P1|
+-------------+

• Find Key=1 -> P0
• Find Key=2 -> P1
• Find Key=3 -> P1

Trait Implementations

impl<T: PartialOrd> Tree<T> for BPlusTree<T>

fn new(
    pid: u32,
    node_type: NodeType,
    key_type: DataType,
    ptr_size: usize,
    key_size: usize,
    row_ptr_size: Option<usize>
) -> Box<Self>

fn height(&self) -> u32

fn insert(&mut self, val: T)

fn delete(&mut self, val: T)

fn search(&self, val: T) -> (u32, usize)