B+Tree

先日のLinear Hash同様、今年の技術士二次試験はB+Treeに関しても出題がありました。
結構良い問題ですよね．．．


先日は、Linear Hashを調べるので結構時間が掛かってしまったので、今日はB+Tree。


B-Treeに関しては、「情報処理試験 ソフトウェア開発技術者完全攻略〈2004年版〉」を参考にさせていただきました。（ところで、この本、結構重宝しています。なんで改定版が出ないのでしょうか．．．）



B+Tree（B+-Treeと書く場合もある）はB-Treeの改良型です。
B-Treeとの大きな違いは、Data自体をNodeに格納せずLeafに全て格納することです。NodeはKeyとPointerのみを持つので、B-Treeと比較するとNode当たりのKeyを大く取れます。この考え方はもとはISMA（http://ja.wikipedia.org/wiki/Indexed_Sequential_Access_Method）から来たもので、B-TreeとISMAを組み合わせた考え方がB+Treeともいえます。
また、B+TreeはLeaf間にPointerを持っており、比較演算子の処理等もB-Treeと比較して容易ともいえるかと思います。
Keyの追加・削除やNodeの分離といった処理は、基本的にB-Treeと同じですので、こちらを参考にして下さい。→（http://www.atmarkit.co.jp/flinux/rensai/fs02/fs02c.html）