博士

やっほー、ロボ子！今日はB-Treeについて話すのじゃ！

ロボ子

博士、こんにちは。B-Treeですね！データベースのインデックスでよく使われるやつですね。

博士

そうそう！B-Treeはディスクアクセスに最適化された自己平衡木構造なのじゃ。各ノードが1つのディスクブロックに収まるように設計されてるんだぞ。

ロボ子

なるほど。ノードがディスクブロックに収まるように設計されているんですね。具体的には、どのような構造になっているんですか？

博士

B-Treeはルートノード、内部ノード、リーフノードの3つで構成されるのじゃ。内部ノードは検索をガイドする中間層で、キーとポインタを格納するんだぞ。リーフノードは実際のデータ、つまりキーと値のペアを格納するのじゃ。

ロボ子

キーとポインタですか。B-Treeの重要な特徴として「高ファンアウト」というものがあるそうですが、これはどういう意味ですか？

博士

ファンアウトが高いほど、必要なディスクシークが減ってクエリが高速化するのじゃ！例えば、10億件のレコードの場合、ファンアウトが1000のB-Treeの高さはたったの3になるんだぞ。

ロボ子

高さが3ですか！それはすごいですね。B-Treeのルックアップアルゴリズムはどのように動くんですか？

博士

まずルートノードから開始して、現在のノードで二分探索を行うのじゃ。そして、セパレータキーの範囲を見つけて、対応する子ポインタをたどる。これをリーフノードに到達するまで繰り返すのじゃ。リーフでキーを見つけるか、存在しないと判断したら終わりだぞ。

ロボ子

なるほど。挿入時にノードが一杯になった場合はどうなるんですか？

博士

ノード分割じゃ！ノードの中点を見つけて、新しい兄弟ノードを作成し、キーの半分を新しいノードに移動させるのじゃ。そして、中間のキーを親ノードに昇格させる。親ノードが一杯なら、再帰的に分割するぞ！

ロボ子

削除時はどうでしょう？ノードが空になりすぎると、どうなるんですか？

博士

ノードマージじゃ！右の兄弟ノードからすべてのキーを左の兄弟ノードにコピーして、親ノードからセパレータキーをマージされたノードに降格させるのじゃ。右の兄弟ノードを削除して、親ノードが空になりすぎると、再帰的にマージするぞ。

ロボ子

B-Treeは様々なデータベースで使用されているんですね。MySQL、PostgreSQL、SQLite、MongoDBなどで使われているとのことですが、それぞれページサイズが違うんですね。

博士

そう！MySQL InnoDBでは、プライマリキーインデックスとセカンダリインデックスにB+-Treeを使っていて、ページサイズは16KBなのじゃ。PostgreSQLはデフォルトのインデックスタイプとしてB-Treeを使っていて、ページサイズは8KBだぞ。

ロボ子

SQLiteはテーブルとインデックスの両方にB-Treeを使用し、ページサイズは4KBで設定可能なんですね。MongoDB WiredTigerはインデックスにB-Treeを使用し、内部ページサイズは4KB、リーフページサイズは32KBなんですね。

博士

B-Treeにもトレードオフがあるのじゃ。例えば、書き込み増幅や、非シーケンシャルキーの範囲クエリに弱い点、キャッシュのメモリオーバーヘッドなどがあるぞ。

ロボ子

書き込みが多いワークロードには向かないんですね。LSM-Treeの方が適しているとのことですが、B-Treeが優位な点はどんなところですか？

博士

ディスクI/Oを最小限に抑えることができるのじゃ！高いファンアウトが木の高さを低減させるからな。それに、自動的にバランスを保つし、範囲クエリもサポートするぞ。HDDとSSDの両方に最適化されているのも強みじゃ！

ロボ子

なるほど。B-Treeは奥が深いですね。とても勉強になりました！

博士

ところでロボ子、B-Treeって、まるで私の知識みたいじゃない？最初は小さいけど、どんどん成長して、いろんな情報を整理してくれるのじゃ！

ロボ子

博士、それは少し強引な例えですね…。

博士

えへへ。まあ、B-Treeも私も、これからもどんどん進化していくぞ！