データベースの内部構造の話として、B木とB+木について説明を行う。
B木
B木は、位数Nの場合、2N個のデータ部(di)と、 2N+1個の次のノードへのポインタ(pj)で、 １ノードが構成される。 i番目のポインタpiの先には、di-1より大きく、 diより小さいデータを格納する。 また、１つのノード内のデータ件数は、N以上、2N以下を満たすように構成する。
データの挿入などを行うことで、1ノード内のデータ件数が2N個を越える場合、 追加データを含めた2N+1個の中央の値を上位に昇格させ、ノードを2つに分割する。 昇格先の上ノードもあふれる場合は、再帰的に同じ処理を繰り返す。
データあふれで昇格&分割の説明(wikipediaより引用)
同様に、データ削除の場合も、1ノード内データ件数がNを下回る場合も、 2つのノードを併合などの処理を行う。
B+木
B木では、追加削除が容易ではあるが、全データの順次処理をする場合、 再帰処理などが必要になったりするため、データのシーケンシャルアクセス・ランダムアクセスが 苦手である。データベースでは、複数テーブルの全データで直積といった処理も多いことから、 次々と処理を行うためのヒントが必要となる。
このため、末端のノードにおいて、シーケンスセットと呼ばれるリスト構造を作っておく。 末端のデータをリストでつないだ情報を持つことで、データ順の順次アクセスが容易となる。
参考教科書では、シーケンスセットをノードとは別に保存する説明で記載されているが、 WikipediaのB+木の説明では、末端ノード同士を横方向に接続するだけの図で説明されている。 この辺は、実装方法の異差かな???