ICDロゴ

Bツリー (Balanced tree)

【ビー・ツリー】

最終更新日: 2001/07/14

 データを順序付けて格納するために使われる、コンピュータ・アルゴリズムの1つ。与えられたデータをそのキー(インデックス、索引)の順番に並べ替えて格納したり、与えられたキーに基づいてデータを取り出したりする場合に使われるアルゴリズムであり、リレーショナル・データベース・システムの索引付けや、ファイル・システムにおけるファイル名の管理などで一般的に使われている。

 Bツリーでは、各キーとそれに対応するデータをペアにして、昇順になるように並べ、それを「ノード」と呼ばれる固定的なサイズの領域に格納する。ノードには、キーとデータの組か、他のノードへのリンクが(昇順に)格納できる。各ノードはツリー状に接続され、ルートから末端の各ノード(リーフ・ノード)までの距離(ツリーの高さ)がバランスするように管理されることから、Bツリーと呼ばれる。

 エントリを追加する場合は、追加するキーの値をノード内のキーの値と比較し、適切な位置に挿入する。各ノードのサイズは固定なので、エントリの総数に関係なく一定のコストですむ。もしノードがすでにいっぱいで追加する余地がない場合は、新しいノードを用意して現在のノードのデータを分割して格納し、上位ノードからのリンクを修正する。

 エントリの検索は、ルート・ノードから再帰的に、目的とするキーがどの子ノードに含まれるかを検索する。検索するノードの数は最大でもツリーの高さ分しかないので、どのキーでもほぼ同じコストで検索できるのがこのBツリーの特徴である。

 Bツリーを改良したものとして、B+ツリーがある。

Copyright (C) 2000-2007 Digital Advantage Corp.

関連用語

アイティメディアの提供サービス

キャリアアップ