前回の続き
B-Tree
中間ノード, リーフノードで構成されている。
リーフノードがTreeの末端であり、Key に応じたValue を持つ集合である
中間ノードは複数のKeyと複数の子ノードへのポインタを持つ
子ノードへのポインタの数はKeyより1つ多い。これは最小のKeyより1つ前の子ノードへのポインタを持つからである。
中間ノード・リーフノードは自身が持つKeyでソートされている これは必ず担保されていて、検索時にソート済みのデータセットに対して2分探索を行うためである
書き込みは、リーフノードの検索から始まる 該当ノードの容量に余裕があればそのまま書き込みして終了 そうでない場合は、ノードの分割を行う
ノードAが以下のKey を持つとする
- 10
- 15
- 18
そして、16が挿入されるときは新しいノードBを作り、データの半分を送る。ノードBはこのようになる。
- 10
- 15
そして、ノードAの容量に空きができたので、ノードAに値を書き込む
- 16
- 18
そして、中間ノード側にノードBのポインタと、新しい分割Keyである 16 の値を送る。
中間ノードが溢れてしまった場合は、中間ノードも同様の処理を行う。
memcomparable-format
複合キーをつくるときにソート可能な方法でエンコードする手法
a, b のキーをエンコードして得られる値はソート順が保たれるということらしい
データの表現
上記のフォーマットで8バイト+1バイトでデータのつながりを表現していくのはなるほどなぁという感じだった。
[02, 00, 00, 00, 00, 00, 00, 00, 01]
の場合、9バイト目の 01 がそれより前の8バイトのデータをどう読むか決めている。
上記は 01 なので1バイト目のみ読み出せばよい。
データが8バイト以上のときどうなってるかというと、9バイト目のフラグが 09 になる。
Eveeeeeee は↓のようになる
[45, 76, 65, 65, 65, 65, 65, 65, 09, 65, 00, 00, 00, 00, 00, 00, 00, 01]
セカンダリインデックス
対象の値を Key にもち、Value をプライマリキー(PK)に対応させる。
こうすることで、Key に対する Value の PK を探すことで検索の高速化をしている
セカンダリインデックスがユニークでないときは、PKの値と連結したものを B-Tree の Key にする