Struct BPlusTree 

pub struct BPlusTree<K, V> { /* private fields */ }

An ordered map backed by a B+tree.

Keys are kept in sorted order across a tree of fixed-fan-out nodes. Point operations — get, insert, contains_key — run in time logarithmic in the number of entries: each level is one binary search over a node, and the height grows with the logarithm of the entry count.

The structure is the same one storage engines use for an on-disk index, laid out so each node maps onto a fixed-size page. This release keeps the tree in memory; the node layout is the durable one a pager will later persist.

K must be Ord; insert additionally needs Clone, because splitting a leaf copies a separator key up into the parent.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(3_u32, "three");
index.insert(1, "one");
index.insert(2, "two");

assert_eq!(index.get(&2), Some(&"two"));
assert_eq!(index.len(), 3);

Implementations

impl<K, V> BPlusTree<K, V>

pub fn new() -> Self

Create an empty tree with the default node fan-out.

Examples

use index_db::BPlusTree;

let index: BPlusTree<u32, &str> = BPlusTree::new();
assert!(index.is_empty());

pub fn len(&self) -> usize

The number of entries in the tree.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert("k", 1);
assert_eq!(index.len(), 1);

pub fn is_empty(&self) -> bool

Whether the tree holds no entries.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
assert!(index.is_empty());
index.insert("k", 1);
assert!(!index.is_empty());

pub fn height(&self) -> usize

The height of the tree in levels: a tree whose root is a leaf has height one, and every level of internal nodes above the leaves adds one more.

Because the tree is balanced, this is the number of nodes touched on any root-to-leaf path, and so the cost of a point lookup in node visits.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
assert_eq!(index.height(), 1); // just the root leaf
for k in 0..1_000_u32 {
    index.insert(k, k);
}
assert!(index.height() >= 2); // splits have grown the tree taller

pub fn clear(&mut self)

Remove every entry, returning the tree to its empty state.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(1_u32, "a");
index.clear();
assert!(index.is_empty());
assert_eq!(index.get(&1), None);

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

An iterator over every entry, in ascending key order.

The iterator is double-ended: call rev for descending order, or drive it from both ends.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(2_u32, "b");
index.insert(1, "a");
index.insert(3, "c");

let collected: Vec<_> = index.iter().map(|(&k, &v)| (k, v)).collect();
assert_eq!(collected, vec![(1, "a"), (2, "b"), (3, "c")]);

// Reverse with `.rev()`.
let keys: Vec<_> = index.iter().rev().map(|(&k, _)| k).collect();
assert_eq!(keys, vec![3, 2, 1]);

impl<K: Ord, V> BPlusTree<K, V>

pub fn get(&self, key: &K) -> Option<&V>

Look up the value stored under key, or None if the key is absent.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(10_u32, "ten");
assert_eq!(index.get(&10), Some(&"ten"));
assert_eq!(index.get(&11), None);

pub fn contains_key(&self, key: &K) -> bool

Whether the tree holds an entry for key.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(10_u32, "ten");
assert!(index.contains_key(&10));
assert!(!index.contains_key(&11));

pub fn range<R: RangeBounds<K>>(&self, range: R) -> Iter<'_, K, V>

An iterator over the entries whose keys fall in range, in ascending key order.

range is any standard range expression — a..b, a..=b, ..b, a.., or .. — interpreted over the key order. Like iter the result is double-ended, so a range can be walked forward or in reverse with rev.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
for k in 0..10_u32 {
    index.insert(k, k);
}

// Half-open range [3, 7).
let keys: Vec<_> = index.range(3..7).map(|(&k, _)| k).collect();
assert_eq!(keys, vec![3, 4, 5, 6]);

// Inclusive range, walked in reverse.
let rev: Vec<_> = index.range(2..=4).rev().map(|(&k, _)| k).collect();
assert_eq!(rev, vec![4, 3, 2]);

// Open-ended range.
let tail: Vec<_> = index.range(8..).map(|(&k, _)| k).collect();
assert_eq!(tail, vec![8, 9]);

impl<K: Ord + Clone, V> BPlusTree<K, V>

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Insert key with value. If the key was already present its previous value is replaced and returned; otherwise the entry is added and None is returned.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
assert_eq!(index.insert(1_u32, "a"), None);    // new key
assert_eq!(index.insert(1, "b"), Some("a"));   // replaced
assert_eq!(index.get(&1), Some(&"b"));

pub fn remove(&mut self, key: &K) -> Option<V>

Remove key, returning its value if it was present, or None if the tree held no such key.

Removing keeps the tree balanced: an under-full node borrows an entry from a sibling or merges with one, and when the root is left with a single child the tree collapses a level. Every leaf stays at the same depth.

Examples

use index_db::BPlusTree;

let mut index = BPlusTree::new();
index.insert(1_u32, "a");
index.insert(2, "b");

assert_eq!(index.remove(&1), Some("a")); // returns the removed value
assert_eq!(index.remove(&1), None);       // already gone
assert_eq!(index.get(&1), None);
assert_eq!(index.len(), 1);

Trait Implementations

impl<K, V> Default for BPlusTree<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<'a, K, V> IntoIterator for &'a BPlusTree<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.