nodedb_vector/hnsw/graph/index/
tombstones.rs

1// SPDX-License-Identifier: Apache-2.0
2
3//! Soft deletion and the counts derived from it.
4//!
5//! Deleting a node marks it rather than removing it, because removal would
6//! renumber every id the graph's neighbor lists refer to. The tombstone ratio
7//! is what compaction watches to decide when the graph is worth rebuilding.
8
9use super::state::HnswIndex;
10
11impl HnswIndex {
12    pub fn len(&self) -> usize {
13        self.nodes.len()
14    }
15
16    pub fn live_count(&self) -> usize {
17        self.nodes.len() - self.tombstone_count()
18    }
19
20    pub fn tombstone_count(&self) -> usize {
21        self.nodes.iter().filter(|n| n.deleted).count()
22    }
23
24    /// Tombstone ratio: fraction of nodes that are deleted.
25    pub fn tombstone_ratio(&self) -> f64 {
26        if self.nodes.is_empty() {
27            0.0
28        } else {
29            self.tombstone_count() as f64 / self.nodes.len() as f64
30        }
31    }
32
33    pub fn is_empty(&self) -> bool {
34        self.live_count() == 0
35    }
36
37    /// Soft-delete a vector by internal node ID.
38    pub fn delete(&mut self, id: u32) -> bool {
39        if let Some(node) = self.nodes.get_mut(id as usize) {
40            if node.deleted {
41                return false;
42            }
43            node.deleted = true;
44            true
45        } else {
46            false
47        }
48    }
49
50    pub fn is_deleted(&self, id: u32) -> bool {
51        self.nodes.get(id as usize).is_none_or(|n| n.deleted)
52    }
53
54    pub fn undelete(&mut self, id: u32) -> bool {
55        if let Some(node) = self.nodes.get_mut(id as usize)
56            && node.deleted
57        {
58            node.deleted = false;
59            return true;
60        }
61        false
62    }
63}
nodedb_vector/hnsw/graph/index/tombstones.rs

nodedb_vector/hnsw/graph/index/
tombstones.rs
