Slide 15.3: B-tree insertions Slide 15.5: B-tree worst-case search depth Home

B-tree Insertions (Cont.)

---

The figure on the previous slide is repeated on the right one more time. (d)—Inserting keys W and Y causes the third node to split, leaving four leaf nodes. (d) shows the tree after B is inserted.

• (e)—The insertion of the next key, E, will cause the first leaf node to split.


• (f)—The final tree, after inserting U M K, is shown at (f).