B+木(B+ Tree)は B木 を変形し、 シーケンシャルアクセスの性能などを改善した多分探索木です。 データベースやファイルシステムを実装する場合、 B木そのものより、このB+木が使われることが多いようです。
このページではB+木の実装を紹介します。 しかし説明の詳細はB木と重複することが多いので省略します。 ですので、このページを読む前に、 必ず B木のページ を理解してください。 まず、具体的にB+木の例を見てみましょう。以下のようになります。
|
|
B+木は探索木として見ると少し不自然な形をしています。 普通の探索木では、目標のキーが見つかればそこで探索を打ち切りますが、 B+木では、目標のキーが見つかった後も、最下層に到達するまで探索を続けます。 例えば、図1.で説明すると、 根(root)の４から左部分木を探索するとすぐ２が見つかります。 ２を探していたのなら、ここで探索を打ち切ればいいわけですが、 B+木の場合、探索を続けて右部分木を探し、 さらにその左部分木を探して最下層の２にたどり着きます。つまり、 キー \(x\) の右部分木の最小値として再びキー \(x\) が現れるという構造をしています。
このため、B+木の最下層には、登録されているキーが全て現れる事になります。 そして、この最下層のキーにのみ値が対応しています。 丸で表したのが値です。また、 矢印で示したリンクが最下層のノード間に張られています。 こういう構造にすると、値をシーケンシャルにアクセスしたい場合、 最下層のノードだけを効率的にアクセスすることができます。
では、B木の挿入処理とB+木の挿入処理を比較して見ましょう。 それぞれのソースコードから挿入の部分を抜き出すと以下のようになります。
顕著な違いは、検索しているキーと一致するキーが見つかった場合の処理です。 B木では一致するキーが見つかると、そこに値を上書きして探索を打ち切るのに対して、 B+木では、一致するキーをスルーして右部分木に対する探索を続行します。
次にノードを分割する split 処理を見て見ましょう。 B+木では内部ノードでの処理と最下層のノードでの処理が微妙に違います。 内部ノードはほぼB木の処理と同じですが、最下層のノード処理が違います。 ここでは、内部ノードでの split と最下層のノードでの split の違いを示します。
最下層のノードでの split の最後の return の部分が特徴的です。
右部分木の最小値を削除せず、そのまま上位の木に送り出しています。
この処理があるため、B+木では、
キー \(x\) の右部分木の最小値として再びキー \(x\) が現れることになります。
最後に、B+木のパフォーマンスについて少し触れておきます。 理由はよくわかりませんが、B+木の検索・挿入・削除のパフォーマンスは、 B木より優れています。シーケンシャルアクセスの改善のみならず、 全体のパフォーマンスの意味でもB+木を使う意義があるようです。
それでは、B+木の実装の全体を示します。以下のようになります。