B-Treeを図示するときの細かいテクニック

これは 自作DBMS Advent Calendar 2020 - Adventar の12日目の記事です。
自作 DBMS ネタというか、課題で B-Tree を書かされてる学生向けって気もしますが、いずれにせよ誰かの役に立つと信じて。

Disk-Oriented な DBMS で欠かせないデータ構造といえば B-Tree です。 で、そのデータ構造をちゃんと把握するには図示が有効なわけですが、これがまた大変というか、理解のために書いてるのに理解してないからうまく書けなくて余計混乱するという悪循環に陥りがちなわけです。

というわけでこの記事では B-Tree を図示するときの細かいテクニックをご紹介します。 (ボケーっとしながら書いたら真の B-Tree と B+Tree が混ざってしまった。適当に脳内で補完して読んでください)

ノードはキーと値(ポインタ)の2階建てにする

素朴に実装する場合、キーと値のペアの構造体を配列で持ったものをノードすると思います。
Rust で書くとこんな感じ。

struct Pair {
    key: K,
    value: V,
}

struct Node {
    pairs: Vec<Pair>,
}

こうすると、メモリ上では キー, 値, キー, 値, … という風にキーと値が交互に並ぶわけですが、これをそのまま図にするのはおすすめできません。
眺めているうちにどれがキーでどれが値だかわからなくなるからです。

そこで、キーと値を分けて2階建にします。こんな感じ。

2階建てにする

左上の斜線が入っている部分は使わないキーのフィールドです。 B-Tree のノードでは必ず値の個数がキーの個数より1個多くなりますから、素朴にペアを交互に並べた場合は必ずどこかに余りが出ます。
この使わない余りを右端にするか左端にするか悩むところですが、おすすめは左端です。
その理由については、図示のテクニックというより実装のテクニックなので今回は省略します。またの機会に。 (2分探索でもさらにもう一本書けるんじゃないか)

一番左の矢印は子ノードの右上に、それ以外は左上に

先程の図で、値のフィールドにキーとの不等式(?)が書いてあったのに気が付いたでしょうか。 キーの直下のポインタの先にあるノードのキーはいずれもそのキー以上であり、キーの左下のポインタの先にあるノードのキーはいずれもそのキー未満である、という意味です。 この関係を矢印に反映させることで混乱を減らせます(主観)。

キーの大小関係を意識して矢印を引く

ルートノードの一番左のポインタ、つまり未使用キーの下から伸びる矢印は一番左のノードの右上を指すようにします。 「一番左のノードには5未満のキーしかない」ことをわかりやすくするためです。
もちろん、メモリ上のアドレス的には左のノードの先頭のキーのあたりを指しているんですが、この場合そっちに忠実になるよりはキーの大小関係に着目したほうがわかりやすいと思います(個人差があります)。

それ以外の矢印については ノードの左上を指しましょう。こちらも決してノードの真上とかを指さないように。

このようにすると、木が B-Tree の要件を満しているかどうかを素早く判断できるようになります。
矢印の向きがそのままキーの大小関係になっているため、左向きの矢印の先でキーが大きくなっていないか、右向きの矢印の先でキーが小さくなっていないかを確認するだけで済みます。簡単ですね。

まとめ

というわけで今回は超小ネタを紹介しました。
もちろん図示の仕方はこれだけが正解ではありません。ぜひ自分にあった作図の方法を探ってみてください。

今回紹介できなかったノードの構造のパターンや2分探索のパターンなどはまた後日気が向いたときに記事にします。アドベントカレンダーにはまだたくさんの空欄がありますからね！

ではまた。