コード → https://github.com/wuxb45/lsm-trie-release
USENIX ATC15の論文。これはタイトルだけで読みたくなる論文ですね。LSMで、trieですよ。
LSMは普通はtreeですよね。Log Structured Merged Treeという古くからある有名なデータ構造。私も何度か実装しました。追加がシーケンシャルwriteになるので高速になり、けっこう便利なのですよね。一方でtrieというのはインデックスがエッジに含まれるtreeで、これも非常に古くからあるデータ構造。組み合わせたらどんな素敵なんだろう、という話。