# TurboVec Vector Deletion: How Swap-Remove Enables Fast O(1) Removal Without Preserving Order

> Discover how TurboVec achieves O(1) vector deletion using swap-remove, sacrificing order for speed. Learn about its efficient internal id table updates.

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

---

**TurboVec does not preserve insertion order during vector deletion; instead, it performs an O(1) swap-remove that moves the last vector into the deleted slot and updates internal id tables.**

TurboVec is an approximate-nearest-neighbor library that stores quantized vectors positionally inside a `TurboQuantIndex` for fast search. When you delete a vector through the high-level `IdMapIndex` API, the implementation trades sequence stability for constant-time performance. Understanding how TurboVec handles vector deletion requires a close look at the swap-remove logic in `RyanCodrai/turbovec`.

## The Swap-Remove Mechanism in TurboVec

Inside the core index, vectors are held in a flat positional array. When a deletion request arrives, the index does not shift subsequent elements forward. Instead, it invokes a **swap-remove** primitive on the underlying storage.

This operation copies the vector currently occupying the last slot into the now-vacant deleted slot, then truncates the storage by one. Because the moved element originates from the end of the array, the original ordering of the remaining vectors is destroyed.

## How `IdMapIndex::remove` Works

The `IdMapIndex` wrapper in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) orchestrates the deletion while keeping external id mappings consistent. The method executes four discrete steps:

1. **Resolve the slot.** It looks up the internal slot index for the given external `id` in the `id_to_slot` map. If the id is absent, it returns `false` immediately.

2. **Swap-remove the vector.** It calls `self.inner.swap_remove(slot)` on the inner `TurboQuantIndex`, which returns the former last index.

3. **Remap the id tables.** If the deleted slot was not the last position, it retrieves the id of the vector that was moved, writes that id into `slot_to_id[slot]`, and updates `id_to_slot` to point to the new slot.

4. **Shrink the slot list.** It pops the final entry from `slot_to_id`, dropping the duplicate trailing record.

All four steps are **O(1)**, giving `IdMapIndex::remove` constant-time complexity regardless of index size.

## Source Code Breakdown

The implementation in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) is concise and explicitly relies on `swap_remove`:

```rust
/// Remove the vector with the given external id.
/// Returns `true` if the id was present and removed, `false` otherwise.
/// O(1) via the inner [`TurboQuantIndex::swap_remove`].
pub fn remove(&mut self, id: u64) -> bool {
    let Some(slot) = self.id_to_slot.remove(&id) else {
        return false;
    };
    let last = self.slot_to_id.len() - 1;

    // Perform the swap-remove on the inner index.
    let moved_from = self.inner.swap_remove(slot);
    debug_assert_eq!(moved_from, last);

    // Mirror the swap-and-pop in our id tables.
    if slot != last {
        let moved_id = self.slot_to_id[last];
        self.slot_to_id[slot] = moved_id;
        self.id_to_slot.insert(moved_id, slot);
    }
    self.slot_to_id.pop();

    true
}

```

The `debug_assert_eq!(moved_from, last)` confirms the invariant that the inner index always pulls from the final slot. After the swap, the bidirectional maps (`slot_to_id` and `id_to_slot`) are patched so that the moved vector’s external id resolves to its new position.

## Observing Non-Deterministic Order After Deletion

You can verify this behavior with a small Rust program that inserts three vectors and deletes the middle one:

```rust
use turbovec::IdMapIndex;

fn main() -> Result<(), Box<dyn std::error::Error>> {
    // Create an index for 768-dimensional vectors, 4-bit quantization.
    let mut idx = IdMapIndex::new(768, 4)?;

    // Add three vectors with stable external IDs.
    let vectors = vec![0.0_f32; 768 * 3];
    idx.add_with_ids(&vectors, &[10, 20, 30])?;

    // Delete the vector with id 20.
    assert!(idx.remove(20));

    // The remaining vectors are now in slots 0 and 1, but the
    // original order (10, 30) is not guaranteed – the vector that
    // was at the last slot (id 30) may have been swapped into slot 1.
    println!("Current ids: {:?}", idx.slot_to_id);
    Ok(())
}

```

Running this snippet typically prints `slot_to_id` with id `30` occupying slot `1`, proving that TurboVec deletion is order-agnostic. The documentation in [`turbovec/src/lib.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs) and the test suite in [`turbovec/tests/swap_remove.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/swap_remove.rs) reinforce this contract.

## Preserving Insertion Order Outside TurboVec

If your application requires strict insertion order after deletes, TurboVec’s API does not provide a linear-removal mode. You have two alternative paths:

- **Rebuild the index.** Collect the surviving ids in order, create a fresh `IdMapIndex`, and re-add the vectors sequentially.
- **Use external buffering.** Maintain an ordered `Vec` of ids outside TurboVec and treat the index as an unordered pool.

Both strategies trade the **O(1)** deletion speed of TurboVec for sequence stability.

## Performance Characteristics

- **Time complexity:** `IdMapIndex::remove` runs in **O(1)** time because hash-map lookups and a single swap-remove are constant-time operations.
- **Space complexity:** The id tables `slot_to_id` and `id_to_slot` shrink by one entry, so no extra allocations are required.
- **Order guarantee:** None. After deletion, the element at the final index is relocated into the vacated slot.

## Summary

- TurboVec deletes vectors using a **swap-remove** strategy inside `TurboQuantIndex`.
- The `IdMapIndex::remove` method in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) completes in **O(1)** time by swapping the last vector into the deleted slot.
- External id mappings are patched in place via `slot_to_id` and `id_to_slot`.
- **Insertion order is not preserved** after a deletion.
- Applications that need ordered deletion must rebuild the index or handle ordering outside of TurboVec.

## Frequently Asked Questions

### Does TurboVec preserve insertion order when deleting vectors?

No. TurboVec uses swap-remove semantics, so the vector at the last slot is moved into the position of the deleted vector. This destroys the original insertion sequence to achieve O(1) performance.

### What is the time complexity of `IdMapIndex::remove`?

`IdMapIndex::remove` is **O(1)**. It performs a constant-time hash-map lookup, a single `swap_remove` on the inner index, and updates the bidirectional id tables in place.

### How does TurboVec update id mappings during a deletion?

After the inner index swaps the last vector into the deleted slot, `IdMapIndex::remove` reads the moved vector’s id from the end of `slot_to_id`, writes it into the vacated slot, and updates `id_to_slot` so that future lookups resolve correctly. Finally it pops the trailing entry from `slot_to_id`.

### Can I force TurboVec to maintain order during deletion?

No, TurboVec does not expose an ordered removal API. If order must be kept, you should rebuild the index with the surviving vectors in the desired sequence, or manage an ordered layer outside of the index.