Struct BPlusIndex

Source

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

Expand description

An arena-backed B+Tree sorted multimap.

Entries are (K, V) pairs sorted lexicographically. The pair is the unique identity: inserting the same (K, V) twice is a no-op, but inserting (K, V1) and (K, V2) stores both.

Nodes are stored in contiguous Vecs and referenced by u32 indices. Freed nodes are recycled via an internal free list.

Implementations§

Source §

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

Source

pub fn new() -> Self

Creates a new empty index.

Source

pub fn len(&self) -> usize

Returns the number of entries in the index.

Source

pub fn is_empty(&self) -> bool

Returns true if the index contains no entries.

Source

pub fn insert(&mut self, key: K, val: V)

Inserts a (key, val) pair into the index.

If the exact (key, val) pair already exists, this is a no-op. Multiple values for the same key are allowed.

Source

pub fn delete(&mut self, key: &K, val: &V) -> bool

Removes the exact (key, val) pair from the index.

Returns true if the entry was found and removed, false otherwise.

Source

pub fn update(&mut self, old_key: &K, new_key: K, val: V)

Re-indexes an entry by deleting (old_key, val) and inserting (new_key, val).

This is a convenience for the common case where the indexed field of a row changes but the row identifier (the value) stays the same.

Source

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

Returns a reference to the first value associated with key, or None.

For unique indexes this is the only value. For non-unique indexes this returns the smallest V for the given K.

Time: O(log n).

Source

pub fn lookup_range<'a>(&'a self, key: &'a K) -> LookupRange<'a, K, V> ⓘ

Returns an iterator over all values associated with key.

Values are yielded in ascending V order. The iterator follows the leaf chain, so it works correctly even when entries for one key span multiple leaves.

Time: O(log n) for the initial descent, then O(k) for k results.

Source