B+木：挿入で節が割れて伸びる
次数 m を決めてキーを挿入し、満杯の節が割れて中央キーが親へ昇る様子と、高さ（= ディスク I/O 回数）の変化を体感します。
3
42
次数 m（最大キー = m−1）
—
登録キー数 N
—
木の高さ（= 探索 I/O）
—
これまでの分割回数
—
B+木の構造（赤＝直前に割れた節 ／ 葉は連結リストで横に繋がる）
B+木は、データベースの索引で使われる「平たくて多分岐」な探索木です。1 つの節に最大
キーを挿入していくと、葉がやがて満杯（
木の高さはディスクから索引をたどるI/O 回数そのもの。次数 m を上げると同じキー数でも高さが下がる（= I/O が減る）ことを確かめましょう。
m−1 個のキーを詰め込み、子は最大 m 個に枝分かれします（m を次数と呼びます）。キーを挿入していくと、葉がやがて満杯（
m−1 個）になります。そこへもう 1 つ入れると節は分割され、中央のキーが親へ押し上げられます。この押し上げが根まで伝わると、根が割れて木が 1 段高くなるのです。木の高さはディスクから索引をたどるI/O 回数そのもの。次数 m を上げると同じキー数でも高さが下がる（= I/O が減る）ことを確かめましょう。
いま何が起きている？
ここがポイント
- 満杯の節は割れる ── 節のキーが m−1 個を超えると、中央キーを親へ押し上げて 2 つに分割する。
- 分割は上へ伝播する ── 親も満杯なら親も割れ、根まで届くと根が割れて高さが +1 される（成長は根方向＝上向き）。
- 高さ = I/O 回数 ── 高さ h ≒ logmN。次数 m を上げると同じ N でも木が低くなり、ディスクアクセスが減る。
- BST（2分木）との違い ── 二分探索木は 1 節 1 キー・2 分岐で偏ると高くなる。B+木は多分岐＋必ず根方向に伸びるので常にバランスし、低く保たれる。