Struct BPlusTree

pub struct BPlusTree<S: NodeStore> { /* private fields */ }

B plus tree implementation, with following considerations:

1. Performance critical, for sweep like algo, the sweepline’s searching and updating is on hot path
2. Cursor support, after one search, it should be fairly easy to move next or prev without another search
3. Memory efficient, reduce mem alloc

Example

use sweep_bptree::{BPlusTree, NodeStoreVec};

// create a node_store with `u64` as key, `(f64, f64)` as value
let mut node_store = NodeStoreVec::<u64, (f64, f64)>::new();
let mut tree = BPlusTree::new(node_store);

// insert new value
assert!(tree.insert(3, (0., 0.)).is_none());

// update by insert again
assert_eq!(tree.insert(3, (1., 1.)).unwrap(), (0., 0.));

// remove the value
assert_eq!(tree.remove(&3).unwrap(), (1.0, 1.0));

assert!(tree.is_empty());

Example

Create multiple owned cursors

use sweep_bptree::{BPlusTree, NodeStoreVec};
let mut node_store = NodeStoreVec::<u64, (f64, f64)>::new();
let mut tree = BPlusTree::new(node_store);

for i in 0..100 {
    tree.insert(i, (i as f64, i as f64));
}

let cursor_0 = tree.cursor_first().unwrap();
let cursor_1 = tree.cursor_first().unwrap();

// remove the key 0
tree.remove(&0);

// cursor's value should be empty now
assert!(cursor_0.value(&tree).is_none());

// move to next
let cursor_next = cursor_0.next(&tree).unwrap();
assert_eq!(*cursor_next.key(), 1);
assert_eq!(cursor_next.value(&tree).unwrap().0, 1.);

// insert a new value to key 0
tree.insert(0, (100., 100.));
// now cursor_1 should retrieve the new value
assert_eq!(cursor_1.value(&tree).unwrap().0, 100.);

Implementations

impl<S: NodeStore> BPlusTree<S>

pub fn descend_visit<V>(&self, v: V) -> Option<V::Result>

where V: DescendVisit<S::K, S::V, S::Argument>,

visit the tree descendly through visitor v

impl<S: NodeStore> BPlusTree<S>

pub fn bulk_load(data: Vec<(S::K, S::V)>) -> Self

bulk load data into a new BPlusTree, the loaded tree’s leaf with fill rate 1.0 It requires data sorted by S::K

impl<S> BPlusTree<S>

where S: NodeStore,

pub fn new(node_store: S) -> Self

Create a new BPlusTree with the given NodeStore.

pub fn node_store(&self) -> &S

Gets a reference to the NodeStore that this BPlusTree was created with.

pub fn len(&self) -> usize

Returns the number of elements in the tree.

pub fn is_empty(&self) -> bool

Returns true if the tree contains no elements.

pub fn root_argument(&self) -> &S::Argument

Returns a reference to root argument

pub fn insert(&mut self, k: S::K, v: S::V) -> Option<S::V>

Insert a new key-value pair into the tree.

pub fn statistic(&self) -> &Statistic

pub fn get<Q: ?Sized + Ord>(&self, k: &Q) -> Option<&S::V>

where S::K: Borrow<Q>,

Get reference to value identified by key.

pub fn get_mut<Q: ?Sized + Ord>(&mut self, k: &Q) -> Option<&mut S::V>

where S::K: Borrow<Q>,

Get mutable reference to value identified by key.

pub fn first(&self) -> Option<(&S::K, &S::V)>

Returns first key-value pair in the map.

pub fn last(&self) -> Option<(&S::K, &S::V)>

Returns last key-value pair in the map.

pub fn remove<Q>(&mut self, k: &Q) -> Option<S::V>

where Q: Ord + ?Sized, S::K: Borrow<Q>,

delete element identified by K

pub fn iter(&self) -> Iter<'_, S>

Create an iterator on (&K, &V) pairs

pub fn into_iter(self) -> IntoIter<S>

Consume the tree and create an iterator on (K, &V) pairs

pub fn cursor_first(&self) -> Option<Cursor<S::K>>

Create an cursor from first elem

pub fn get_cursor(&self, k: &S::K) -> Option<(Cursor<S::K>, Option<&S::V>)>

Create an cursor for k

pub fn clear(&mut self)

Clear the tree

pub fn get_by_argument<Q>(&self, query: Q) -> Option<(&S::K, &S::V)>

where S::Argument: SearchArgument<S::K, Query = Q>,

get by argument

pub fn get_mut_by_argument<Q>(&mut self, query: Q) -> Option<&mut S::V>

where S::Argument: SearchArgument<S::K, Query = Q>,

get mut reference to value by argument’s Query

pub fn rank_by_argument<R>(&self, k: &S::K) -> Result<R, R>

where S::Argument: RankArgument<S::K, Rank = R>,

Get rank for argument

pub fn remove_by_argument<Q>(&mut self, query: Q) -> Option<(S::K, S::V)>

where S::Argument: SearchArgument<S::K, Query = Q>,

remove by argument

Trait Implementations

impl<S: Clone + NodeStore> Clone for BPlusTree<S>

where S::Argument: Clone,

fn clone(&self) -> BPlusTree<S>

Returns a duplicate of the value.

const fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<S: NodeStore> Drop for BPlusTree<S>

fn drop(&mut self)

Executes the destructor for this type.