B木（B-Tree）の探索：データ構造におけるB木クエリの仕組み

B木（B-Tree）は、データベースやファイルシステムなどで広く利用されている平衡多分木構造です。ここでは、B木における要素の探索方法、いわゆる「B木クエリ」の実行手順について詳しく解説します。

B木の探索例

以下のようなB木を例に考えてみましょう。

B木の例：

B木の探索手法は、二分探索木（Binary Search Tree）と非常によく似ています。例として、上記の木から「66」という値を検索する場合の手順を見てみましょう。

1. まず根（ルート）から探索を開始します。目的の値66は根の要素46よりも大きいため、右側の子ノードへ移動します。
2. 右の子ノードには複数の要素がソートされた状態で格納されており、[56, 81] となっています。目的のキー66は56より大きく81より小さいため、この2つの要素の間に位置する部分木へ進みます。
3. 葉レベルに到達した時点で、目的の要素66が見つかります。

探索アルゴリズム

B木内の要素を検索するためのアルゴリズムは以下の通りです。

BTreeSearch(root, key)

入力： 木のルートノードと、検索対象のキー

出力： キーを持つノードの値。キーが存在しない場合はnullを返す

x := ルートを読み込む
if x がインデックスノードの場合
    if x 内に o->key = 'key' を満たすオブジェクト o が存在すれば、o->val を返す
    'key' が属するキー範囲を持つ x の子ノード x->child[i] を特定する
    return BTreeSearch(x->child[i], key)
else
    if x 内に o->key = 'key' を満たすオブジェクト o が存在すれば、o->val を返す
    else null を返す
    end if
end if

このように、B木の探索では各ノード内のキーと比較しながら適切な子ノードへと降りていくことで、効率的に目的のデータを検索できます。各ノードが多数のキーを持つ多分岐の平衡構造であるため、大規模なデータセットでもディスクアクセス回数や比較回数を抑えられ、少ないステップで探索を完了できるのが大きな特徴です。