B木

R木はいまひとつ分かっていませんので学習しようと試みる。「木」とついているので木構造なのは分かるのですが、そこまで。
まず、Googleさんに聞いてみる。キーワードは「R木」。これだと結構情報が少ない。今度は「R-tree」でやってみると、Wikipediaがヒット。B-Treeに似ているとのこと。
ということで、まずB木を調べることに。二分木と同じ意味だと思っていたことは内緒。
http://ja.wikipedia.org/wiki/B%E6%9C%A8 を見てみます。
ノードはm個の枝と、m-1個のキーを持ちます。ここで「キー」とは、どの枝に行くかの境界を示すもので、データの要素そのものです。m=2のときは二分木ですね。
データ挿入時は、根から葉に向かって、入るべきノードを探索していきます。見つかったらそこのキーに入れるのですが、キーがいっぱいになっている場合には「分割」を行います。キー列(新たに入るべきキーも含む)の中央値となるキーを抜き出して親ノードに入れて、残ったキー列を中央値と比べて小さい方と大きい方とに分割して、二つを親ノードの子として入れなおすというものです。いっぱいになった際に、そのノードの子に追加するのでなく、親に影響を与えるのがポイントですね、たぶん。