8. Assume university database is designed in a way that the value of student ID

Question

8. Assume university database is designed in a way that the value of student ID number only increases meaning that student IDs never reused even after graduation of students. Meaning that for a new student we always assign a student ID number that has not been used before. Moreover we do not delete the student records after their graduation. Now you want to index the student file on this key (student ID) using a B+ tree: (a) Discuss how these conditions affect the performance of created B+ tree index. (b) Suggest a new B+ tree insertion algorithm to improve the performance.

Explanation / Answer

# B+ tree insetion algorithm To insert the new record (student ID) ,first search the traversad path on the key(ID) already exists. Where the new record is to be indexed when the leaf node L that is reached. If L is not full then an index entry of the new node is created that which includes the search key value (student ID) of the new row and a reference to where new row is in the data file. If L is full, then a new leaf node Lnew is added to the B+-tree as a right sibling of L. The keys and index entry of L for the new record are distributed evenly betwen L and Lnew. Lnew is inserted in the linked list of leaf nodes just to the right of L. We must now link new node Lnew to the tree and since Lnew is to be a sibling of L, it will then be pointed to by the parent of L. The smallest key value of Lnew is copied and inserted into the parent of L -- which will also be the parent of Lnew. This entire step is known as commonly referred to as a split of a leaf node. If the parent P of L is full, then it is split in turn. However, this split of an internal node is a bit different. The search key values of P and the new inserted key must still be distributed evenly among P and the new page introduced as a sibling of P. In this split, however, the middle key is moved to the node above -- note, that unlike splitting a leaf node where the middle key is copied and inserted into the parent, when you split an internal node the middle key is removed from the node being split and inserted into the parent node. This splitting of nodes may continue upwards on the tree. When a key is added to a full root, then the root splits into two and the middle key is promoted to become the new root. This is the only way for a B+-tree to increase in height -- when split cascades the entire height of the tree from the leaf to the root.

Related Questions

Navigate

• Browse (All)
• Browse 8
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.