Struct BTreeIndex

pub struct BTreeIndex { /* private fields */ }

A btree index satisfies scalar queries using a b tree

The upper layers of the btree are expected to be cached and, when unloaded, are stored in a btree structure in memory. The leaves of the btree are left to be searched by some other kind of index (currently a flat search).

This strikes a balance between an expensive memory structure containing all of the values and an expensive disk structure that can’t be efficiently searched.

For example, given 1Bi values we can store 256Ki leaves of size 4Ki. We only need memory space for 256Ki leaves (depends on the data type but usually a few MiB at most) and can narrow our search to 4Ki values.

Note: this is very similar to the IVF index except we store the IVF part in a btree for faster lookup

Trait Implementations

impl Clone for BTreeIndex

fn clone(&self) -> BTreeIndex

Returns a copy 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 DeepSizeOf for BTreeIndex

fn deep_size_of_children(&self, context: &mut Context) -> usize

Returns an estimation of the heap-managed storage of this object. This does not include the size of the object itself.

fn deep_size_of(&self) -> usize

Returns an estimation of a total size of memory owned by the object, including heap-managed storage.

impl Index for BTreeIndex

fn as_any(&self) -> &dyn Any

Cast to Any.

fn as_index(self: Arc<Self>) -> Arc<dyn Index>

Cast to Index

fn as_vector_index(self: Arc<Self>) -> Result<Arc<dyn VectorIndex>>

Cast to vector::VectorIndex

fn index_type(&self) -> IndexType

Get the type of the index

fn statistics(&self) -> Result<Value>

Retrieve index statistics as a JSON Value

fn calculate_included_frags<'life0, 'async_trait>( &'life0 self, ) -> Pin<Box<dyn Future<Output = Result<RoaringBitmap>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait,

Read through the index and determine which fragment ids are covered by the index

impl ScalarIndex for BTreeIndex

fn search<'life0, 'life1, 'async_trait>( &'life0 self, query: &'life1 dyn AnyQuery, ) -> Pin<Box<dyn Future<Output = Result<RowIdTreeMap>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait,

Search the scalar index

fn load<'async_trait>( store: Arc<dyn IndexStore>, ) -> Pin<Box<dyn Future<Output = Result<Arc<Self>>> + Send + 'async_trait>>

where Self: 'async_trait,

Load the scalar index from storage

fn remap<'life0, 'life1, 'life2, 'async_trait>( &'life0 self, mapping: &'life1 HashMap<u64, Option<u64>>, dest_store: &'life2 dyn IndexStore, ) -> Pin<Box<dyn Future<Output = Result<()>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait, 'life2: 'async_trait,

Remap the row ids, creating a new remapped version of this index in dest_store

fn update<'life0, 'life1, 'async_trait>( &'life0 self, new_data: SendableRecordBatchStream, dest_store: &'life1 dyn IndexStore, ) -> Pin<Box<dyn Future<Output = Result<()>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait,

Add the new data into the index, creating an updated version of the index in dest_store