CSci351 Introduction to File Processing: Homework 5

Due date: Wednesday, April 30, 2008 in class
Each homework may have a different weight based on its difficulty level.
Absolutely no copying others' work
  1. Balanced binary trees can be effective index structures for memory-based indexing, but they have several drawbacks when they become so large that part of all of them must be kept on secondary storage.
    1. Why is it important to keep search trees balanced?     (05%)



    2. In what way is an AVL tree better than a simple binary search tree?     (05%)



    3. Suppose you have a file with 4,000,000 keys stored on disk in a completely full, balanced binary search tree.     (10%)
      1. If the tree is not paged, what is the maximum number of accesses required to find a key?



      2. If the tree is paged in the manner illustrated in Figure 9.12, but with each page able to hold 31 keys and to branch to 32 new pages, what is the maximum number of accesses required to find a key?



      3. If the page size is increased to hold 255 keys with branches to 256 nodes, how does the maximum number of accesses change?




  2. Show the B-tree of order four that results from loading the following set of keys in order:     (15%) 
       D  I  L  M  F  G  T  Q  A  S  N  E  X  O  K  Z  J  B  U  Y






  3. Given a B-tree of order 512,     (15%)
    1. What is the maximum number of descendants from a page?

    2. What is the minimum number of descendants from a page (excluding the root and leaves)?

    3. What is the minimum number of descendants from the root?

    4. What is the maximum depth of the tree if it contains 1,000,000 keys?

  4. Show the trees that result after each of the keys I, F, H, and G is deleted from the B-tree of Figure 9.15(c).     (15%)








  5. Consider the simple prefix B+ tree shown in Figure 10.7. Suppose a key added to Block 2 results in a split of Block 2 and the consequent addition of Block 8, so Blocks 2 and 8 appear as follows:     (20%) 
           ...  ——>  Bolen—Bor ——> CAD—CAGE ——> ...
                     2             8
    1. What does the tree look like after the insertion?





    2. Suppose that, subsequent to the insertion, a deletion causes underflow and the consequent concatenation of Blocks 1 and 2. What does the tree look like after the deletion?





    3. Describe a case in which a deletion results in redistribution rather than concatenation, and show the effect it has on the tree.






  6. Use the data stored in the simple prefix B+ tree in Figure 10.16 to construct a B+ tree. Assume that the index set of the B+ tree is of order four.     (15%)