ホーム » スタッフ » 斉藤徹 » B木とB+木

2010年1月
« 12月   2月 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

最近の投稿(電子情報)

アーカイブ

カテゴリー

B木とB+木

データベースの内部構造の話として、B木B+木について説明を行う。

B木

B木は、位数Nの場合、2N個のデータ部(di)と、 2N+1個の次のノードへのポインタ(pj)で、 1ノードが構成される。 i番目のポインタpiの先には、di-1より大きく、 diより小さいデータを格納する。 また、1つのノード内のデータ件数は、N以上、2N以下を満たすように構成する。

データの挿入などを行うことで、1ノード内のデータ件数が2N個を越える場合、 追加データを含めた2N+1個の中央の値を上位に昇格させ、ノードを2つに分割する。 昇格先の上ノードもあふれる場合は、再帰的に同じ処理を繰り返す。


データあふれで昇格&分割の説明(wikipediaより引用)

同様に、データ削除の場合も、1ノード内データ件数がNを下回る場合も、 2つのノードを併合などの処理を行う。

B+木

B木では、追加削除が容易ではあるが、全データの順次処理をする場合、 再帰処理などが必要になったりするため、データのシーケンシャルアクセス・ランダムアクセスが 苦手である。データベースでは、複数テーブルの全データで直積といった処理も多いことから、 次々と処理を行うためのヒントが必要となる。

このため、末端のノードにおいて、シーケンスセットと呼ばれるリスト構造を作っておく。 末端のデータをリストでつないだ情報を持つことで、データ順の順次アクセスが容易となる。

参考教科書では、シーケンスセットをノードとは別に保存する説明で記載されているが、 WikipediaのB+木の説明では、末端ノード同士を横方向に接続するだけの図で説明されている。 この辺は、実装方法の異差かな???