データベースと秋の空・RDBMS掌握術!

第4回 RDBMSマジック、インデックス(2)
~インデックス界の帝王,B-Tree

この記事を読むのに必要な時間:およそ 2 分

二分探索木

二分探索木は以下の図にあるような構造を持ったアルゴリズムです。すべてのノードは,以下のルールに従って格納されています。

  • ノードは,必ず一つの値を持つ
  • ノードは,最大二つの小ノードを持つ。おのおの左右に分かれており,親ノードよりも左側が「小さい」⁠右側が「大きい」値を持ったノードを格納する

二分探索木の例

二分探索木の例
二分探索木の検索

二分探索木における探索は,常に以下のルールによります。

  • 一番頂上のノードから始めます。
  • 検索したい値と,ノードに入っている場合を比較します。
  • 一致した場合は当たりです。
  • 検索したい値がノードの値より大きい場合,右側に移ります。逆に小さい場合は左側に移ります。
  • 一致したものが見つかるまで続けます。

例えば,図において6を検索したい場合,

  • 「8」のノードから始める(①)
  • 「8」は6より大きいので,左側の子ノードに移る(②)
  • 移った先の「4」は6より小さいので,右側の子ノードに移る(③)
  • 移った先の「6」は6と等しいので,当たり!(④)

のようになり,全体が13個あるのに対して,8, 4, 6の3つだけの検索ですむようになります。

二分探索木の検索

二分探索木の検索

さらにポイントとしては,二分探索木は値を順に並べているため,範囲検索も行うことが出来ます。

  • 一番頂上のノードから始めます。
  • 検索したい範囲のノードに入っているかを比較します。
  • 最小値より大きい場合,左側をスキャンします。
  • 範囲内の場合,自分を列挙します。
  • 最大値より小さい場合,右側をスキャンします。

また,この場合,範囲にこだわらずにすべての値を列挙すれば値が順にそろうため,そのままソートとして扱うことも出来ます! 木構造のアルゴリズムは実に便利です。

挿入,更新,削除

検索が簡単で便利な反面,データの更新削除が非常に面倒なのが木構造の欠点です。

データを挿入する場合も削除する場合も,ひとまず検索を行って,実際に格納する場所や削除するエントリがどこになるかを確定します。

挿入の場合は,そのエントリの下に空きがあるはずですので,それを見て挿入します。

挿入

削除の場合には,実際に探し出したあと削除します。末端の場合は特に問題はありません。

削除

もし末端ではなく下にノードがある場合,いずれかのエントリを上位に昇格させる処理が必要になります。

削除して昇格

更新はすなわち挿入と削除です。

著者プロフィール

谷田豊盛(たにだゆたか)

国立明石工業高等専門学校卒。いったん公務員になるが,プログラミングが好きでコンピューター業界に転進。 PostgreSQLを触り出したのは6.3のころから。特にCygwinを使ったWindows環境で使っていたが,それが高じて現在ではPostgreSQLで飯を食うことに。