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. Beyond point access it supports ordered iteration and range scans, forward and in reverse.

The tree does not own its nodes directly. It addresses them by id through an internal node store, and the store the nodes live in is a seam: today they sit in a heap slab (a fast, single-threaded, in-process ordered map), and the same algorithm can later run over a page-backed store without change. That seam is internal — the public surface is just this one type.

K must be Ord; insert and remove additionally need Clone, because the tree copies separator keys between nodes as it splits and rebalances.

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());

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

pub fn from_sorted<I: IntoIterator<Item = (K, V)>>(entries: I) -> Self

Build a tree in bulk from entries already sorted by key.

When the input is sorted strictly ascending by key, the tree is built bottom-up — leaves packed and balanced in one pass — which is much faster than inserting one entry at a time. If the input is not strictly ascending (out of order or with duplicate keys), it falls back to ordinary insertion, so the result is always a correct tree; only the fast path requires sorted, unique keys. On the fallback path a later duplicate key overwrites an earlier one.

Examples

use index_db::BPlusTree;

// Sorted input takes the fast bottom-up path.
let index = BPlusTree::from_sorted((0..1_000_u32).map(|k| (k, k * k)));
assert_eq!(index.len(), 1_000);
assert_eq!(index.get(&30), Some(&900));
assert_eq!(index.get(&999), Some(&998_001));

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

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());

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

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.