RDBMSで使われるB木を学ぼう （2/3）－ ＠IT

それでは、B木への要素の追加について、より細かく見ていくことにします。 まず、追加する値が与えられた場合、節点が葉である場合とそうでない場合で処理が異なります。その節点が葉であるかどうかは、子の節点を保持しているかどうかで判断ができます。節点が葉の場合には、ここにはすべてnilがはいっていますし、一番左から埋めていくところなので、一番左のポインタをチェックすればよいことになります。 葉のバケットにキーを追加する場合、バケットに空きがあればキーの大小関係を壊さないようにして新しいキーを追加します。 バケットがいっぱいであればバケットの分割が発生します。K次のB木には2×K個のキーがバケットに入っていて、そこにキーを1つ追加するわけですから、キーをソートしておいた場合には、0から数えてK個目のキーが中央値となります。 まず、この中央値を親の節点に返します。また、新しいバケットを生成して、そこへ

[horristic]

B-Tree