B+Tree - MOXBOX #BTree

概要 B-Tree の派生型である B+Tree は、個々のキーの検索効率を下げる代わりに、ある範囲のデータをまとめて取得するケースに適した構造を持つ。B-Tree が中間ノードにもデータエントリを保持していたのに対して、B+Tree では末端の葉にのみエントリを保持し、葉は相互にリンクしたリストの構造を持っている。 このようなソートされたリンクリスト構造を併せ持つことで B+Tree ではキーの範囲条件 \(x_0 \leq k \lt x_1\) に一致するデータを効率的に取得することができる (B-Tree では何度も中間ノードに上る必要があった)。 中間ノード及び葉のそれぞれに格納可能な最大エントリ数を \(M \geq 2\)、最小エントリ数を \(1 \leq t \leq \lfloor \frac{M}{2} \rfloor\) とする (以下の説明図では \(M=4\)、