【びーつりー】
B木 とは？
最終更新:
💡 複数のキーで、探す範囲を絞る
一つの節に複数のキーを持つ、平衡の取れた探索木。値の範囲で枝を選ぶ仕組みと、データベースの索引との関係を解説します。
📌 このページのポイント
- 一つの節に複数のキーを持つ多分岐の探索木
- キーの順序と範囲から、次に探す枝を選ぶ
- 追加や削除でも、平衡を保つように構造を調整する
- 索引の性能はデータ量・実装・検索条件などで変わる
ひよこ B木って、データベースの木なの？
ひよこ 図の20と40は、何を表している？
ペンギン先生 探す値と比べるキーだよ。この例では、20より小さい値、20と40の間の値、40より大きい値を、それぞれ別の子の節で探す。20や40自体もキーとして木の中にあるよ。
ひよこ 枝が何本もあるのが特徴なんだね。
ペンギン先生 そう。二つの枝だけを持つ木と違い、多数の子を持てるんだ。平衡を保ち、深くなり過ぎないようにすることで、探すときに通る段数を抑えやすいよ。
ひよこ 追加したら、形が崩れない？
ペンギン先生 節に収まらなくなると分割するなど、構造を調整するよ。削除でも必要に応じて調整し、木の平衡を保つ。図は探索の例で、追加や削除の途中は省略しているんだ。
ひよこ データベースなら、必ずB木で高速に探せる？
ペンギン先生 索引にはほかの種類もあるよ。PostgreSQLのB-tree索引は、等しい値や範囲の検索などに対応する。ただし索引を使うかや実際の速さは条件次第。何件でも必ず3回で読める、といった保証ではないんだ。
もっと詳しく知りたい人へ
B木とB+木は同じ？
関連するデータ構造ですが、同一ではありません。B+木では、検索対象の項目を葉に集め、内部の節を探索の案内に使う構成を取ります。データベースで「B-tree」と呼ぶ索引の具体的な配置は、各実装の説明も確認します。
段数が少なければ、ディスクを読む回数も必ず同じ？
段数と実際の入出力回数は分けて考えます。既にメモリーにあるページ、索引をたどった後に読む表のデータ、検索する件数などで変わります。段数だけから固定の処理時間や入出力回数は決まりません。
まとめ：ざっくりこれだけ覚えればOK！
「B木」って出てきたら「複数のキーで範囲を絞って探す、平衡の取れた木構造」と思えばだいたいOK！
📖 おまけ：英語の意味
「B-tree」 ＝ 多分岐の平衡探索木の名称
💬 日本語ではB木と呼びます。BをBalancedなど一つの語の略だと断定せず、データ構造の名称として覚えるとよいでしょう。