B+木を使ったデータベースの設計をしよう。これを使うと、レコードの順序に基づいた検索ができる。範囲検索とか、前方一致検索ができる。その基本的な構造について考察する。
ハッシュテーブルのデータベースはO(1)という究極の時間計算量を実現する。レコード数がいくら増えても個々のレコードの処理にかかる時間が一定なのだ。これは理論だけの話ではなく、実際に性能テストをしても一定になる。しかもハッシュテーブルはスロットロックとの親和性が高いので、並列化もしやすい。一方で、欠点もある。キーの完全一致でしか検索できないことだ。ハッシュ法ではレコードの順序という概念が消失してしまう。「5以上の」とか「abcで始まる」みたいな検索条件は指定できない。それらを実現するには「ordered」な、すなわち「順序付き」のデータ構造が必要となる。順序付きのデータ構造はO(log N)という計算量を持つのが典型であり、つまり個々のレコードの処理時間はレコード数の対数に比例する時間がかかる。突き詰めると大抵のアルゴリズムは二分探索なので、レコード数をNとするとlog2(N)に比例する時間がかかるということだ。2で1、4で2、8で3、256で8、65536で16、42億で32だ。O(1) には負けるが、計算機の上で扱うには十分に早い計算量だ。C++の標準ライブラリで例えれば、std::mapやstd::setは順序付きのデータ構造であり、std:unordered_mapやstd::unordered_setは順序付きでないデータ構造だ。ちなみにstd::mapやstd::setは赤黒木というツリー系のデータ構造で実装されていて、std:unordered_mapやstd::unordered_setはハッシュ法で実装されている。
さて、ファイル上に表現した連想配列であるDBMでも、順序付きのデータ構造を実現したい。そうすると必然的にツリー系のアルゴリズムが選択される。ランダムアクセスが不得意だったりフラグメンテーションの問題に悩まされがちなファイル上のデータ構造では、個々のレコードをノードとする赤黒木は効率が悪い。その代わりに、複数のレコードを一括して木のノードにするB木やB+木やその変種を用いるのが一般的だ。その中でもB+木が定番だ。順序つきのデータベースはRDBのインデックスとしてもよく使われる。OracleもMySQLもPostgreSQLもインデックスにはB+木の変種を使っているだろう。ということで、我らがDBMでもB+木を実装しようじゃないか。まず、以下の図をご覧いただきたい。
B+木は、多進平衡木の一種である。まず、根ノードがあり、根ノードは1個以上で任意の数までの子ノードを持つことができ、その子ノードもさらに子ノードを持つことができ、任意の数の階層を経て、子を持たないノードに到達する。子を持たないノードはリーフノードと呼ばれ、子を持つノードは内部ノードと呼ばれる。個々のノードが3つ以上の子を持てるので「多進」で、個々のリーフノードから根ノードまでの距離が一定範囲に収まるので「平衡」である木が多進平衡木だ。ちなみにB木にもその定義が当てはまるのだが、Key-Valueのレコードを保存するにあたり、内部ノードにも値が保存されるのがB木、リーフノードにしか値が保存されないのがB+木だ。B+木の方がデータベース業界ではよく使われる。後述するイテレータが実装しやすいからだ。
個々のノードをファイルに保存できればDBMの上でB+木が表現できる。そのためには、各ノードにIDを振るとともに、ノードのデータを単一の文字列としてシリアライズする方法を決めればよい。そうすると、IDをキー、シリアライズしたデータを値としたkey-value構造に落とし込める。そうしてできたkey-valueレコードを、既に設計してあるハッシュデータベースに保存すれば良い。B+木の一つのレコードにアクセスするにはハッシュテーブルの複数のレコードにアクセスすることが必要になるわけだが、ハッシュテーブルの計算量はO(1)なので、O(log N) * O(1) = O(log N) ということで、全体の計算量に影響はない。
B+木のアルゴリズムをストーリー仕立てで説明していこう。Life of B+ treeである。まず、データベースが作成されたその瞬間。リーフノードが一つ作られる。内容は何もないが、そのノードを識別するために1というIDが振られる。データベースにレコードが追加されると、そのレコードはキーの昇順で並べられて、リーフノードに収納される。データベースが閉じられる際には、レコードを含んだリーフノードは単一の文字列としてシリアライズされて、IDをキー、シリアライズされた文字列を値としたKey-Valueレコードとして、ハッシュデータベースに保存される。データベースを再び開いてそのリーフを読み込む際には、IDを指定してKey-Valueレコードを読み込み、値をデジリアライズして元のデータを復元する。
リーフノードにはどんどんレコードが追加されていく。リーフノードの中のレコードはキーの昇順で並べられるので、二分探索で所望のノードを探すことができる。ところで、リーフノードは、シリアライズした際の文字列のサイズが一定の長さを超えると見込まれる場合に、2つに分割される。あるリーフノードにA, B, C, Dというレコードが存在したとして、それを分割するなら、AとBは元のレコードに残り、CとDは新しく作られたレコードに移動させられる。新しく作られたリーフノードには2というIDが振られる。リーフノードが分割された際には、二つのリーフノードを繋ぐ親として、内部ノードが作られる。その内部ノードにもIDが振られる。10001としよう。内部ノードでは、そこから到達可能な最初の子供をheir（長子）として登録するとともに、それ以降の子ノードを扱うにはリンクという構造体を追加する。個々のリンクは、子ノードの最初のキーと、子ノードのIDを持つ。唯一であったリーフノードが2つに分割された状態では、AとBを格納した元のノード（ID=1）が親のheirであり、新しく作られたCとDを含むノードの情報がリンクとして登録される。そのリンクのキーはCで、IDは2ということになる。以後、新しくレコードが追加される場合には、内部ノードの木構造を辿って対象のリーフノードが特定されることになる。つまり、内部ノードを見て、Cより前であればheirであるID=1のノードを対象とし、C以後であればそのリンクの子であるID=2のノードを対象とすることになる。検索も同様の手順で行う。リーフノード同士は双方向連結リストで繋がれる。したがって、リーフノードが分割される際には、自分のnextに新ノードのIDを登録し、新ノードのprevに自分のIDを登録する。
レコードの追加とリーフノードの分割を繰り返すと、親の内部ノードに多数のリンクが蓄積されることになる。リンクはキーの昇順で並べられるので、所望のリンクは二分探索で探すことができる。リンクの数が一定数を超えた時、その内部ノードは二つに分割され、さらに上に親である内部ノードが作られる。そうして木の高さが徐々に上がっていく。一方で、レコードが消された場合も見ていこう。レコードを消すにあたっては、そのレコードが所属するリーフノードが特定され、該当レコードのデータが削除される。その際に、そのレコードをシリアライズした際の文字列のサイズが一定の長さを下回った場合には、そのリーフは直前または直後の兄弟と統合される。兄弟とは、共通の親ノードを持つノードである。例えば、レコードAとBを持つノード1からBが削除されたとして、Aだけが残ってそのサイズが閾値を下回ったとする。その際には、その兄弟であるノード2と結合される。ノード2はCとDを持つので、ノード2はAとCとDを持つノードとなり、ノード1は消える。それに伴い、親ノードにheirとして登録されていた情報は抹消されて、ノード2は新たなheirとなる。ノード2のためのリンクは抹消される。そうすると親ノードのリンク数は減る。そうしてレコードの削除が繰り返されるとしよう。親ノードが持つリンク数が一定より少なくなると、そのノードはその兄弟と結合される。その際の親ノードの処理はリーフを結合する時と同じである。子ノードが一つになった内部ノードはその存在意義を失うので、必ず兄弟と結合されることになる。もし根ノードの子が一つになった場合、その唯一の子を新たな根に指定して、古い根ノードは削除する。それによって木の高さが一つ下がる。
key-valueのレコードはリーフノード上にしか存在しないところがB+木の良いところだ。そしてそのリーフノードは双方向連結リストで繋がれているので、レコードを昇順あるいは降順に辿るイテレータが容易に実装できる。例えば、「10以上20未満」というクエリを処理するなら、まず10以上の最初のレコードを探すべく根ノードから二分探索を繰り返しつつ該当のリーフノードにたどり着き、そこでも二分探索をして10以上の最初のレコードを特定する。それからイテレータを一つず進め、20以上のレコードに出くわしたら処理を完了させる。リーフノードの最後のレコードで処理が終わらなければ、nextリンクを辿って次のリーフノードに飛び、処理を続ける。文字列が辞書順に並んでいるデータベースなら、同じやり方で前方一致検索ができる。レコードを並べる際に使われる比較関数は任意のものを設定できる。一貫した全順序比較を行う関数であれば、どんな関数を指定しても良い。
以上の説明でB+木のアルゴリズムを網羅した気分だが、どうだろう。要点は、個々のノードをシリアライズした時のサイズが一定を上回った場合にはノードが分割され、一定を下回った場合にはノードが結合されるということだ。これによって、各ノードのサイズが一定範囲に保たれる。デフォルトでは、ノードのサイズがOSのページサイズである4096より大きくなった場合には分割され、その半分である2048を下回った場合には結合されるということになる。ということは、実効データの利用率の期待値は、75%くらいになる。ただ、実際にはもうちょい複雑だ。サイズが2000になったノードを兄弟と結合させたいとして、その兄弟のサイズが4000だった場合に、結合したら6000になってしまう。それは4096を超えているから、再分割すべきだろうか。あるいは、結合させるのではなく一部のレコードだけを兄弟に引っ越しさせるという手もある。このあたりは同じB+木の枠組みでも様々な工夫が考えられるところだ。この問題に正解はなく、典型的なユースケースを想定して性能実験を繰り返して決めるしかない。とりあえず最初は愚直に兄弟と結合させる実装にしておこう。
ところで、各ノードの情報が参照される度にデータを読み込んでデシリアライズし、更新される度にデータをシリアライズして書き込んでいては、めちゃ遅くなってしまう。なので、B+木の実装においてはキャッシュ機構が非常に重要になる。キャッシュの構造は、ノードのIDをキーにして、デシリアライズされたノードのオブジェクトを値とするオンメモリの連想配列である。シリアライズの書式やキャッシュの設計については次回以降に検討する。
