The Shape-Shifting Index: Why Your Search Index Should Be Two Different Data Structures

If you have ever designed a storage engine, sooner or later you'll encounter a fork in the road: do you want to use an LSM (Log-structured merge) tree or a B-tree as your foundational data structure? LSM trees (used by RocksDB, Cassandra) are optimized for fast writes, while B-trees (used by Postgres, MySQL) are optimized for fast reads. But if you're building a search engine — one that handles logs, metrics, and vector embeddings at the same time — neither answer is quite right.

We ran into this when building the storage engine behind Infino. The workload is brutal: millions of log lines per second during ingestion, then complex prefix queries and aggregations during analysis. We needed something that could handle both without compromise.

The answer turned out to be surprisingly simple. Don't pick one data structure. Pick two.

The problem with picking one

Let us illustrate the issue of picking one data structure with another example: HashMap vs binary search trees. A HashMap is the obvious choice for fast writes. In practice, it gives O(1) insertion and lock-free concurrency with something like DashMap in Rust. But HashMaps are terrible at prefix queries. Prefix searches such as "Give me all keys starting with error.timeout." are inefficient — you have to look at every single key in your HashMap to get an answer.

A sorted structure such as a B-tree fixes the prefix problem. The keys are ordered, so prefix search is a range scan. But now every insert has to maintain that order. Under high write pressure, you're constantly splitting and merging nodes to keep the tree balanced.

What if you didn't have to choose?

The shape-shifting trick

Here's the idea to support both a high volume of writes as well as prefix searches. While a segment of data is accepting writes, store terms in a plain concurrent HashMap. Inserts are fast, there is no ordering overhead, and multiple threads can write simultaneously.

Once the segment reaches a configured threshold — based on its size — we transform the HashMap into a completely different structure that is optimized for reads, and create a new empty segment that is now ready to accept writes. Once the new segment is full, again convert it to the read-optimized structure, and create a new segment to accept more writes, and so on.

Let us call the write-optimized data structure LiveIndex, and the read-optimized data structure FrozenIndex. Below is what they may look like — runnable code is available in the infino-public-experiments repository on GitHub.

// Phase 1: Write-optimized
struct LiveIndex {
    terms: DashMap<String, u64>,
}

// Phase 2: Read-optimized, suitable for prefix searching
struct FrozenIndex {
    fst: FstMap<Mmap>,
    values: Vec<u64>,
}

The two structures above serve the same purpose: map a term to its numeric identifier. However, they have radically different performance profiles as we'll see in the next section.

Note that the read-optimized data structure above is a Finite-state transducer (FST), which we use at Infino extensively. FSTs are a fascinating data structure, and their use at Infino could be the topic of another blog post. If you'd like to read about them, Andrew Gallant's blog post gives an excellent overview.

The benchmark

You can run the benchmark in infino-public-experiments yourself. Here is an example run on a Macbook Pro M4 Max for 1M terms. No surprises about the trade-off — the HashMap wins on exact lookups, and the FST wins on prefix searches. Note that FST also has a much smaller memory footprint due to its compact nature, and since it can be memory-mapped directly from a file on the disk. In practice, lower memory consumption translates to lower cost.

The freeze operation

The transformation from HashMap to FST is a one-time cost paid when a segment is full. For 1M terms, the freeze operation takes 185ms on Apple MacBook Pro M4 Max. Since every read operation after the freeze benefits from the faster structure, this one-time cost is easily justified.

fn freeze(self) -> FrozenIndex {
    // Step 1: Sort the keys. FSTs require sorted input —
    // this is what enables the suffix sharing.
    let mut sorted: Vec<(String, u64)> = self.terms.into_iter().collect();
    sorted.sort_unstable_by(|a, b| a.0.cmp(&b.0));

    // Step 2: Build the FST. Each term maps to an index
    // into a side array that holds the actual values.
    let mut builder = MapBuilder::memory();
    let mut values = Vec::with_capacity(sorted.len());
    for (i, (term, val)) in sorted.into_iter().enumerate() {
        builder.insert(term, i as u64).unwrap();
        values.push(val);
    }

    // Step 3: Write to disk and memory-map.
    let bytes = builder.into_inner().unwrap();
    write_to_disk(&bytes);
    let mmap = memory_map_from_disk();
    let fst = FstMap::new(mmap).unwrap();

    FrozenIndex { fst, values }
}

The bigger principle

This pattern — using one structure for writes and a different one for reads — isn't limited to term indexes. It shows up everywhere in database design once you start looking.

• Time-series databases buffer incoming metric points in a mutable array, then compress them into columnar blocks when the time window closes.
• Log stores collect events in a write-optimized buffer, then build inverted indexes and posting lists once the data is sealed.
• Vector databases maintain a growing HNSW graph in memory during ingestion, then serialize it into memory-mapped files for serving.
• Analytics engines accumulate rows in append-only buffers, then convert them to Parquet-style columnar files for fast scans.

The above are real examples from Infino's storage engine architecture. The insight is always the same: mutable data and immutable data have different physics. A data structure that's good for both is actually good at neither. When you know the data won't change, you can build structures that would be way too expensive to maintain on every write (such as FSTs, compressed posting lists, pre-sorted range trees) and amortize the build cost over millions of reads.

Try it yourself

The benchmark code is available at github.com/infinohq/infino-public-experiments. Clone it, run cargo run --release in the shape-shifting-index directory, and see the numbers on your own hardware. The FST library we use in this benchmark is BurntSushi's fst crate, and the hashmap library is xacrimon's dashmap crate.

If you're interested in how this pattern fits into a larger system — one that handles logs, metrics, and vector search in a single engine — check out Infino.