Chapter 14, Problem 8PE

Explanation of Solution

Secondary B⁺-tree:

• Secondary B⁺-tree is constructed on a relation r with n_r tuples.
• The cost of building the tree index when one record is inserted at a time with the given assumptions.
• The cost of insertion is the sum of below costs:
• The cost to locate the page number of the requisite leaf node. In case of insertions this cost may vary as the non-leaf nodes are already in memory.
• The cost to read one random disk access after reaching the leaf level.
• The cost to update is also one random disk access.
• The cost to write one page.
• Not that if a node split occurs due to insertion the cost increases by an extra page write.
• Now, in the worst scenario, each leaf node is just half filled. So, the number of splits is given by 2×(n_r/f).
• So, the total cost is maximum of either of these two values;
  • (2×n_r) random disk access, or
  • (n_r+2×(n_r/f)) page writes.
• Here, the cost of page writes is assumed to be negligible. So, the cost of random disk access is more.
• So, substitute the given values in above in the above formula to get;
  • (2×n_r) random disk access
  • =2×10000000×10×(1/1000)sec
  • =200000sec
  • 55.5hours
• first sort the file in ascending order using the function which is assumed to be available.
• Now, for each pair of value and pointer from the file call the insert-in-leaf function.
• In insert-in-leaf function;
  • Check if the tree is empty, if yes, this is the first root node to be inserted. If it is considered as “L”.
  • Otherwise, since the values are sorted so insertion will occur in the last leaf node. So, transverse the leaf node to get the last leaf node.
  • Check if this node “L” is full or not. If not, insert the given value and pointer pair at the first available location is node “L”.
  • If this node is full, split it. In this case,
    • Create a leaf node and assume it as “L1”.
    • Set the pointer in node “L” to this node “L1”.
    • Initialize “K1” to the last value from nodes chain “L”.
    • Call the insert_in_parent function with desired values to insert this node in the parent...