B+木

id:yellow_73:20080325 の続き。
B木については、「C言語による最新アルゴリズム事典」にまるまるあったので、とりあえずどうにかなりそうです。
今度はB+木。
WikiPediaにざらっと説明がありました。
http://en.wikipedia.org/wiki/B%2B_tree
あ、英語はよく分かりません:-)
図が示されていますので、それを見るだけで十分かも知れません。
B木は全てのノードに実データが仕込まれていたのですが、B+木は最も低いレベルのノードに実データが仕込まれ、(非リーフの)ノードは、キーだけを持って、検索を助けるようになっています。
リーフは一方向の線形リンクトリストになっています。リーフ内はソートされているし、リーフ間の大小関係も保障されているので、リーフのリストはソートされています。ちょうど直上ノードのキーがクイックソートのピボットみたいになってる。なので、与えられたキー範囲内にある実データ全てを抜き出すのは、その範囲の左端を見つけて、あとは右に右に進んでいけば全部取れそう。