lsm-trie · research

LSM-trie

LSM-trie is a hash-routed, multi-level key-value store that groups lookup filters to limit out-of-memory metadata reads.

Routing: hash prefixes select table containers; suffixes select buckets. Grouped filters cover the same bucket position across sub-levels. Native ordered range search is not supported. [1]

Lookup: the pinned implementation checks active tables before traversing containers, where filter bits select candidate tables. A positive candidate still requires full-key verification. [2] [3]

Relations

related

Log-structured merge-tree, Bloom filter, Read amplification

Limitations

• The two-read design assumes resident upper-level metadata; false positives and bucket migrations can add reads. [1]

Citations

1. Wu, Xu, Shao and Jiang. LSM-trie. USENIX ATC 2015, pp. 71-82; sections 2.3-2.4, Table 1. (accessed 2026-11-11)
2. LSM-trie author code: recursive_lookup and db_lookup, pinned revision. (accessed 2026-11-11)
3. LSM-trie author code: full-key equality and recursive bucket lookup, pinned revision. (accessed 2026-11-11)

Further reading

4. Hesela: LSM-trie, cold metadata and false-positive counts. (accessed 2026-11-11)

JSON: /data/terms/lsm-trie.json