Tweet

Bツリー （Balanced tree）

【ビー・ツリー】

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

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

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

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

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

Copyright (C) 2000-2007 Digital Advantage Corp.