ハッシュインデックス

新規追加でも更新でもログに対する操作は同じなので、新たに挿入したログレコードのオフセットでハッシュマップを更新すればいい

ログが長くなったらマージして短くする

メモリにハッシュマップが乗らなくなると困る

ハッシュマップをディスクに置いてしまうのは非効率らしい

実例

Bitcask (Riak)

各キーに対する更新が頻繁に行われるがキーの空間自体は大きくならない場合に有利になる

実装上課題になるポイント

ファイルフォーマット

レコードの削除→墓石 tombstoneを用いる

クラッシュのリカバリ

部分的に書き込まれたレコード

並行性の制御

シーケンシャル書き込みはHDDでもSSDでも有利

HDDだと特にそうだがフラッシュベースのSSD（Solid State Drive）であっても、ある程度はシーケンシャルな書き込みの方が望ましい

pros

ログが追記オンリーなので並行性制御やクラッシュリカバリに有利

cons

メモリにハッシュマップが収まらなくなると不利

範囲クエリが効率的ではない