The split as described in the lecture always moves up the smallest value in the right node, so the result should be

  [4| | ]

[1|3| ] [5| | ]

Mathematically the median of an even-numbered list (e.g. 1,3,4,5) is the average of the two middle values (i.e. 3.5), which may not always be a valid value (e.g. the median of 'a' and 'b' is not a character), so you need to either round up or round down. In our implementation we always round up.

I shouldn't have said "round up" or "round down" as it implies integer values but in practice an integer value may not be a valid key. The correct way to put it is that we can move up either the largest value in the left node or the smallest value in the right node, and we always pick the smallest value in the right node. So in your first example we move up 26 instead 16.

You are also right in the 2nd part where the correct result should be

  [4| | ]

[1|3| ] [4|5| ]

I didn't notice "split a leaf" in the original question. Sorry about that.

What if you have the following (made up) B-Tree:

                                                      [10|__|__]

           [5|__|__]                                                                        [20|30|50]               

[1|__|__] -> [6|__|__]                          [11|12|13] -> [21|23|25]  -> [31|35|38] -> [52|54|56]

We want to insert 12:

                                                                                     [10|30|__]

           [5|__|__]                                                           [16|20|__]                                                                               [30|50|__]               

[1|__|__] -> [6|__|__]                          [12|14|__] -> [16|18|__] -> [21|23|25]                              [__|__|__] -> [31|35|38] -> [52|54|56]

Is this the correct outcome?  Notice how [30|50|__]  in level 2 will never get a number less than 30.  I ran into the same issue in Q6.  BTW, this is my last questions for B-Trees.  I just want to make sure I understand every situation since this came up in the Sample Final.

intregrisist wrote:

What if you have the following (made up) B-Tree:

                                                      [10|__|__]

           [5|__|__]                                                                        [20|30|50]               

[1|__|__] -> [6|__|__]                          [11|12|13] -> [21|23|25]  -> [31|35|38] -> [52|54|56]

 

We want to insert 12:

  ...

In your example, 12 is already in the tree. Handling duplicate keys in B-tree requires additional mechanism (e.g. overflow leaf blocks). You don't need to worry about duplicate keys in the exam.

intregrisist wrote:

Sorry, I didn't realize there was a 12.  What I wanted to point out is the situation with the children of [30|50|__] :

EX: (instead of 12 its 15) same B-Tree as my last post:

After we insert 15, we get:

                                                                                      [10|30|__]

           [5|__|__]                                                            [13|20|__]                                                                            [30|50|__]               

[1|__|__] -> [6|__|__]                          [11|12|__] -> [13|15|__] -> [21|23|25]                           [__|__|__] -> [31|35|38] -> [52|54|56]

 

Is this normal or correct?

It's incorrect.

• The 3rd node in the 2nd level should be [50] instead of [30|50].
• There shouldn't be an empty node at the leaf level (3rd from the right).
• Although unrelated to this insert, the two leaf nodes on the left (i.e. [1] and [6]) are incorrect too because you shouldn't have two sibling nodes each having only one key.

Why there's 5,10,30,50 in the non-leaf nodes in intregrisist's question?

All the keys should appear in the leafs, no?

cdecesa wrote:

Dr. Sun,

I am still having some trouble with the B-Tree in question 6 of the sample final. I have tried several times but am struggling to find the correct solution. Can you please walk us through the steps for inserting 115 into this B-Tree (assuming we have already performed the insert operations for 180,139,176)?

I don't give out answers to the sample exams. Feel free to discuss among yourselves though.

HuanXue wrote:

I think it's like this after insert the 115:

[100|120|  ]

[110|  |  ]                                                                       [150|179|  ]

[100|101|  ]     [110|115|  ]                                        [120|130|139]

 

I ignored the not related part.

According to Sun: "...we always pick the smallest value in the right node."  In this case you used the largest of the left node. Also, do we not keep the 120 in lvl 2?

I'm sorry. I mean "110 is the smallest value in the right node".

I think no.

In the root case, that should be the smallest value of the leafs in the part which this key points to.

If you don't understand my poor English... you can see the lecture ppt "index.ppt", page 14.  After the insert, 160 should be the key of the right part.

HuanXue wrote:

I think no.

In the root case, that should be the smallest value of the leafs in the part which this key points to.

If you don't understand my poor English... you can see the lecture ppt "index.ppt", page 14.  After the insert, 160 should be the key of the right part.

It does get the smallest value in the right node BUT it doesn't keep that value.  This would solve the issue I was having.

HuanXue wrote:

Well... I still think I'm following the B-tree insert rules which we studied on the class.

Ah, I see.  He does mention its a B+ Tree in slide 7.  That's why the algorithm is going off a B+ Tree properties even though it says B-Tree later on.