B-tree Insert

• This is a B-Tree with degree t=2
  • What is the minimum keys?
  • What is the maximum keys?
  • When is a node split?
• Insert the following values into the tree, one at a time: 43, 7, 13
• Redraw the tree after each insertion.

Start

Insert 43

Try to insert 7 but 5 | 10 | 15 is Full with 2t-1 keys

Split moving median 10 up to parent

Insert 7

Try to insert 13 with 15 but must split any full nodes (2t-1 keys) encountered.

Split 10 | 25 | 40 into nodes of t-1 keys

Insert 13