Course : Datenbanken II Department: Master of Computer Engineering Technische Universitt Clausthal Read this before starting with the tasks!!

The usage of the wrong definition leads to not getting points! (also if the steps are right, you dont get points, when using other definitions!) See the below example on how to split leaf-nodes in the B⁺-tree.

Please read the following, to be sure to do it right and have every mandatory information in your structure.

When you create a B⁺-tree, you can make it simple, as you do not need to make extra room inside the nodes for the node-pointers. (But of course you need to draw the pointers!!) Meaning a simple structure like in the picture below is sufficient for displaying your solution. It includes, the nodes, keys and EVERY pointer (except data-pointers)!

The basic difference in the definitions is about the splitting of nodes. Therefore the example below shows, how the splits are done for an even or odd number of indexes in a leaf node. If you find online-courses or tutorials, be careful, because they might use other definitions, which result in other solutions!

For this assignment the definitions of the Reading Database Indexing will apply. The picture below shows, how you make a split for odd and even number of elements per node. On the left we can insert up to 3 elements in a single node, so that we have to split when inserting the 4th. Since we dont have a middle element, we always chose the left one of the 2 in the middle. The resulting tree is displayed in the picture. Please note, that all pointers (except the datapointers) are included in the drawing. For internal pointers the starting point is very important and located at the lower corners of the rectangle, which holds the element!

The right tree shows how to split for an even number of elements in a tree. After inserting the third, you split them with 2 elements to the left node and 1 to the right node! Of course the middle element goes up.

Figure 1: Examples on how to split for the order of 4, when inserting the numbers 1, 2, 3, 4 (left) and the order of 3, when inserting the numbers 1, 2, 3 (right)

For more information read the Reading Database Indexing in Moodle, there is also an example on how to insert and delete elements in a B⁺-tree.

Task1 5 Marks

It is December again and Santa Claus prepares for his yearly journey. In the last year he wanted to store all the people he has to visit with linear hashing, which did not work out as good as he thought. This year he will try another attempt on storing all the names in an index structure again. He thinks, that a B⁺-tree is perfect for storing the information he needs to save. He already converted the names to numbers and asks you to store all the values in an empty B⁺-tree.

Before he goes to manage his elves he gives you the following information: The B⁺-tree should have the order of 3 and there are no elements stored so far. He states, that he wants to use the definitions on page 2 of this assignment and urges you to keep in mind, that you will end up on the naughty list, if you forget to draw just one pointer!

(a) Build a B⁺-tree starting with an empty tree. Insert the following sequence of ele- ments into the tree:

10, 13, 14, 12, 11, 9, 15

Show your tree after each insertion!

(b) After you inserted the indexes you recognize Santa running towards you. He says that 4 of the indexes are actually wrong and you have to delete them in the following order

9, 14, 11, 12

Show your tree after each deletion!

(c) You deleted the indexes and see Santa coming to your office again. He apologizes and states, that the first list was actually correct but he held the paper upside down. You think about it and know what to do: Consider the sequence from (a) and reverse the order! Insert the new sequence into an empty B⁺-tree starting with 15.

Show your tree after the last insertion