Struct BTreeIndex 

pub struct BTreeIndex { /* private fields */ }

B-Tree based index for ordered key lookups and range queries.

This index maintains keys in sorted order, enabling:

• Exact key lookups
• Range queries (e.g., all keys between “a” and “z”)
• Prefix scans (e.g., all keys starting with “user:”)
• Ordered iteration

Performance

• Insert: O(log n)
• Lookup: O(log n)
• Range query: O(log n + k) where k is the number of results

Example

use rustlite_core::index::{BTreeIndex, Index};

let mut index = BTreeIndex::new();
index.insert(b"apple", 1).unwrap();
index.insert(b"banana", 2).unwrap();
index.insert(b"cherry", 3).unwrap();

// Exact lookup
assert_eq!(index.find(b"banana").unwrap(), vec![2]);

// Range query
let range = index.range(b"apple", b"cherry").unwrap();
assert_eq!(range.len(), 3);

Implementations

impl BTreeIndex

pub fn new() -> Self

Create a new empty B-Tree index.

pub fn range( &self, start: &[u8], end: &[u8], ) -> Result<Vec<(Vec<u8>, Vec<u64>)>>

Range query: find all entries where key is in [start, end] inclusive.

Returns a vector of (key, values) pairs in sorted order.

pub fn prefix_scan(&self, prefix: &[u8]) -> Result<Vec<(Vec<u8>, Vec<u64>)>>

Prefix scan: find all entries where key starts with the given prefix.

Returns a vector of (key, values) pairs in sorted order.

pub fn min_key(&self) -> Option<&[u8]>

Get the minimum key in the index, if any.

pub fn max_key(&self) -> Option<&[u8]>

Get the maximum key in the index, if any.

pub fn iter(&self) -> impl Iterator<Item = (&[u8], &[u64])>

Iterate over all entries in sorted order.

Trait Implementations

impl Clone for BTreeIndex

fn clone(&self) -> BTreeIndex

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for BTreeIndex

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for BTreeIndex

fn default() -> Self

Returns the “default value” for a type.

impl Index for BTreeIndex

fn insert(&mut self, key: &[u8], value: u64) -> Result<()>

Insert a key-value pair into the index. The value is typically a pointer/offset to the actual data.

fn find(&self, key: &[u8]) -> Result<Vec<u64>>

Find all values matching the exact key.

fn remove(&mut self, key: &[u8]) -> Result<bool>

Remove all entries for a key from the index. Returns true if any entries were removed.

fn len(&self) -> usize

Returns the number of entries in the index.

fn clear(&mut self)

Clear all entries from the index.

fn index_type(&self) -> IndexType

Returns the index type.

fn is_empty(&self) -> bool

Returns true if the index is empty.