Version 1.0 - initial version


Due Date - 11:59pm Sunday, April 1st
Late Period Ends - 11:59pm Tuesday, April 3rd


Homework Assignment 4

  1. Consider the B+ tree index shown below. Each intermediate node can hold up to five pointers and four key values. Each leaf can hold up to four records, and leaf nodes are linked as usual, although these links are not shown in the figure. Answer the following questions.

    1. Name all the tree nodes that must be fetched to answer the following query: “Get all records with search key larger than 88.”
    2. Show the B+ tree that would result from inserting a record with search key 109 into the tree.
    3. Show the B+ tree that would result from deleting the record with search key 81 from the original tree.
    4. Name a search key value such that inserting it into the (original) tree would cause an increase in the height of the tree.

  2. Suppose that all search key values are integers, and that a leaf page can contain four data entries. Give examples of each of the following:
    1. A B+ tree whose number of levels changes from 2 to 3 when the value 22 is inserted. Show your structure before and after the insertion.
    2. A B+ tree in which the deletion of the value 22 leads to a redistribution. Show your structure before and after the deletion.
    3. A B+ tree in which the deletion of the value 22 causes a merge of two nodes but without altering the height of the tree. Show your structure before and after the deletion.

  3. Assume that you have just built a dense B+ tree index on a heap file containing 30,000 records. The key field for this B+ tree index is a 40-byte string, and it is a candidate key. Pointers (i.e., record ids and page ids) are 10-byte values. The size of one disk page is 1000 bytes. The index was built in a bottom-up fashion using the bulk-loading algorithm, and the nodes at each level were filled up as much as possible.

    1. How many levels does the resulting tree have?
    2. For each level of the tree, how many nodes are at that level?
    3. How many levels would the resulting tree have if key compression is used and it reduces the average size of each key in an entry to 10 bytes?
    4. How many levels would the resulting tree have without key compression but with all pages 70 percent full?
  4. Using the defined hashing scheme to implement an index file and starting with an empty hash table (both global and local set to 0 when using extendible), add the following sequence. For this exercise, h(n) = n mod 8 and our bucket size is 4.

    0,1,3,7,8,9,12,14,19,21,24,32,46,44,48

    1. Extendible hashing. Use suffix bits.
    2. Static hashing
These homework solutions must be checked into Canvas in .pdf format

Late assignments are subject to a 20% penalty.



Copyright © 2016: Colorado State University for CS 430. All rights reserved.