# How Turbovec Handles Deletions in the TurboQuantIndex and IdMapIndex

> Learn how turbovec efficiently handles deletions in TurboQuantIndex and IdMapIndex using swap_remove and dual-swap for O(1) synchronized updates without element shifting.

- Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec)
- Tags: internals
- Published: 2026-08-22

---

**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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/id_map.rs#L82).
- Removing an existing ID shrinks the index and hides the entry — see [`remove_existing_id_shrinks_and_hides_it`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/id_map.rs#L93).
- Re-adding a previously removed ID works because the slot tables remain consistent — see [`remove_then_re_add_same_id_is_allowed`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/id_map.rs#L146).
- The internal swap when deleting the last slot is verified in [`id_map_remove_last_then_add_keeps_slot_tables_consistent`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/state_sequences.rs#L214).

## 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:

```rust
// 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`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs) (core API) | — (calls `swap_remove` in tests) |
| `swap_remove` behavior test | [`turbovec/tests/swap_remove.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/swap_remove.rs) | [L55-L70](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/swap_remove.rs#L55) |
| IdMapIndex `remove` method | [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) | [L520-L540](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs#L520) |
| IdMapIndex removal tests | [`turbovec/tests/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/id_map.rs) | [L82-L150](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/id_map.rs#L82) |
| Consistency after removal | [`turbovec/tests/state_sequences.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/state_sequences.rs) | [L214-L225](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/state_sequences.rs#L214) |

## 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`](https://github.com/RyanCodrai/turbovec/blob/main/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.