Struct BfTreeProvider 

pub struct BfTreeProvider<T, Q = QuantVectorProvider>
where
    T: VectorRepr,
{ /* private fields */ }

An Bf-tree based implementation of a DataProvider built around the idea of having up to two layers of vector stores: a full-precision store and an optional quantized store. This provider uses the identity mapping between external and internal vector IDs.

Type Parameters:

• T: The primitive element type of the full-precision vector. This is typically some type like f32 or half::f16.

• Q: The full type of the quant vector store. This is not constrained by a trait and rather relies on implementation for several concrete types, including:

  • QuantVectorProvider: A Bf-Tree based spherical quantized vector store.
  • NoStore: Disable quantization altogether. Note that this disables all methods reached through quantization based [Accessor]s at compile-time.

Indexing Strategies

• FullPrecision: Only retrieves data from the full-precision portion of the index. No quantized vectors are used. During search, start points are filtered from the final results.

• Quantized: Performs all operations (search, pruning, insert) entirely in the quantized space using spherical distance functions. Post-processing copies candidate IDs forward without reranking. Fastest option — full-precision vectors are not touched at query time.

Examples

The following code demonstrates how to instantiate and use the BfTreeProvider in a number of different scenarios.

Full-Precision Only - No Deletes

This example demonstrates how to create a BfTreeProvider that only supports full-precision vectors.

use diskann_bftree::provider::{
    BfTreeProvider, BfTreeProviderParameters
};
use diskann_bftree::NoStore;
use diskann_vector::distance::Metric;
use diskann_utils::views::{Init, Matrix};
use bf_tree::Config;
use std::num::NonZeroUsize;

let parameters = BfTreeProviderParameters {
    max_points: 5,
    num_start_points: NonZeroUsize::new(1).unwrap(),
    dim: 4,
    metric: Metric::L2,
    max_degree: 32,
    vector_provider_config: Config::default(),
    quant_vector_provider_config: Config::default(),
    neighbor_list_provider_config: Config::default(),
    graph_params: None,
    use_snapshot: false,
};

// Create a table that supports 5 points and 1 start point.
let start_points = Matrix::new(Init(|| 0.0f32), 1, 4);
let provider = BfTreeProvider::<f32, _>::new(
    parameters,
    start_points.as_view(),
    NoStore,
);

Full-Precision and Spherical Quantization

To create a two-level provider with a spherical quantization-based quant vector store, a Poly<dyn Quantizer> can be supplied for the quant_precursor argument, as this implements the CreateQuantProvider trait.

use diskann_quantization::{
    alloc::{GlobalAllocator, Poly, poly},
    algorithms::TransformKind,
    spherical::{iface, SphericalQuantizer, SupportedMetric, PreScale},
};
use diskann_utils::views::{Init, Matrix};
use diskann_bftree::provider::{
    BfTreeProvider, BfTreeProviderParameters
};
use diskann_vector::distance::Metric;
use bf_tree::Config;
use std::num::NonZeroUsize;
use rand::rngs::StdRng;
use rand::SeedableRng;

let dim = 4;
let data = Matrix::new(Init(|| 1.0f32), 4, dim);
let mut rng = StdRng::seed_from_u64(42);
let sq = SphericalQuantizer::train(
    data.as_view(), TransformKind::Null,
    SupportedMetric::SquaredL2, PreScale::None,
    &mut rng, GlobalAllocator,
).unwrap();
let imp = iface::Impl::<1>::new(sq).unwrap();
let poly = Poly::new(imp, GlobalAllocator).unwrap();
let quantizer: Poly<dyn iface::Quantizer> = poly!(iface::Quantizer, poly);

let parameters = BfTreeProviderParameters {
    max_points: 5,
    num_start_points: NonZeroUsize::new(1).unwrap(),
    dim: 4,
    metric: Metric::L2,
    max_degree: 32,
    vector_provider_config: Config::default(),
    quant_vector_provider_config: Config::default(),
    neighbor_list_provider_config: Config::default(),
    graph_params: None,
    use_snapshot: false,
};

// Create a table that supports 5 points and 1 start point.
let start_points = Matrix::new(Init(|| 0.0f32), 1, 4);
let provider = BfTreeProvider::<f32, _>::new(
    parameters,
    start_points.as_view(),
    quantizer,
);

Implementations

impl<T, Q> BfTreeProvider<T, Q>

where T: VectorRepr,

pub fn new<TQ>( params: BfTreeProviderParameters, start_points: MatrixView<'_, T>, quant_precursor: TQ, ) -> ANNResult<Self>

where Self: StartPoint<T>, TQ: CreateQuantProvider<Target = Q>,

Construct a new data provider with start points initialized.

This is the primary constructor for BfTreeProvider where start points are known from the beginning. It creates the provider and sets the start points in one operation.

Arguments

• params: An instance of BfTreeProviderParameters collecting shared configuration information.
• start_points: A matrix view containing the start point vectors. The number of rows must match params.num_start_points.get().
• quant_precursor: A precursor type for the quantizer layer.

Type Constraints

• Self: StartPoint<T> - The provider must implement the StartPoint trait.

pub fn starting_points(&self) -> ANNResult<Vec<u32>>

Return a vector of starting points.

pub fn iter(&self) -> Range<u32>

An iterator over all ids including start points (even if they are deleted).

pub fn num_start_points(&self) -> usize

pub fn max_points(&self) -> usize

Return the maximum number of points (excluding frozen/start points)

pub fn dim(&self) -> usize

Return the vector dimension

pub fn metric(&self) -> Metric

Return the distance metric

pub fn max_degree(&self) -> u32

Return the maximum degree from the neighbor provider

impl<T> BfTreeProvider<T, QuantVectorProvider>

where T: VectorRepr,

pub fn counts_for_get_vector(&self) -> (usize, usize)

Return the number of vector reads for full-precision and quant-vectors respectively

impl<T> BfTreeProvider<T, NoStore>

where T: VectorRepr,

pub fn counts_for_get_vector(&self) -> (usize, usize)

Return the number of vector reads for full-precision and quant-vectors respectively

impl<T, Q> BfTreeProvider<T, Q>

where T: VectorRepr, Q: AsyncFriendly,

pub fn neighbors(&self) -> &NeighborProvider<u32>

Trait Implementations

impl<T, Q> DataProvider for BfTreeProvider<T, Q>

where T: VectorRepr, Q: AsyncFriendly,

type Context = DefaultContext

type InternalId = u32

type ExternalId = u32

type Error = ANNError

type Guard = NoopGuard<u32>

The operation guard returned by SetElement::set_element to notify self if an operation fails.

fn to_internal_id( &self, _context: &DefaultContext, gid: &Self::ExternalId, ) -> Result<Self::InternalId, Self::Error>

Translate an external id to its corresponding internal id.

fn to_external_id( &self, _context: &DefaultContext, id: Self::InternalId, ) -> Result<Self::ExternalId, Self::Error>

Translate an internal id to its corresponding external id.

impl<'a, T, Q> DefaultPostProcessor<'a, BfTreeProvider<T, Q>, &'a [T]> for FullPrecision

where T: VectorRepr, Q: AsyncFriendly,

type Processor = Pipeline<FilterStartPoints, CopyIds>

The default post-processor type.

fn default_post_processor(&self) -> Self::Processor

Create the default post-processor.

impl<'a, T> DefaultPostProcessor<'a, BfTreeProvider<T>, &'a [T]> for Quantized

where T: VectorRepr,

type Processor = Pipeline<FilterStartPoints, Rerank>

The default post-processor type.

fn default_post_processor(&self) -> Self::Processor

Create the default post-processor.

impl<T, Q> Delete for BfTreeProvider<T, Q>

where T: VectorRepr, Q: AsyncFriendly + DeleteQuant,

Hard-delete implementation for BfTreeProvider.

This provider performs hard deletes: vector data is immediately and irrecoverably erased from the underlying bf-tree storage when Delete::delete is called. When a quantized store is present, both the full-precision and quantized entries are removed.

This has an important consequence for inplace delete: the [InplaceDeleteMethod::VisitedAndTopK] strategy is incompatible with this provider because it requires reading the deleted vector’s data (via InplaceDeleteStrategy::get_delete_element) after the delete has already been committed. Use [InplaceDeleteMethod::OneHop] or [InplaceDeleteMethod::TwoHopAndOneHop] instead, as these strategies only require neighbor topology (which remains accessible).

fn release( &self, _context: &Self::Context, _id: Self::InternalId, ) -> impl Future<Output = Result<(), Self::Error>> + Send

Release a node by an internal ID.

fn delete( &self, _context: &Self::Context, gid: &Self::ExternalId, ) -> impl Future<Output = Result<(), Self::Error>> + Send

Delete an item by external ID.

fn status_by_external_id( &self, context: &Self::Context, gid: &Self::ExternalId, ) -> impl Future<Output = Result<ElementStatus, Self::Error>> + Send

Check the status via external ID.

fn status_by_internal_id( &self, _context: &Self::Context, id: Self::InternalId, ) -> impl Future<Output = Result<ElementStatus, Self::Error>> + Send

Check the status via internal ID.

fn statuses_unordered<Itr, F>( &self, context: &Self::Context, itr: Itr, f: F, ) -> impl Future<Output = Result<(), Self::Error>> + Send

where Itr: Iterator<Item = Self::InternalId> + Send, F: FnMut(Result<ElementStatus, Self::Error>, Self::InternalId) + Send,

A potentially optimized bulk version of status_by_internal_id.

impl<T, Q> HasId for BfTreeProvider<T, Q>

where T: VectorRepr, Q: AsyncFriendly,

type Id = u32

impl<T, Q> InplaceDeleteStrategy<BfTreeProvider<T, Q>> for FullPrecision

where T: VectorRepr, Q: AsyncFriendly,

Inplace delete strategy using full-precision vectors.

Compatibility

This strategy is used with [InplaceDeleteMethod::OneHop] and [InplaceDeleteMethod::TwoHopAndOneHop]. It is not compatible with [InplaceDeleteMethod::VisitedAndTopK] because BfTreeProvider performs hard deletes — the vector data is erased before get_delete_element is called, causing it to fail.

type DeleteElementError = ANNError

Error type for accessing for search.

type DeleteElement<'a> = &'a [T]

The type provided to the search portion of inplace-deletion and used to instantiate the required SearchStrategy.

type DeleteElementGuard = Box<[T]>

The guard type returned by get_delete_element.

type PruneStrategy = FullPrecision

The pruning strategy to use after the initial search is complete.

type DeleteSearchAccessor<'a> = FullAccessor<'a, T, Q>

The accessor used during the delete-search phase.

type SearchPostProcessor = CopyIds

The processor used during the delete-search phase.

type SearchStrategy = FullPrecision

The type of the search strategy to use for graph traversal.

fn search_strategy(&self) -> Self::SearchStrategy

Construct the search strategy object.

fn prune_strategy(&self) -> Self::PruneStrategy

Construct the prune strategy object.

fn search_post_processor(&self) -> Self::SearchPostProcessor

Construct the search post-processor for the delete-search phase.

async fn get_delete_element<'a>( &'a self, provider: &'a BfTreeProvider<T, Q>, _context: &'a DefaultContext, id: u32, ) -> Result<Self::DeleteElementGuard, Self::DeleteElementError>

Construct the accessor used to retrieve the item being deleted.

impl<T> InplaceDeleteStrategy<BfTreeProvider<T>> for Quantized

where T: VectorRepr,

Inplace delete strategy using quantized vectors.

Compatibility

Same constraint as FullPrecision’s impl: not compatible with [InplaceDeleteMethod::VisitedAndTopK] due to hard deletes.

type DeleteElementError = ANNError

Error type for accessing for search.

type DeleteElement<'a> = &'a [T]

The type provided to the search portion of inplace-deletion and used to instantiate the required SearchStrategy.

type DeleteElementGuard = Box<[T]>

The guard type returned by get_delete_element.

type PruneStrategy = Quantized

The pruning strategy to use after the initial search is complete.

type DeleteSearchAccessor<'a> = QuantAccessor<'a, T>

The accessor used during the delete-search phase.

type SearchPostProcessor = Rerank

The processor used during the delete-search phase.

type SearchStrategy = Quantized

The type of the search strategy to use for graph traversal.

fn search_strategy(&self) -> Self::SearchStrategy

Construct the search strategy object.

fn prune_strategy(&self) -> Self::PruneStrategy

Construct the prune strategy object.

fn search_post_processor(&self) -> Self::SearchPostProcessor

Construct the search post-processor for the delete-search phase.

async fn get_delete_element<'a>( &'a self, provider: &'a BfTreeProvider<T, QuantVectorProvider>, _context: &'a DefaultContext, id: u32, ) -> Result<Self::DeleteElementGuard, Self::DeleteElementError>

Construct the accessor used to retrieve the item being deleted.

impl<'a, T, Q> InsertStrategy<'a, BfTreeProvider<T, Q>, &'a [T]> for FullPrecision

where T: VectorRepr, Q: AsyncFriendly,

type PruneStrategy = FullPrecision

The pruning strategy associated with the insertion strategy.

fn prune_strategy(&self) -> Self::PruneStrategy

Return the prune strategy used for insertion.

fn insert_search_accessor( &'a self, provider: &'a Provider, context: &'a <Provider as DataProvider>::Context, vector: T, ) -> Result<Self::SearchAccessor, Self::SearchAccessorError>

This API is invoked during inserts to create the associated SearchAccessor.

impl<'a, T> InsertStrategy<'a, BfTreeProvider<T>, &'a [T]> for Quantized

where T: VectorRepr,

type PruneStrategy = Quantized

The pruning strategy associated with the insertion strategy.

fn prune_strategy(&self) -> Self::PruneStrategy

Return the prune strategy used for insertion.

fn insert_search_accessor( &'a self, provider: &'a Provider, context: &'a <Provider as DataProvider>::Context, vector: T, ) -> Result<Self::SearchAccessor, Self::SearchAccessorError>

This API is invoked during inserts to create the associated SearchAccessor.

impl<T, Q> IntoIterator for &BfTreeProvider<T, Q>

where T: VectorRepr,

Allow &BfTreeProvider to implement IntoIter

type Item = u32

The type of the elements being iterated over.

type IntoIter = Range<u32>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T> LoadWith<String> for BfTreeProvider<T, NoStore>

where T: VectorRepr,

type Error = ANNError

The error type if deserialization is unsuccessful.

async fn load_with<P>(storage: &P, prefix: &String) -> Result<Self, Self::Error>

where P: StorageReadProvider,

Load self form disk using provider for IO-related needs. Argument auxiliary can be arbitrary metadata required for a successful operation, such as file paths.

impl<T> LoadWith<String> for BfTreeProvider<T, QuantVectorProvider>

where T: VectorRepr,

type Error = ANNError

The error type if deserialization is unsuccessful.

async fn load_with<P>(storage: &P, prefix: &String) -> Result<Self, Self::Error>

where P: StorageReadProvider,

Load self form disk using provider for IO-related needs. Argument auxiliary can be arbitrary metadata required for a successful operation, such as file paths.

impl<T, Q, B> MultiInsertStrategy<BfTreeProvider<T, Q>, B> for FullPrecision

where T: VectorRepr, Q: AsyncFriendly, B: for<'a> Batch<Element<'a> = &'a [T]> + Debug,

type Seed = Builder<u32, Ref<[T]>>

The prune-accessor “seed”, potentially containing B for faster access.

type FinishError = Infallible

Any critical error that occurs during finish.

type PruneStrategy = FullPrecision

The delegated PruneStrategy used for pruning.

type InsertStrategy = FullPrecision

The delegated InsertStrategy for most insertion related decisions.

fn insert_strategy(&self) -> Self::InsertStrategy

Construct the associated InsertStrategy.

fn finish<Itr>( &self, _provider: &BfTreeProvider<T, Q>, _ctx: &DefaultContext, batch: &Arc<B>, ids: Itr, ) -> impl Future<Output = Result<Self::Seed, Self::FinishError>> + Send

where Itr: ExactSizeIterator<Item = u32> + Send,

Package batch and the associated internal IDs into an intermediate seed.

fn seeded_prune_accessor<'a>( &'a self, provider: &'a BfTreeProvider<T, Q>, _context: &'a DefaultContext, seed: &'a Self::Seed, capacity: usize, ) -> ANNResult<FullPruneAccessor<'a, T, Q>>

Construct a PruneAccessor from a seed returned by Self::finish.

impl<T, B> MultiInsertStrategy<BfTreeProvider<T>, B> for Quantized

where T: VectorRepr, B: Batch + for<'a> Batch<Element<'a> = &'a [T]> + Debug,

type Seed = ()

The prune-accessor “seed”, potentially containing B for faster access.

type FinishError = Infallible

Any critical error that occurs during finish.

type PruneStrategy = Quantized

The delegated PruneStrategy used for pruning.

type InsertStrategy = Quantized

The delegated InsertStrategy for most insertion related decisions.

fn insert_strategy(&self) -> Self::InsertStrategy

Construct the associated InsertStrategy.

fn finish<Itr>( &self, _provider: &BfTreeProvider<T, QuantVectorProvider>, _ctx: &DefaultContext, _batch: &Arc<B>, _ids: Itr, ) -> impl Future<Output = Result<Self::Seed, Self::FinishError>> + Send

where Itr: ExactSizeIterator<Item = u32> + Send,

Package batch and the associated internal IDs into an intermediate seed.

fn seeded_prune_accessor<'a>( &'a self, provider: &'a BfTreeProvider<T, QuantVectorProvider>, _context: &'a DefaultContext, _seed: &'a (), capacity: usize, ) -> ANNResult<QuantPruneAccessor<'a, T>>

Construct a PruneAccessor from a seed returned by Self::finish.

impl<T, Q> PruneStrategy<BfTreeProvider<T, Q>> for FullPrecision

where T: VectorRepr, Q: AsyncFriendly,

type PruneAccessor<'a> = FullPruneAccessor<'a, T, Q>

The concrete type of the PruneAccessor that is used during index construction.

type PruneAccessorError = Infallible

An error that can occur when getting the prune accessor.

fn prune_accessor<'a>( &'a self, provider: &'a BfTreeProvider<T, Q>, _context: &'a DefaultContext, capacity: usize, ) -> Result<Self::PruneAccessor<'a>, Self::PruneAccessorError>

Return the PruneAccessor. Argument capacity provides an upper bound on the length of the iterator passed to PruneAccessor::fill.

impl<T> PruneStrategy<BfTreeProvider<T>> for Quantized

where T: VectorRepr,

type PruneAccessor<'a> = QuantPruneAccessor<'a, T>

The concrete type of the PruneAccessor that is used during index construction.

type PruneAccessorError = ANNError

An error that can occur when getting the prune accessor.

fn prune_accessor<'a>( &'a self, provider: &'a BfTreeProvider<T, QuantVectorProvider>, _context: &'a DefaultContext, capacity: usize, ) -> Result<Self::PruneAccessor<'a>, Self::PruneAccessorError>

Return the PruneAccessor. Argument capacity provides an upper bound on the length of the iterator passed to PruneAccessor::fill.

impl<T> SaveWith<String> for BfTreeProvider<T, NoStore>

where T: VectorRepr,

type Ok = usize

The return type upon successful saving. This is often (but is not required to be) the number of bytes written to disk.

type Error = ANNError

The error type if serialization is unsuccessful.

async fn save_with<P>( &self, storage: &P, prefix: &String, ) -> Result<Self::Ok, Self::Error>

where P: StorageWriteProvider,

Safe self to disk using provider for IO-related needs. Argument auxiliary can be arbitrary metadata required for a successful operation, such as file paths.

impl<T> SaveWith<String> for BfTreeProvider<T, QuantVectorProvider>

where T: VectorRepr,

type Ok = usize

The return type upon successful saving. This is often (but is not required to be) the number of bytes written to disk.

type Error = ANNError

The error type if serialization is unsuccessful.

async fn save_with<P>( &self, storage: &P, prefix: &String, ) -> Result<Self::Ok, Self::Error>

where P: StorageWriteProvider,

Safe self to disk using provider for IO-related needs. Argument auxiliary can be arbitrary metadata required for a successful operation, such as file paths.

impl<'a, T, Q> SearchStrategy<'a, BfTreeProvider<T, Q>, &'a [T]> for FullPrecision

where T: VectorRepr, Q: AsyncFriendly,

Perform a search entirely in the full-precision space.

Starting points are not filtered out of the final results.

type SearchAccessor = FullAccessor<'a, T, Q>

The concrete type of the accessor that is used to access Self during the greedy graph search. The query will be provided to the accessor exactly once during search to construct the query computer.

type SearchAccessorError = Infallible

An error that can occur when getting a search_accessor.

fn search_accessor( &'a self, provider: &'a BfTreeProvider<T, Q>, _context: &'a DefaultContext, query: &'a [T], ) -> Result<Self::SearchAccessor, Self::SearchAccessorError>

Construct and return the search accessor.

impl<'a, T> SearchStrategy<'a, BfTreeProvider<T>, &'a [T]> for Quantized

where T: VectorRepr,

Perform a search entirely in the quantized space.

Starting points are not filtered out of the final results.

type SearchAccessor = QuantAccessor<'a, T>

The concrete type of the accessor that is used to access Self during the greedy graph search. The query will be provided to the accessor exactly once during search to construct the query computer.

type SearchAccessorError = ANNError

An error that can occur when getting a search_accessor.

fn search_accessor( &'a self, provider: &'a BfTreeProvider<T, QuantVectorProvider>, _context: &'a DefaultContext, query: &'a [T], ) -> Result<Self::SearchAccessor, Self::SearchAccessorError>

Construct and return the search accessor.

impl<T> SetElement<&[T]> for BfTreeProvider<T, QuantVectorProvider>

where T: VectorRepr,

Assign to both the full-precision and quant vector stores

fn set_element( &self, _context: &Self::Context, id: &u32, element: &[T], ) -> impl Future<Output = Result<Self::Guard, Self::SetError>> + Send

Store the provided element in both the full-precision and quant vector stores.

Full-precision is written first as the authoritative store. This ensures that if the quant write fails, the worst case is a vector reachable in full-precision but not yet in quantized search (benign), rather than a quantized ghost with no full-precision backing data.

type SetError = ANNError

The kind of error yielded by set_element.

impl<T> SetElement<&[T]> for BfTreeProvider<T, NoStore>

where T: VectorRepr,

Assign to just the full-precision store

fn set_element( &self, _context: &Self::Context, id: &u32, element: &[T], ) -> impl Future<Output = Result<Self::Guard, Self::SetError>> + Send

Store the provided element in just the full-precision vector stores

type SetError = ANNError

The kind of error yielded by set_element.

impl<T> StartPoint<T> for BfTreeProvider<T, QuantVectorProvider>

where T: VectorRepr,

Set start points for the BfTreeProvider with quantization.

This implementation sets both the full-precision and quantized vectors for each start point, as well as initializing empty neighbor lists.

impl<T> StartPoint<T> for BfTreeProvider<T, NoStore>

where T: VectorRepr,

Set start points for the BfTreeProvider without quantization.

This implementation sets the full-precision vectors for each start point and initializes empty neighbor lists.