ハッシュデータベースを基盤に構築したB+木のデータベースを、以後、ツリーデータベースと呼ぶ。データベース全体のメタデータとして何を持つべきか、B+木の各ノードはどのようなデータを持つか、またどのようにシリアライズするか、ここで完全に詰めて定義する。
ツリーデータベースのメタデータは、ハッシュデータベースのメタデータセクションに設けておいた「オペイクデータ」フィールドに保持する。64バイトしか確保していないので、ギュウギュウに詰めて押し込む。
- マジックデータ
- オスセット0からの4バイトの文字列 "TDB" とそれに続くヌル文字。
- レコード数
- オフセット4からの6バイトのビッグエンディアン整数。
- 実効データサイズ
- オフセット10からの6バイトのビッグエンディアン整数。
- 根ノードのページID
- オフセット16からの6バイトのビッグエンディアン整数。
- 最初のリーフノードのページID
- オフセット22からの6バイトのビッグエンディアン整数。
- 最後のリーフノードのページID
- オフセット28からの6バイトのビッグエンディアン整数。
- リーフノードの数
- オフセット34からの6バイトのビッグエンディアン整数。
- 内部ノードの数
- オフセット34からの6バイトのビッグエンディアン整数。
- リーフノードの最大サイズ
- オフセット46からの3バイトのビッグエンディアン整数。
- 内部ノードの最大枝数
- オフセット49からの3バイトのビッグエンディアン整数。
- 木の階層数
- オフセット52からの1バイト整数
- 比較関数の型ID
- オフセット53からの1バイト整数
- オペイクデータ
- オフセット54から10バイトの任意の文字列
マジックデータはツリーデータベースを識別するために用いる。ツリーデータベースをハッシュデータベースとして開くことはできるが、ハッシュデータベースをツリーデータベースとして開くことはできない。レコード数は現在の生きているレコードの数で、実効データサイズはキーのサイズと値のサイズの総計。
根ノードのIDは、ツリー探索のエントリポイントとして必要だ。最初と最後のリーフノードのIDは、全体を前と後ろからスキャンするイテレータで用いられる。リーフノードの数と内部ノードの数は、それぞれのクラスの新たなノードを作る時に連番のIDを振るのに使われる。ところで、それぞれのIDは6バイトの整数で表現されるので、変域は0から281兆ほどまでである。そのうち、211兆まではリーフノードに割り当て、そこから先は内部ノードに割り当てる。正確に言うと2^46*3までがリーフノードのIDの変域として予約され、それに1を足した値が最初の内部ノードのIDになる。つまりIDの大きさだけでリーフノードと内部ノードは区別できる。内部ノードの方が変域が狭いのは、リーフノードの方が多くなるからだ。この仕様だと、リーフノードの分割を211兆回より多く行うとデータベースが壊れる。でもそうするには20京回くらいの挿入と削除を行う必要があるので、10万QPSでレコードを挿入し続けても6600年は持つ計算になる。
リーフノードの最大サイズと内部ノードの最大枝数はチューニングパラメータだ。デフォルトは8130と256にしよう。ランダムアクセスに特化させるならリーフノードの最大サイズは4080がよいのだが、この辺りはもうちょい実験して考える。木の階層数はデータの操作には全く使われないのだが、デバッグやチューニングのためにメタデータとして記録することにする。
B+木には比較関数が設定できる。デフォルトは文字列の辞書順である。より厳密に言えば、符号なし8バイト文字列の辞書順だ。UTF-8やISO-8859-1ならば、デフォルトの比較関数で文字コードの辞書順と同じ並びになる。それ以外の文字コードを使いたかったり、大文字小文字の違いを無視したかったりする場合には、自分で比較関数を書いて設置できる。いくつかビルトインの比較関数を提供する予定で、それらには予めIDを振っておきたい。比較関数が異なる設定でデータベースを操作すると整合性が破壊されるので、メタデータとして登録しておくことは重要だ。関数のIDは以下の感じになるだろう。
- 1 = デフォルトの文字列比較
- 2 = ASCIIの大文字小文字を無視した文字列比較
- 3 = 10進数の文字列比較
- 4 = 16進数の文字列比較
- 255 = ユーザ定義関数
リーフノードは以下の書式でシリアライズする。
- 前のノードのID
- 6バイトのビッグエンディアン整数
- 次のノードのID
- 6バイトのビッグエンディアン整数
- レコードの繰り返し
- キーのサイズ。可変長整数
- キーの文字列。
- 値のサイズ。可変長整数
- 値の文字列。
内部ノードは以下の書式でシリアライズする。
- 長子のノードのID
- 6バイトのビッグエンディアン整数
- リンクの繰り返し
- キーの長さ。可変長整数
- キーの文字列
- 子ノードのID
これで行けるはず。KCのツリーデータベースとほとんど同じ書式だけど、IDの幅が8バイトではなく6バイトになったところが違う。8バイトだと10万QPSで挿入し続けて4億年持つ計算になるが、そこまでは要らんよね。それにしても、きちんと設計をまとめると気持ちがいいな。たとえ記憶喪失になってもこれを読み直せば同じ実装ができるはず。
