hematite/btree/
mod.rs

1//! Generic B-tree module over opaque byte keys and values.
2//!
3//! This module is the structural layer between `storage` and `catalog`. It knows how to maintain
4//! ordered trees on top of pages, but it does not know what keys or values mean.
5//!
6//! Public surfaces:
7//! - [`ByteTreeStore`] / [`ByteTree`] / [`ByteTreeCursor`] for raw byte keys and values;
8//! - [`TypedTreeStore`] / [`TypedTree`] / [`TypedTreeCursor`] for typed callers using codecs;
9//! - [`KeyValueCodec`] as the only typed boundary.
10//!
11//! Internal surfaces:
12//! - node serialization and validation;
13//! - split / merge / rebalance logic;
14//! - value overflow handling;
15//! - tree validation and page-space accounting.
16//!
17//! This is the generic data-structure half of the future fork point.
18
19pub mod bytes;
20pub mod codec;
21pub(crate) mod cursor;
22pub(crate) mod index;
23pub(crate) mod node;
24pub(crate) mod tree;
25pub mod typed;
26pub(crate) mod value_store;
27
28pub use crate::storage::{JournalMode, PageId, PagerIntegrityReport};
29pub(crate) use bytes::ByteTreeStoreSnapshot;
30pub use bytes::{ByteTree, ByteTreeCursor, ByteTreeStore};
31pub use codec::{KeyValueCodec, RawBytesCodec};
32pub use tree::TreeSpaceStats;
33pub use typed::{TypedTree, TypedTreeCursor, TypedTreeStore};
34
35pub const BTREE_ORDER: usize = 100;
36
37#[derive(Debug, Clone, Copy, PartialEq, Eq)]
38pub enum NodeType {
39    Internal,
40    Leaf,
41}
42
43#[derive(Debug, Clone)]
44pub struct BTreeKey {
45    pub data: Vec<u8>,
46}
47
48impl BTreeKey {
49    pub fn new(data: Vec<u8>) -> Self {
50        Self { data }
51    }
52
53    pub fn as_bytes(&self) -> &[u8] {
54        &self.data
55    }
56}
57
58impl PartialEq for BTreeKey {
59    fn eq(&self, other: &Self) -> bool {
60        self.data == other.data
61    }
62}
63
64impl Eq for BTreeKey {}
65
66impl PartialOrd for BTreeKey {
67    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
68        Some(self.cmp(other))
69    }
70}
71
72impl Ord for BTreeKey {
73    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
74        self.data.cmp(&other.data)
75    }
76}
77
78#[derive(Debug, Clone, PartialEq)]
79pub struct BTreeValue {
80    pub data: Vec<u8>,
81}
82
83impl BTreeValue {
84    pub fn new(data: Vec<u8>) -> Self {
85        Self { data }
86    }
87
88    pub fn as_bytes(&self) -> &[u8] {
89        &self.data
90    }
91}
92
93#[cfg(test)]
94mod tests;
hematite/btree/mod.rs

hematite/btree/
mod.rs
