今更という感じだが、LevelDB について調べた。
table_format にあるように、LevelDB の SST の中身は block に分かれている。 block のなかは key-value の組が複数個入っている。 block ではキーのプレフィックスを圧縮したり block そのものを圧縮していたりするらしい。
このようなデータ構造では馬鹿正直にデータのルックアップにスキャンをしていたら大変なので index block を持っている。 index block もソースコードを読むと block 構造になっている。
さて、index によってキーが入っていそうな block がルックアップされたとしても、 実際 block を舐めるのはブロック自体の圧縮や、キーのプレフィックス圧縮があるのでまだコストが高い。 そのためオプションだが bloom フィルターを用いてキーがあるかどうか確認できるようになっている。
ここまでで単一の SST 内の検索が可能になった。 LevelDB は複数の SST が DB を構築しているため、SST 自身のルックアップが必要になる。
このルックアップは単純で、SST はキーの上限と下限がわかるので、各 level で二分探索していけば良い。 ただし level-0 では SST 間でキーのオーバーラップがあるらしいのでキーを含む SST 全部を検索対象にする。
また LevelDB は SST になる前のデータを memtable としてメモリ上に持っている。 こちらは skiplist で検索可能になっている。
