When to Use swap_remove vs IdMapIndex for Deletions in Turbovec

Use TurboQuantIndex::swap_remove when you manage slot indices yourself and can tolerate invalidation of external references; use IdMapIndex::remove when you need stable external IDs that remain valid after deletion.

Turbovec is a high-performance vector search library by RyanCodrai that stores vectors positionally inside a TurboQuantIndex. When deleting vectors, you must choose between the low-level swap_remove method that manipulates internal storage directly, or the IdMapIndex wrapper that maintains stable external identifiers. Understanding the trade-offs between swap_remove vs IdMapIndex for deletions in turbovec is essential for building both performant and maintainable applications.

Understanding TurboQuantIndex::swap_remove

The swap_remove method provides direct, O(1) deletion by rearranging the internal storage layout.

How swap_remove Works

According to the source code in [src/lib.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs#L92-L104), TurboQuantIndex::swap_remove deletes a vector by swapping the last vector into the removed slot and truncating the buffers. This positional manipulation means the vector that previously occupied the last slot now lives at the index of the deleted vector.

The operation invalidates every external reference that relied on the old slot index. If other components of your system store slot numbers to reference vectors, those references become immediately stale after a swap_remove operation.

Performance Characteristics

• Time Complexity: O(1) - Performs a single swap and buffer truncation.
• Space Complexity: O(1) - No additional allocations required.
• Reference Safety: Destabilizes slot indices; any stored slot numbers may now point to wrong vectors.

When to Use swap_remove

Choose this method when you are writing performance-critical code that already tracks slot positions and can immediately update dependent indices. Use it in benchmarks, simple demos, or algorithms where you recompute index tables after each deletion. Avoid it when external systems rely on persistent identifiers for vectors.

Understanding IdMapIndex::remove

The IdMapIndex wrapper provides a higher-level abstraction that decouples external IDs from internal storage positions.

How IdMapIndex Handles Deletion

As implemented in [src/id_map.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs#L57-L80), the IdMapIndex::remove method accepts a stable u64 ID and performs three steps:

1. Looks up the current slot for the given ID using the internal id_to_slot hash map.
2. Calls TurboQuantIndex::swap_remove internally on that slot.
3. Updates the bidirectional mapping tables (slot_to_id and id_to_slot) to reflect the swap, ensuring that the external ID of the moved vector now points to the new slot.

This internal bookkeeping ensures that while the physical storage moves vectors via swap, the external IDs remain stable and valid for all remaining vectors.

Performance Characteristics

• Time Complexity: O(1) - One hash-map lookup plus the inner swap operation.
• Space Complexity: O(n) - Requires additional hash maps to maintain ID-to-slot mappings.
• Reference Safety: Preserves external ID stability; callers can continue using the same IDs after deletion.

When to Use IdMapIndex::remove

Select this approach when you need stable external identifiers, such as persistent database keys, Python bindings, or any code that stores IDs rather than slot numbers. Use it when you want to delete by ID without exposing the inner slot layout to callers, or when multiple components need to reference vectors without coordinating on index shifts.

Code Examples

Direct swap_remove for Slot-Based Deletion

When you control slot indices and can handle the shift, use the low-level API directly:

use turbovec::TurboQuantIndex;

let dim = 256;
let mut idx = TurboQuantIndex::new(dim, 4).unwrap();
// Add 10 vectors...
idx.add(&vectors);
println!("len before: {}", idx.len());

// Delete the vector at slot 3 (the last vector moves to slot 3)
let moved_from = idx.swap_remove(3);
println!("vector previously at {} moved to slot 3", moved_from);
println!("len after: {}", idx.len());

Implementation reference: The swap_remove method swaps the last packed bytes into the deleted slot and truncates the buffers ([src/lib.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs#L92-L104)).

IdMapIndex::remove for ID-Based Deletion

When you need stable identifiers, use the wrapper that manages the mapping:

use turbovec::IdMapIndex;

let mut index = IdMapIndex::new(1536, 4).unwrap();
let vectors = vec![0.0_f32; 1536 * 3];
index.add_with_ids(&vectors, &[1001, 1002, 1003]).unwrap();

assert_eq!(index.len(), 3);
index.remove(1002);               // O(1) via inner swap_remove
assert_eq!(index.len(), 2);
assert!(!index.contains(1002));   // ID is gone, other IDs stay stable

Implementation reference: The remove method uses internal hash maps and then calls inner.swap_remove(slot) ([src/id_map.rs](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs#L57-L66)).

Summary

• Use TurboQuantIndex::swap_remove when you manage slot indices yourself, need maximum performance without hash-map overhead, and can immediately update any dependent references after deletion.
• Use IdMapIndex::remove when you require stable external u64 identifiers, want to abstract away internal storage layout, or have multiple components referencing vectors by persistent IDs.
• Both operations run in O(1) time, but IdMapIndex adds a small constant factor for hash-map lookups to maintain ID stability.
• Direct swap_remove invalidates slot-based references, while IdMapIndex::remove preserves external ID validity through bidirectional table updates.

Frequently Asked Questions

Does swap_remove change the IDs of other vectors?

When using IdMapIndex::remove, the external IDs of other vectors remain stable and unchanged. However, when using TurboQuantIndex::swap_remove directly, there are no external IDs—only slot indices change. The vector that was previously at the last slot moves to the deleted slot, so any code storing raw slot indices must update its references.

Is IdMapIndex significantly slower than swap_remove?

Both methods operate in O(1) time. IdMapIndex::remove adds one hash-map lookup and table updates to the underlying swap_remove operation. For most applications, this overhead is negligible compared to the cost of maintaining manual index consistency across your codebase.

Can I use swap_remove with IdMapIndex?

You should not call swap_remove directly on the internal TurboQuantIndex if you are using IdMapIndex as a wrapper. Doing so would bypass the ID-to-slot mapping maintenance, causing the IdMapIndex tables to become inconsistent with the actual storage. Always use IdMapIndex::remove to ensure the bidirectional tables stay synchronized.

What happens to the last vector when I delete from the middle?

In both approaches, the vector physically occupying the last storage slot moves into the position of the deleted vector. With swap_remove, you receive the old last index as a return value. With IdMapIndex::remove, this shift happens internally, and the mapping tables are updated so that the moved vector's external ID now points to the new slot location.

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