b_tree/
lib.rs

1//! A persistent B+ tree using [`freqfs`].
2//!
3//! See the `examples` directory for usage examples.
4
5use std::borrow::Borrow;
6use std::cmp::Ordering;
7use std::fmt;
8
9use collate::{Collate, CollateRef};
10
11mod group;
12mod node;
13mod range;
14mod tree;
15
16pub use node::{Block, Node};
17pub use range::Range;
18pub use tree::{BTree, BTreeLock, BTreeReadGuard, BTreeWriteGuard, Keys};
19
20pub use collate;
21
22const NODE_STACK_SIZE: usize = 32;
23
24/// The size limit for a [`Key`] in a stream to be stack-allocated
25pub const KEY_STACK_SIZE: usize = 32;
26
27/// The type of item in a stream of B+Tree keys
28pub type Key<V> = smallvec::SmallVec<[V; KEY_STACK_SIZE]>;
29
30/// A collator used by a B+Tree
31#[derive(Copy, Clone)]
32pub struct Collator<C> {
33    value: C,
34}
35
36impl<C> Collator<C> {
37    /// Construct a new [`Collator`] for a B+Tree from an existing `value` collator.
38    pub fn new(value: C) -> Self {
39        Self { value }
40    }
41
42    /// Borrow the value collator used by this key [`Collator`].
43    pub fn inner(&self) -> &C {
44        &self.value
45    }
46}
47
48impl<C: Collate> Collator<C> {
49    fn cmp_slices<L, R>(&self, left: &[L], right: &[R]) -> Ordering
50    where
51        L: Borrow<C::Value>,
52        R: Borrow<C::Value>,
53    {
54        for i in 0..Ord::min(left.len(), right.len()) {
55            match self.value.cmp(left[i].borrow(), right[i].borrow()) {
56                Ordering::Equal => {}
57                ord => return ord,
58            }
59        }
60
61        Ordering::Equal
62    }
63}
64
65impl<C: Collate> Collate for Collator<C> {
66    type Value = Vec<C::Value>;
67
68    fn cmp(&self, left: &Self::Value, right: &Self::Value) -> Ordering {
69        self.cmp_slices(left, right)
70    }
71}
72
73impl<C: Collate> CollateRef<[C::Value]> for Collator<C> {
74    fn cmp_ref(&self, left: &[C::Value], right: &[C::Value]) -> Ordering {
75        self.cmp_slices(left, right)
76    }
77}
78
79impl<C: Collate> CollateRef<Key<C::Value>> for Collator<C> {
80    fn cmp_ref(&self, left: &Key<C::Value>, right: &Key<C::Value>) -> Ordering {
81        self.cmp_slices(left, right)
82    }
83}
84
85impl<C> PartialEq for Collator<C>
86where
87    C: Collate,
88{
89    fn eq(&self, other: &Self) -> bool {
90        self.value == other.value
91    }
92}
93
94impl<C> Eq for Collator<C> where C: Collate {}
95
96/// The schema of a B+Tree
97pub trait Schema: Eq + fmt::Debug {
98    /// The type of error returned by [`Schema::validate_key`]
99    type Error: std::error::Error + Send + Sync + 'static;
100
101    /// The type of value stored in a B+Tree's keys
102    type Value: Default + Clone + Eq + Send + Sync + fmt::Debug + 'static;
103
104    /// Get the maximum size in bytes of a leaf node in a B+Tree with this [`Schema`].
105    fn block_size(&self) -> usize;
106
107    /// Get the number of columns in this [`Schema`].
108    fn len(&self) -> usize;
109
110    /// Get the order of the nodes in a B+Tree with this [`Schema`].
111    fn order(&self) -> usize;
112
113    /// Return a validated version of the given `key`, or a validation error.
114    fn validate_key(&self, key: Vec<Self::Value>) -> Result<Vec<Self::Value>, Self::Error>;
115}
b_tree/lib.rs

b_tree/
lib.rs
