データベースの内部構造の説明を行う。

最初に、元概念となる2分木の説明を交え、O(log N)にて検索できる利点を説明し、 そのN分木のようなものということで、4年情報構造論での"B木"の説明を行う。

しかし、2分木ではデータ追加の際に、末端にデータが次々と追加され、 追加順番によっては、左右の木の段数が不均衡となった木が生成される可能性がある。

B木は、この問題に対応し、位数(d)の場合、１つの節は2d個のデータ保存場所と、 2d+1個の次の節へのポインタで構成する。 データを収納する場合には、d個以上2d個以内を収納する。 さらに、データを追加してオーバーフローが起こった場合、 中央値のデータを上部ノードに移行し、節を２つに分割する方法をとる。 中央値で分割するため、不均衡が発生しづらい点が特徴。

Wikipedia B木より引用。

B+木

B木では、節が下に行くにつれ分割される。このため、全データに対する逐次処理 を行う場合には、再帰呼び出しが必須となる。しかしながら、再帰は処理も大変であり、 これらを簡単にするためにB+木が使われる。

B+木は、末端の節の先に逐次処理のための線形リストを設け、末端の節を横断できる ようにリストでつないでおく。

Wikipedia B+木より引用。