# How to Use IdMapIndex for Stable External Vector IDs with O(1) Removal

> Learn how to use IdMapIndex for stable external vector IDs. Achieve O(1) removal with TurboQuantIndex and bidirectional hash maps for constant-time operations.

- Repository: [Ryan Codrai/turbovec](https://github.com/RyanCodrai/turbovec)
- Tags: how-to-guide
- Published: 2026-07-27

---

**Use `IdMapIndex` to wrap `TurboQuantIndex` with bidirectional hash maps that translate between stable external `u64` IDs and internal slot indices, enabling constant-time removal via swap-remove semantics.**

The `IdMapIndex` type in the RyanCodrai/turbovec repository provides a robust solution for assigning persistent external identifiers to vectors while maintaining the high-performance characteristics of the underlying quantized index. This wrapper bridges the gap between database primary keys or user-defined IDs and the positional storage requirements of the **TurboQuantIndex** engine.

## Understanding the IdMapIndex Architecture

`IdMapIndex` is a thin wrapper around the positional `TurboQuantIndex` that maintains two synchronized lookup tables in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) (lines 48-52):

- **`slot_to_id: Vec<u64>`** – Maps internal positional slots to external `u64` IDs
- **`id_to_slot: HashMap<u64, usize>`** – Maps external IDs back to their current slot position

This **bidirectional mapping** ensures that vector repositioning during removals remains transparent to API consumers. The tables are updated atomically on every mutation to keep internal storage and external identifiers consistent.

## Adding Vectors with Stable External IDs

To insert vectors with explicit identifiers, use the `add_with_ids` method (or `add_with_ids_2d` for 2-D inputs) implemented in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) (lines 55-78). The method validates that supplied IDs are unique, records the mapping in both tables, then delegates actual vector storage to the inner index.

```rust
use turbovec::IdMapIndex;

// Create an index with a 1536-dimensional space, 4-bit encoding
let mut idx = IdMapIndex::new(1536, 4).unwrap();

// Prepare vectors and external IDs
let vectors: Vec<f32> = vec![0.0; 1536 * 3];  // 3 vectors
let ids: Vec<u64> = vec![1001, 1002, 1003];   // stable external IDs

// Add vectors with their IDs
idx.add_with_ids(&vectors, &ids).unwrap();

```

*Explanation:* The `new` constructor initializes both the inner quantized index and the empty mapping tables. `add_with_ids` performs the O(n) encoding and HashMap inserts necessary to establish the bidirectional relationships before storage.

## Implementing O(1) Removal

The **O(1) removal** mechanism relies on constant-time HashMap lookups combined with swap-remove semantics. When `remove(external_id)` is called, the implementation in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) (lines 58-66) executes three steps:

1. **Lookup** – Queries `id_to_slot` to find the internal slot index (O(1))
2. **Swap-remove** – Calls `inner.swap_remove(slot)` to pop the last vector into the vacated position (O(1))
3. **Remap** – Updates `slot_to_id` for the moved vector and removes the deleted entry from `id_to_slot` (O(1))

No linear scan is required because the HashMap provides direct access to the internal position, and swap-remove avoids shifting subsequent elements.

```rust
// Remove by external ID - constant time operation
idx.remove(1002);
assert_eq!(idx.len(), 2);

```

## Search and Stable ID Translation

After a search operation, `IdMapIndex` translates the slot indices returned by `TurboQuantIndex` back to external IDs via the `slot_to_id` vector. This translation occurs in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) (lines 44-166) and adds O(nq·k) overhead to the search results, where `nq` is the number of queries and `k` is the number of neighbors returned.

```rust
// Search returns stable external IDs, not internal slots
let query: Vec<f32> = vec![0.0; 1536];
let (scores, found_ids) = idx.search(&query, 2);
println!("Top-2 IDs: {:?}, scores: {:?}", found_ids, scores);

```

## Performance Characteristics

According to the header documentation in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) (lines 29-36), the complexity characteristics are:

- **Adding vectors:** O(n) encoding plus O(n) HashMap inserts
- **Removing an ID:** O(1) HashMap lookup plus O(1) swap-remove
- **Searching:** Same cost as the inner index plus O(nq·k) slot-to-ID translation pass

The memory overhead is minimal: one `u64` per vector in `slot_to_id` and one HashMap entry per vector in `id_to_slot`.

## Summary

- **IdMapIndex** provides **stable external IDs** via bidirectional mapping between `u64` identifiers and internal storage slots
- **O(1) removal** is achieved through HashMap lookup and **swap-remove** semantics without index rebuilding
- Search results automatically translate internal positions to stable external identifiers
- Implementation resides primarily in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) with re-exports in [`turbovec/src/lib.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/lib.rs)
- Unit tests verifying ID mapping and removal semantics are located in [`turbovec/tests/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/tests/id_map.rs)

## Frequently Asked Questions

### How does IdMapIndex maintain O(1) removal performance?

It stores a HashMap (`id_to_slot`) that converts external IDs to internal slots in constant time. When removing, it looks up the slot, calls `swap_remove` on the inner `TurboQuantIndex`, and updates the mapping tables for the moved vector—all O(1) operations. This avoids the O(n) cost of linear scanning or shifting elements that traditional vector storage would require.

### Can I use string IDs instead of u64?

The current implementation in [`turbovec/src/id_map.rs`](https://github.com/RyanCodrai/turbovec/blob/main/turbovec/src/id_map.rs) specifically uses `u64` for external IDs. To use string identifiers, you must hash them to `u64` values before insertion, or maintain a separate string-to-u64 mapping in your application code. The underlying storage is hardcoded to expect 64-bit unsigned integers.

### What happens to existing IDs after a removal?

Remaining vectors retain their stable external IDs because the wrapper updates both `slot_to_id` and `id_to_slot` tables to reflect new positions after the swap operation. Only the internal slot indices change during the `swap_remove`; external identifiers remain persistent throughout the lifetime of the index.

### Is IdMapIndex thread-safe for concurrent searches?

Yes, as the underlying `TurboQuantIndex` supports concurrent reads and the mapping tables are only modified during `add` or `remove` operations, which require mutable access. Multiple threads can safely call `search` simultaneously through immutable references, making it suitable for read-heavy workloads.