【図解】B+木（B+ Tree）の探索・クエリ処理をわかりやすく解説

B+木の探索（クエリ）とは

本記事では、B+木（B+ Tree）における要素の検索方法について詳しく解説します。B+木の探索は「B+木クエリ」とも呼ばれ、基本的な流れはB木（B-Tree）のクエリ処理と非常によく似ています。ただし、B+木にはB木にはない重要な特徴があり、それは範囲クエリ（レンジクエリ）をサポートしている点です。

まず、次のようなB+木を例として考えてみましょう。

B+木の例：

単一キーの検索手順

B+木の探索は、二分探索木の考え方に近いものです。上記の木から「63」を検索するケースを例に、手順を説明します。

1. 探索は根（ルート）ノードから開始します。「63」はルートの要素「60」より大きく「75」より小さいため、「60」の右側の子ノードへ移動します。
2. 右側の子ノードにも「63」が存在しますが、ここがB木との大きな違いです。このノードは内部ノードであり、実際のデータは格納されていません（B木であれば、この時点で検索が完了します）。
3. さらに下位へ進み、葉（リーフ）レベルに到達して初めて「63」というレコードが見つかります。これが実際の検索結果となります。

範囲クエリをサポートする理由

たとえば「63から78までのすべての要素」を取得したい場合を考えてみましょう。B+木では、各要素ごとに探索をやり直す必要はありません。まず最初の値（63）が属する葉ノードを特定し、その後は葉ノード同士が連結リストのようにつながっているという構造を利用して、78に達するまで順番にノードをたどるだけで済みます。

この仕組みにより、B+木は大量データの中から特定の範囲のデータを非常に効率的に取り出せるため、データベースのインデックスなどで広く採用されています。

探索アルゴリズム

続いて、B+木内の要素を検索するアルゴリズムを確認しましょう。

BPlusTreeSearch(root, key)：

• 入力： 木の根ノードと、検索対象のキー
• 出力： キーを持つノードの値。存在しない場合は null を返す

現在のノードのレコードに対して二分探索を実行する
'key' を持つレコードが見つかった場合：
    該当するレコードを返す
そうでなく、現在のノードが葉ノードでありキーが見つからない場合：
    null を返す