Struct HnswIndex 

pub struct HnswIndex { /* private fields */ }

Hierarchical Navigable Small World graph index.

• FP32 construction for structural integrity
• Heuristic neighbor selection (Algorithm 4)
• Beam search with configurable ef parameter

Implementations

impl HnswIndex

pub fn hnsw_neighbors_layer0(&self, node_id: u32) -> Vec<u32>

Return the layer-0 neighbor list of node_id, or an empty slice if the node does not exist or has no layer-0 neighbors.

Used by LirePatcher for local topology-drift estimation.

impl HnswIndex

pub fn insert(&mut self, vector: Vec<f32>) -> Result<(), VectorError>

Insert a vector into the index.

1. Assign a random layer using the exponential distribution
2. Greedily descend from the entry point to the new node’s layer + 1
3. At each layer from the node’s layer down to 0, search for nearest neighbors, select via the diversity heuristic, and add bidirectional edges
4. Prune over-connected nodes to maintain the M/M0 invariant

impl HnswIndex

pub fn graph_checkpoint_to_bytes(&self) -> Result<Vec<u8>, VectorError>

Serialize ONLY the graph topology (neighbors, entry point, params) to rkyv bytes. Vector data is intentionally omitted — node_vectors is filled with empty Vec<f32> placeholders.

Pair with [Self::from_graph_checkpoint] on restore. The same RKHNS\0 magic and version byte are used so from_checkpoint can decode the bytes, but the resulting index has empty node storage.

This is the Lite pagedb-segment write path: vectors live in the segment, graph topology lives in the B+ tree. Origin never calls this method.

pub fn checkpoint_to_bytes(&self) -> Result<Vec<u8>, VectorError>

Serialize the index to rkyv bytes (with magic header) for storage.

Magic header RKHNS\0 allows from_checkpoint to detect format.

pub fn from_checkpoint(bytes: &[u8]) -> Result<Option<HnswIndex>, VectorError>

Restore an index from a checkpoint snapshot.

Returns:

• Ok(Some(index)) — successfully decoded (rkyv format).
• Ok(None) — bytes do not start with the RKHNS\0 magic header.
• Err(VectorError::UnsupportedVersion) — magic matches RKHNS\0 but the version byte is not HNSW_FORMAT_VERSION; the caller must reject the buffer.
• Err(VectorError::CheckpointDeserializationError) — magic and version matched but the rkyv payload itself failed to decode (structurally corrupt checkpoint).

impl HnswIndex

pub fn with_backing( &mut self, b: Arc<dyn VectorSegmentBacking>, ) -> Result<&mut HnswIndex, VectorError>

Attach a crate::segment_backing::VectorSegmentBacking to this index.

After this succeeds, dist_to_node falls back to the backing whenever an F32 node’s local vector storage is empty. This is used by Lite’s graph-checkpoint-only restore path: the graph topology is loaded from the B+ tree blob, but vector data lives in a pagedb segment.

Origin never calls this — its node arenas are always populated.

Errors

The backing is validated against this index BEFORE being attached, and is not attached at all when it cannot serve every node whose local storage is empty. An attached-but-unserviceable backing is the worst outcome available: the graph looks healthy, so search proceeds and then finds no vector for a node it must score. Callers should treat an error as “this segment is unusable — rebuild the index from the authoritative vectors, or leave the collection unloaded”, never as something to ignore.

• VectorError::StoredDimensionMismatch if the backing’s dim() is not this index’s dim.
• VectorError::VectorUnavailable if the backing holds fewer vectors than the index has nodes, or if a node that needs the backing has no correctly-sized vector in it.

impl HnswIndex

pub fn compact(&mut self) -> usize

Compact the index by removing all tombstoned nodes.

Returns the number of removed nodes. See compact_with_map for the variant that also returns the old→new id remapping.

pub fn compact_with_map(&mut self) -> (usize, Vec<u32>)

Compact and return both the removed count and the old→new id map.

id_map[old_local] = new_local, or u32::MAX if the node was tombstoned (removed). Repairs edges so the entry point reaches every remaining node.

impl HnswIndex

pub fn export_neighbors(&self) -> Vec<Vec<Vec<u32>>>

Export all neighbor lists for snapshot transfer.

impl HnswIndex

pub fn new(dim: usize, params: HnswParams) -> HnswIndex

Create a new empty HNSW index.

pub fn with_seed(dim: usize, params: HnswParams, seed: u64) -> HnswIndex

Create with a specific RNG seed (for deterministic testing).

pub fn metric(&self) -> DistanceMetric

The distance metric this index was built with. Search-time metric overrides must match this; differing metrics require either rebuilding the index or a metric-aware re-rank pass.

pub fn params(&self) -> &HnswParams

pub fn dim(&self) -> usize

pub fn dtype(&self) -> VectorStorageDtype

Storage dtype this index was constructed with.

pub fn entry_point(&self) -> Option<u32>

pub fn max_layer(&self) -> usize

pub fn rng_state(&self) -> u64

Current RNG state (for snapshot reproducibility).

pub fn memory_usage_bytes(&self) -> usize

Approximate memory usage in bytes (vector data + neighbor lists).

impl HnswIndex

pub fn len(&self) -> usize

pub fn live_count(&self) -> usize

pub fn tombstone_count(&self) -> usize

pub fn tombstone_ratio(&self) -> f64

Tombstone ratio: fraction of nodes that are deleted.

pub fn is_empty(&self) -> bool

pub fn delete(&mut self, id: u32) -> bool

Soft-delete a vector by internal node ID.

pub fn is_deleted(&self, id: u32) -> bool

pub fn undelete(&mut self, id: u32) -> bool

impl HnswIndex

pub fn get_vector(&self, id: u32) -> Option<&[f32]>

Returns a &[f32] view of the stored vector for node id.

Returns Some only when the index dtype is F32. For F16 or BF16 indexes this method returns None — use Self::get_vector_bytes instead and decode via crate::dtype::cast_to_f32 if an f32 view is needed.

In debug builds, calling this on a non-F32 index triggers a debug_assert! to flag misuse early. In release builds the debug_assert! is a no-op and None is returned silently.

pub fn get_vector_bytes(&self, id: u32) -> Option<&[u8]>

Dtype-agnostic byte view of the stored vector for node id.

Returns None if id is out of range. Pair the returned slice with Self::dtype to interpret the encoding.

pub fn get_vector_or_backing(&self, id: u32) -> Option<Cow<'_, [f32]>>

Returns the stored f32 vector for node id, consulting the pagedb segment backing when the node’s local storage is empty.

This is the rerank-safe accessor. It covers both cases that reading node.storage directly gets wrong:

• Lite’s graph-checkpoint-only restore path: after from_checkpoint + with_backing, per-node vectors are empty placeholders and the data must be fetched through the backing.
• A narrower storage dtype (F16/BF16): the node holds encoded bytes, not f32, so the vector is decoded into an owned Cow.

Returns None when id is out of range, or the node has no local vector and no backing supplies one. Decode failure also yields None — callers needing the reason should use Self::materialize_vector.

Only available on non-WASM targets (the backing type requires mmap).

pub fn materialize_vector(&self, id: u32) -> Result<Vec<f32>, VectorError>

Materialize node id’s vector as an owned Vec<f32>, consulting the segment backing when the node’s local storage is empty.

This is the authoritative accessor for every caller that copies vector data out of the index — segment serialization, checkpointing, snapshot export, parameter rebuilds. Reading node.storage directly is wrong on the graph-checkpoint-only restore path, where per-node storage is an empty placeholder and the real data lives in the attached backing.

Errors

• VectorError::VectorUnavailable if id is out of range, or local storage is empty and no backing provides the vector.
• VectorError::VectorDecodeFailed if dtype-encoded bytes cannot be decoded to f32.
• VectorError::StoredDimensionMismatch if the materialized vector’s length is not self.dim.

pub fn extract_vectors_and_surrogates( &self, ) -> Result<(Vec<Vec<f32>>, Vec<u64>), VectorError>

Extract all node vectors as owned F32 vecs for segment serialization.

The second tuple element is always empty — HnswIndex has no surrogate map. Surrogates live at the VectorCollection layer in Origin. Lite passes an empty slice so write_vector_segment writes no surrogate block.

Errors

Propagates Self::materialize_vector for the first node whose vector cannot be materialized. Serializing an empty or partial payload would write a segment whose header declares vectors it does not contain, so this fails loudly instead.

pub fn export_vectors(&self) -> Result<Vec<Vec<f32>>, VectorError>

Export all vectors as F32 for snapshot transfer.

For F32 indexes this is a clone. For F16/BF16 indexes each vector is decoded to F32 on the fly. Nodes whose local storage is empty are read through the attached segment backing.

Errors

Propagates Self::materialize_vector for the first node whose vector cannot be materialized. A caller copying vectors out of the index cannot use an empty placeholder, so this reports the failure rather than yielding one.

impl HnswIndex

pub fn search( &self, query: &[f32], k: usize, ef: usize, ) -> Result<Vec<SearchResult>, VectorError>

K-NN search: find the k closest vectors to query.

ef controls the search beam width (higher = better recall, slower). Must be >= k. Typical values: ef = 2k to 10k.

Returns VectorError::DimensionMismatch when query does not have the index dimension.

pub fn search_filtered( &self, query: &[f32], k: usize, ef: usize, filter: &RoaringBitmap, ) -> Result<Vec<SearchResult>, VectorError>

Filtered K-NN search with Roaring bitmap pre-filtering.

pub fn search_filtered_offset( &self, query: &[f32], k: usize, ef: usize, filter: &RoaringBitmap, id_offset: u32, ) -> Result<Vec<SearchResult>, VectorError>

Filtered K-NN search where the bitmap is keyed in a shifted ID space.

id_offset is added to local node IDs before testing filter.contains. Used by multi-segment collections where the bitmap holds GLOBAL ids and each segment’s HNSW nodes are numbered starting at base_id.

pub fn search_with_bitmap_bytes( &self, query: &[f32], k: usize, ef: usize, bitmap_bytes: &[u8], ) -> Result<Vec<SearchResult>, VectorError>

Deserialize a Roaring bitmap from bytes and perform filtered search.

pub fn search_with_bitmap_bytes_offset( &self, query: &[f32], k: usize, ef: usize, bitmap_bytes: &[u8], id_offset: u32, ) -> Result<Vec<SearchResult>, VectorError>

Deserialize a Roaring bitmap and search with an ID offset applied before testing membership. See search_filtered_offset for rationale.

Bytes that do not decode fail with VectorError::InvalidFilterBitmap: an unfiltered search would return rows the filter excludes.