B木とB+木の違い
2016年11月12日
情報処理技術者試験の勉強をしていたら「B+木インデックス」というのが出てきていて、調べていたところ「B木」との違いがよくわからなかったので、メモ。
そもそもB木とは
自分的な解釈。
基本的に、データの検索性を高めるための多分木の木構造でのデータ格納方法。
リスト型のデータからデータへとつながっていて、データの頭と末尾にそれぞれポインタがある。(わかりにくい)
B木とB+木の違いとは
B+木にはB木と違い以下のような要素があるようです。
・データ格納先のアドレスを末端の葉(リーフ)のみに格納する
・リーフ(葉)とリーフ(葉)を結ぶポインタを設ける
↑B+木の図
逆に言うと、通常のB木はノード(節点)にもデータが格納され、葉と葉と結ぶポインタはないということですね。