Here is the question and answer for a B+ database tree insertion, I\'m trying to
ID: 3713473 • Letter: H
Question
Here is the question and answer for a B+ database tree insertion, I'm trying to understand how exactly the number of read/write is established and when they happen...thank you
Root 50 73 85 8 1832 40 1256810 41 45 73 80 91 99 Figure 10.1 Tree for Exercise 10.1 2. Show the B+ tree that would result from inserting a data entry with key 3 into the original tree. How many page reads and page writes does the insertion require? Root 1850 73 85 32 39 13 80 9199* Figure 10.3 2. The data entry with key 3 goes on the first leaf page F. Since F can accommodate at most four data entries (d 2), F splits. The lowest data entry of the new leaf is given up to the ancestor which also splits. The result can be seen in figure 10.3 The insertion will require 5 page writes, 4 page reads and allocation of 2 new pagesExplanation / Answer
It actually requires 3 page reads.
Typically each node is a page. First it will read root node, compares the value 50 (3<50), comes to its predecssor. Reads node |8|18|32|40|, compares with value 8 (3<8), comes to its predecessor. Reads node |1|2|5|6| and compares the values 1,2 and 5 with 3 and inserts 3 after 2. Thats the first write. Since a node can only contain 4 entries, it splits. Introducing new page and writing |5|6| there. After that the lowest data entry of this new page is given to its ancestor, and 5 is written there,which also splits. New page is allocated for |32|40| and these entries are written in that page. Due to split, 18 is given to the ancestor and written in the root node. Below table shows the sequence of reads and writes.
Nodes Read Nodes Written Page Allocation |50| (3<50) |8|18|32|40| (3<8) |1|2|5|6| (leaf node is read) |1|2|3|5|6| (3 written to leaf node and node gets split) 1st Page Allocated |5|6| (wriiten on new page) |5|8|18|32|40| (gets split) 2nd Page Allocated |32|40| (written on new page) |18|50| (written on root node)