データ指向アプリケーションデザインの3章ストレージと抽出を読んだ。

データベースが利用しているデータ構造 🔗

ハッシュインデックス 🔗

ハッシュインデックスでは、データをログとして管理する。ここでいうログは追記だけが可能なデータ構造を指し、いわゆるアプリケーションログのように人間が読める形式でなくても良い。さらにログは複数のセグメントに分割される。各セグメントは、キーからそのキーを持つ最新のデータの位置を検索できるハッシュテーブルを持つ。

書き込み時は、書き込み用のセグメントにデータを追記し、ハッシュテーブルを更新する。書き込み用のセグメントがある一定サイズを超えた場合はファイルをクローズして、新しくセグメントを作成する。そして作成したセグメントを新しい書き込み用のセグメントとする。

読み込み時は、探しているキーを持つデータが見つかるまで、新しいセグメントから順にハッシュテーブルを検索する。

バックグラウンドプロセスとして、クローズ済みのセグメントに対してコンパクションとマージを行う。コンパクションはセグメントを圧縮する処理のことで、セグメント内にキーが重複しているデータがあれば最新のものを残してほかを削除する。マージは名前のとおり2つのセグメントを1つにまとめる。

SSTableとLSMツリー 🔗

SSTableとLSMツリーもハッシュインデックスと同じく、データを複数のセグメントに分割して管理する。各セグメント内のデータはキーでソートされている。このようなセグメントをソート済み文字列テーブル（Sorted String Table, 以下SSTable）と呼ぶ。各SSTableは、疎なハッシュテーブルを持つ。このような構造全体をLog-Structured Merge-Tree（LSMツリー）と呼ぶ。

書き込み時は、インメモリのバランスドツリーにデータを追記する。このバランスドツリーはmemtableと呼ばれる。memtableがある一定サイズを超えたら、SSTableとしてファイルに書き出す。

読み込み時は、まずmemtableを検索し、その後SSTableを新しいものから順に検索する。memtableとSSTableを検索するときは、それぞれが持つ疎なハッシュテーブルを利用する。ハッシュテーブルが持つキーの中から探しているキーと最も近いものを選び、対応するデータの位置を調べる。その周辺を走査して探しているキーを持つデータを見つけ出す。

バックグラウンドプロセスとして、SSTableに対してコンパクションとマージを行う。SSTableはソートされているので、マージソートと似たアルゴリズムで高速にマージできる。

Bツリー 🔗

Bツリーもデータを複数のセグメントに分割して管理する。このセグメントのことをBツリーではページ（もしくはブロック）と呼ぶ。ページ内のデータはキーでソートされている。また、ページのサイズは固定されている。ページはキーの値として他のページへの参照を持つことができ、参照関係の全体は木構造になる。データはリーフに格納されている。各ページが持てる子ページへの参照の数を分岐係数と呼ぶ。通常、分岐係数は数百のオーダーになる。

書き込み時は、まずデータを書き込むリーフを探す。リーフ以外のページに含まれるキーと値は、キーの範囲とその範囲のデータが含まれる子ページへの参照を示している。ルートから順に、書き込もうとしているデータのキーを含む子ページを辿っていくことで、探しているリーフを見つけることができる。書き込みたいデータのキーがリーフに存在する場合は値を上書きする。存在しない場合は、リーフに空き領域があるかどうかで処理が変わる。空き領域がある場合はデータを追記する。ない場合は、ページを2分割してからデータを追記し、それら2つのページを参照するように親ページを更新する。このアルゴリズムはページの木を平衡に保つ。

読み込み時は、探しているキーを含むリーフを書き込み時と同じ方法で見つけ出す。