【ITニュース解説】A B+ tree node underflows: merge or borrow?

データベースなどでデータを効率的に管理するために重要な「B+ツリー」というデータ構造がある。これは、大量のデータを高速に検索、挿入、削除することを可能にする仕組みだ。B+ツリーは、データを格納する「ノード」と呼ばれるブロックが木のような階層構造をなしており、データの索引として機能する。すべての実際のデータは木の末端にある「葉ノード」に格納され、これらの葉ノードは互いに連結されているため、範囲検索などもしやすい特徴を持つ。一方、葉ノード以外の「内部ノード」は、データの検索パスを示すための「キー」と、次のノードを指し示す「ポインタ」のみを保持している。

各ノードには、格納できるキーとポインタの数に上限と下限が設定されている。ノードの容量が適切に保たれることで、B+ツリーは常に効率的な状態を維持できる。しかし、データがノードから削除されると、そのノードに格納されている要素の数が減少する。その結果、ノード内の要素数が規定の下限を下回ってしまう場合があり、これを「アンダーフロー」と呼ぶ。アンダーフローが発生したノードは、その役割に対して容量が小さすぎる状態であり、ツリー全体のバランスと効率を損なう可能性がある。アンダーフローが頻繁に起こると、ツリーのノード数が不必要に増えたり、検索パスが長くなったりして、データベースのパフォーマンス低下につながる。

このアンダーフロー状態を解決し、ツリーの効率性を保つために、「マージ（結合）」と「ボロー（借りる）」という二つの主要な対処法が存在する。

マージは、アンダーフローしたノードが隣接する兄弟ノードと、親ノードから受け取ったキーと共に結合し、一つのノードとする手法だ。例えば、二つの隣り合ったノードがそれぞれ容量の下限を下回っていた場合、これらを結合して一つのノードにすることで、規定の容量要件を満たし、ツリー内のノード数を減らすことができる。この操作の大きなメリットは、ツリー全体の高さを減らせる可能性がある点だ。ツリーの高さが低くなると、データの検索に必要なノードの読み込み回数（ディスクI/O）が減り、結果として検索速度が向上する。また、ノードが結合されることで、物理的なストレージ利用効率が高まることもある。しかし、マージは複数のノードに影響を与える比較的複雑な操作であり、特に頻繁に発生すると、その後のデータ挿入時に再びノードの分割が頻繁に発生し、オーバーヘッドが増える可能性もある。

一方、ボローは、アンダーフローしたノードが、その隣接する兄弟ノードからキーとポインタの一部を「借りる」ことで、自身の要素数を下限以上に回復させる手法だ。この場合、ノードの結合は行われず、アンダーフローしたノードと兄弟ノードはそれぞれ独立したノードとして残る。ボローのメリットは、操作がマージよりもシンプルで局所的である点だ。ツリーの構造を大きく変更することなく、問題のあるノードだけを修復できるため、比較的低コストで実行できる。ツリーの高さは変わらず、ノードの分割や結合といった大規模な操作を回避できるため、特にデータの削除と挿入が頻繁に繰り返される環境では、ツリー全体の安定性を保ちやすい。しかし、ボローはツリーの高さを最適化する効果はなく、根本的なノード数の削減には寄与しない。また、頻繁にデータを借りることになると、ツリーのバランスが偏る可能性もゼロではない。

マージとボロー、どちらの手法を選択するかは、システム全体の要件やデータの特性に大きく依存する。一般的に、データが削除される傾向が強く、ツリー全体のノード数を減らして高さを最適化したい場合は、マージがより効果的であると考えられる。これにより、検索性能の向上が期待できる。逆に、データの削除と挿入が頻繁に発生し、ツリーの構造を安定させつつ、局所的な修正でパフォーマンスを維持したい場合は、ボローの方が適している場合が多い。ボローは操作が軽いため、リアルタイム性の高いシステムでのオーバーヘッドを抑えられる可能性がある。

データベースシステムによっては、これらの二つの手法を状況に応じて使い分けたり、閾値を設けて自動的に判断させたりすることもある。例えば、隣接ノードから少量のデータしか借りられない場合はマージを検討し、十分なデータを借りられる場合はボローを選択するといった実装も考えられる。どちらの手法を選ぶにしても、実装の複雑さ、実行時の性能オーバーヘッド、そしてツリー全体の安定性とバランスを考慮し、システムにとって最適な選択をすることが求められる。システムエンジニアは、これらの内部動作を理解し、効率的なデータ管理が可能なシステム設計を目指す必要がある。