swap_remove in turbovec: TurboQuantIndex vs IdMapIndex Explained

swap_remove is an O(1) TurboQuantIndex method that removes a vector by swapping it with the last element and truncating the list, and you should choose TurboQuantIndex for maximum performance when you only need positional access, while IdMapIndex is required for external 64-bit IDs, ID-based deletion, and filtered allowlist searches.

The turbovec library provides two primary index types for approximate nearest neighbor search in Python: TurboQuantIndex for lightweight quantized storage and IdMapIndex for ID-mapped collections. Understanding how swap_remove operates in the Rust source code is essential for deciding which index structure matches your workload. Both the Python bindings and the underlying core logic are implemented in the RyanCodrai/turbovec repository.

What Is swap_remove?

swap_remove is a method exposed on TurboQuantIndex that deletes a vector at a given position in O(1) time. As implemented in turbovec-python/src/lib.rs at lines 4010–4055, the function acquires a write lock on the internal storage, swaps the target element with the last element in the backing vector list, and truncates the list. Because this operation does not preserve the original ordering of vectors, it avoids the linear shifting cost associated with standard ordered removal.

// TurboQuantIndex.swap_remove implementation
// Source: turbovec-python/src/lib.rs L4010-L4055
fn swap_remove(&self, py: Python<'_>, idx: &Bound<'_, PyAny>) -> PyResult<usize> {
    if let Ok(i) = idx.extract::<usize>() {
        // Bounds check + removal share one write guard
        let removed = py.detach(|| {
            let mut inner = lock_write(&self.inner);
            let len = inner.len();
            if i < len {
                Ok(inner.swap_remove(i))
            } else {
                Err(len)
            }
        });
        match removed {
            Ok(moved) => return Ok(moved),
            Err(len) => Err(PyIndexError::new_err(...)),
        }
    }
    // ...type-checking and error handling omitted for brevity...
}

The method accepts a Python index object, performs a bounds check under a single write guard, and returns the index of the vector that was moved into the vacated slot. If the provided index is out of bounds, it raises a PyIndexError with the current length of the index.

When to Choose TurboQuantIndex Over IdMapIndex

Although both indexes share the same quantization and search engine, their APIs and memory layouts differ. The decision depends on whether your application requires stable external identifiers or can tolerate order-agnostic, position-based management.

Select TurboQuantIndex for Raw Performance

Choose TurboQuantIndex when your workload meets the following conditions:

• No external identifiers needed: You store raw vectors and refer to them only by their numeric position.
• Minimal memory footprint: The index avoids the auxiliary hash-map overhead that IdMapIndex uses to track 64-bit IDs.
• Simple operations: Your workflow consists of add, fast top-k search, and occasional swap_remove by position.

For pure vector workloads where you control item lifecycles by index, TurboQuantIndex delivers the fastest path.

Select IdMapIndex for External ID Mapping

Choose IdMapIndex when you need user-defined identifiers or advanced query filtering:

• add_with_ids: Associates each vector with a user-defined u64 identifier at insertion time.
• remove(id): Deletes a vector by its external ID without needing to know its internal slot.
• allowlist filtering: The search method accepts an allowlist that restricts results to a subset of external IDs, which is critical for multi-tenant or permission-based retrieval.
• contains(id): Quickly checks whether a specific external ID is present in the index.

The IdMapIndex is built on top of the same core engine found in turbovec-core/src/lib.rs, but it trades a small memory overhead for these mapping capabilities.

Code Examples

Removing a Vector with swap_remove in TurboQuantIndex

The following example inserts five random vectors and removes the item at position 2. The swap_remove call returns the index of the vector that was moved into slot 2.

import numpy as np
import turbovec

# Create a quantized index (dimension will be inferred on first add)

index = turbovec.TurboQuantIndex()
vectors = np.random.randn(5, 128).astype(np.float32)   # 5 vectors, dim=128

index.add(vectors)

# Remove the vector at position 2 (third vector)

moved_idx = index.swap_remove(2)
print(f"Removed slot 2; vector from slot {moved_idx} moved into its place")
print(f"Current size: {len(index)}")

Adding, Removing, and Filtering with IdMapIndex

This example demonstrates add_with_ids, ID-based remove, and an allowlist-restricted search:

import numpy as np
import turbovec

# Create an ID-mapped index

index = turbovec.IdMapIndex()
vectors = np.random.randn(4, 64).astype(np.float32)
ids      = np.array([101, 102, 103, 104], dtype=np.uint64)

# Insert vectors with their external IDs

index.add_with_ids(vectors, ids)

# Delete a vector by its external identifier

removed = index.remove(103)   # returns True

print(f"ID 103 removed? {removed}")

# Search, limiting results to a subset of IDs

queries = np.random.randn(2, 64).astype(np.float32)
allowlist = np.array([101, 104], dtype=np.uint64)
scores, result_ids = index.search(queries, k=3, allowlist=allowlist)
print("Top-k IDs:", result_ids)

Summary

• swap_remove is an O(1) deletion method on TurboQuantIndex that swaps the target vector with the last element and truncates; it does not preserve insertion order.
• Choose TurboQuantIndex for the fastest, simplest vector-only workloads that rely on positional access.
• Choose IdMapIndex when you need stable external 64-bit identifiers, ID-based removal, containment checks, or filtered allowlist searches.
• The Python binding for swap_remove lives in turbovec-python/src/lib.rs (lines 4010–4055), while the core Rust implementations for both indexes reside in turbovec-core/src/lib.rs.

Frequently Asked Questions

What is the time complexity of swap_remove in TurboQuantIndex?

swap_remove runs in O(1) time because it swaps the target element with the last item in the internal buffer and then truncates the list. It never shifts remaining elements, which is why it is significantly faster than an order-preserving removal.

Can I use swap_remove if I need to preserve vector order?

No. swap_remove explicitly does not preserve vector order. If you require stable ordering or need to delete by a stable external identifier, use IdMapIndex and call remove(id) instead of swap_remove.

Does IdMapIndex support filtering searches to a subset of IDs?

Yes. IdMapIndex.search() accepts an allowlist parameter, which is a NumPy array of uint64 external IDs. The query then returns top-k results drawn only from that allowed subset, enabling multi-tenant or permission-based retrieval patterns.

Where are the swap_remove and core index implementations located?

The swap_remove Python binding is implemented in turbovec-python/src/lib.rs at lines 4010–4055. The underlying core Rust data structures for both TurboQuantIndex and IdMapIndex are defined in turbovec-core/src/lib.rs according to the turbovec source tree.

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