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

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 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 is concise and explicitly relies on swap_remove:

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

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 and the test suite in 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 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.

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