How Turbovec Handles Deletions in the TurboQuantIndex and IdMapIndex

TLDR: Turbovec deletes vectors using swap_remove for the TurboQuantIndex (swapping the last vector into the vacated slot) and a mirrored dual-swap in IdMapIndex::remove(id: u64) -> bool, keeping both indexes synchronized in O(1) time with no element shifting.

Turbovec is a high-performance vector-search library written in Rust, developed in the RyanCodrai/turbovec repository. It stores compressed vectors in a TurboQuantIndex (the ANN index) and tracks external user-provided identifiers in an IdMapIndex. When you delete a vector, turbovec must keep both structures internally consistent while preserving its O(1) insert, remove, and search guarantees. The solution is a swap-remove strategy applied to both indexes, as implemented in turbovec/src/id_map.rs and exercised throughout the test suite.

TurboQuantIndex Deletions: The swap_remove Strategy

The TurboQuantIndex performs deletions via a swap_remove operation (a variant of Vec::swap_remove). Instead of shifting all subsequent vectors left (which would be O(n)), turbovec swaps the last vector into the now-empty slot and truncates the tail.

The process follows four steps:

1. The vector at the target slot is logically removed.
2. The last vector in the index is moved into the vacated slot.
3. The internal mapping from user-provided IDs to slot numbers is updated so the moved vector's ID now points to its new position.
4. The index's length is decremented, discarding the duplicate entry at the old tail.

Because the operation is a simple swap of the last element, it runs in constant time and does not require shifting remaining vectors. The search cache is also cleared so subsequent queries observe the new layout.

For example, the test in [turbovec/tests/swap_remove.rs at line 55](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/swap_remove.rs#L55) shows a vector being removed, the last vector taking its place, and search results reflecting the new layout. The comment in the same test (// must be reset when swap_remove runs) confirms that the search cache is invalidated after every removal.

IdMapIndex Deletions: The remove(id: u64) -> bool Method

The IdMapIndex tracks the mapping between external IDs and internal slots. Its removal method IdMapIndex::remove(id: u64) -> bool is declared in [turbovec/src/id_map.rs at line 520](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs#L520).

The deletion flow works like this:

1. Look up the slot that stores the vector for the supplied id.
2. If the ID is present, remove it from the id_to_slot map.
3. Clear the slot's entry in the slot_to_id table and decrement the total count.
4. If the deleted slot is the last slot, the removal is a simple pop. If it's an interior slot, the index swaps the last slot's ID into the vacated position — mirroring the swap_remove strategy of the quant index — so the dense storage of IDs stays compact.

This dual-swap approach guarantees that the forward (ID → slot) and reverse (slot → ID) tables stay synchronized and preserves O(1) performance.

The test suite verifies the removal semantics directly:

• Removing a missing ID returns false — see remove_returns_false_for_missing_id.
• Removing an existing ID shrinks the index and hides the entry — see remove_existing_id_shrinks_and_hides_it.
• Re-adding a previously removed ID works because the slot tables remain consistent — see remove_then_re_add_same_id_is_allowed.
• The internal swap when deleting the last slot is verified in id_map_remove_last_then_add_keeps_slot_tables_consistent.

How the Two Indexes Synchronize on Deletion

When you call TurboQuantIndex::swap_remove, the underlying IdMapIndex is updated because the swap logic cascades into the ID map to reflect the moved slot. After a deletion:

• The quant index no longer holds the vector data.
• The ID map no longer contains the removed ID.
• Any ID that was swapped into the vacated slot now points to the new slot location.

This tight coupling means a subsequent search for the removed ID fails, while a search for the swapped-in vector still succeeds using its original ID.

Code Examples

Here is how deletion works in practice, from the user's perspective:

// Delete a vector by its external ID.
let mut idx = TurboQuantIndex::new(dim, 4).unwrap();
idx.add(42, &some_vector).unwrap();   // Insert
assert!(idx.remove(42));              // swap_remove behind the scenes
assert!(!idx.contains(42));           // ID is gone

// Directly remove an ID from the IdMapIndex.
let mut id_map = IdMapIndex::new();
id_map.add(99, 5).unwrap();           // id 99 stored at slot 5
assert!(id_map.remove(99));           // true → slot cleared
assert!(!id_map.contains(99));        // false → ID no longer present

Key Source Files Reference

Component	Source File	Line Reference
TurboQuantIndex deletion logic	turbovec/src/lib.rs (core API)	— (calls swap_remove in tests)
swap_remove behavior test	turbovec/tests/swap_remove.rs	L55-L70
IdMapIndex remove method	turbovec/src/id_map.rs	L520-L540
IdMapIndex removal tests	turbovec/tests/id_map.rs	L82-L150
Consistency after removal	turbovec/tests/state_sequences.rs	L214-L225

Summary

• TurboQuantIndex uses swap_remove, which swaps the last vector into the vacated slot and truncates the tail, giving O(1) deletion with no shifting.
• IdMapIndex uses remove(id: u64) -> bool, which clears both the forward and reverse tables and swaps the last ID into any interior gap to keep dense storage compact.
• Both indexes stay synchronized because the quant index's swap_remove cascades into the ID map's slot tables.
• The search cache is invalidated after every removal so queries reflect the new layout.
• Re-adding a removed ID works because the slot tables remain consistent — verified by the state sequence tests.

Frequently Asked Questions

Is deletion in turbovec O(1)?

Yes. Both indexes use a swap-remove strategy where the last element replaces the removed element and the length is decremented, avoiding any element shifting. The swap_remove logic in turbovec/tests/swap_remove.rs demonstrates this constant-time behavior.

What happens when I delete a nonexistent ID in turbovec?

IdMapIndex::remove(id: u64) -> bool returns false and takes no action if the ID is not present. This is verified in the test remove_returns_false_for_missing_id at turbovec/tests/id_map.rs#L82.

Can I re-add an ID after deleting it in turbovec?

Yes. Because the id_to_slot and slot_to_id tables stay synchronized after a deletion, re-adding a previously removed ID works without conflicts, verified in remove_then_re_add_same_id_is_allowed.

How does turbovec keep the quant index and ID map in sync after deletion?

When TurboQuantIndex::swap_remove runs, it automatically calls into the underlying IdMapIndex to update the slot mapping for the moved vector. Both structures are updated atomically in the same operation, so their state remains consistent.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}