CPSC 461: Copyright © 2002 Katrin Becker 1998-2002 Last Modified October 20, 2001 10:16 PM

TREES REVIEW QUESTIONS

SHORT ANSWER QUESTIONS

1. [ 3 marks ] Why don't B-Trees get unbalanced?
2. [ 4 marks ] Why do we NOT use actual key values as separators in a B+Tree?
3. [ 4 marks ] If we compare a B-Tree with the index set of a B+Tree what can we say about the function (purpose) of the key values? (answer must be different from above)
4. [ 2 marks ] What does the simple prefix mean in the term Simple Prefix B+Tree?
5. [ 2 marks ] What quality of some simple sorts (like bubble sort) make them sometimes preferable to otherwise more efficient sorts when working with large files?
6. [ 3 marks ] Why is it essential to 'demote' the parent key of 2 B-Tree nodes that are being concatenated when a deletion causes underflow?
7. [ 5 marks ] Under what circumstances could you justify using actual key values as separators in a B+Tree?
8. [ 3 marks ] Why is it a good idea to use the same block size for the index set and the sequence set in a B+Tree structured file?
9. [ 4 marks ] How does a B-Tree stay moderately full and balanced?

LONG QUESTIONS

1. (worth 25 total) IN YOUR OWN WORDS, outline and explain the algorithm for loading a simple Prefix B+Tree. What advantages does this method offer over loading the file using the usual insertions?
2. (worth 10 total) Describe the primary differences between B-Trees, B*Trees, and B+Trees.
3. (worth 25 total) Suppose we are implementing a B+Tree that could allow for varying length separators in the index set.
   Records vary in length from 1K to 5K (ave. = 2K).
   There are 10 million records (currently)
   Keys are numbers up to 16 digits long.
   Node size for the tree has been set at 32K (for both index-set and sequence-set nodes)
   Fill in the following table:
   (for the calculations, assume 1K = 1000; state any assumptions you make - being able to explain how you arrived at your calculations is more important than the numbers you get)

   | MINIMUM | MAXIMUM | AVERAGE
   #Records/Sequence-Set Node |  |  |
   #Nodes in Sequence-Set |  |  |
   Index Key Length (assuming 1byte/digit) |  |  |
   Order of B+Tree |  |  |
   Approx. Size of File |  |  |

   Is there a more efficient way to store the index keys? What is it?
   Now what is the order of the tree?
   How big must a byte offset with in the file be? (in bits)
4. (worth 10 total)
   What is the maximum order of a B+Tree that allows varying length separators ( and thus also a variable number of separators) in the index-set block? Assume that the B+Tree uses a block size of 10Kbytes and the separators are of type ASCII. Explain how you calculated your answer (i.e. describe the structure used for the index-set).
5. (worth 10 total)
   Examine the following procedure, paying attention to what happens to the calculation of the median value. Compare the effect of calculating the median value before finding out where the new key goes against the effect of calculating the median value after ?placing? the new key.
   SPLIT ( X: keytype;
   Xr: pageptr;
   ThisPage: pageptr;
   K: position; Y: keytype; Yr: pageptr);
   /* insert key X and pointer Xr at position K into ThisPage and
   splits into ThisPage and Yr with median key Y */
   var i, Median : position;
   begin
   if K <= Min then
   /* determine if new key goes in left or right half */
   Median := Min
   else
   Median := Min + 1;
   new(Yr);/* new node always goes on the right */
   with ThisPage do
   for i := Median + 1 to Max do/* move half the keys */
   Yr^.Key[i - Median] := Key[i];
   Yr^.Child[i - Median] := Child[i];
   Yr^.Count := Max - Median;
   Count := Median;
   if k <= Min then/* put NewKey in ThisPage */
   INSERT(X, Xr, ThisPage, K);
   else/* put new key into Yr */
   INSERT(X, Xr, Yr, K - Median);
   Y := Key[Count];
   Yr^.Child[0] := Child[Count]
   Count := Count - 1;
   end
   end
6. (worth 10 total)
   Given the following B-tree of order 3:
   a) Redraw the tree after insertion of the keys 7, 37, and 57
   b) Redraw the tree
7. (worth 30 total)
   Notice that in this tree, the order of the tree is the same as the number of pointers, and that every key in the node has a left pointer. Notice also that only the leaves contain unique keys – all others represent the highest key in the child pointed to by the pointer on the left.
   Compare this B-Tree with the version studied in class (and in the notes) in the following ways:
   a) [5 marks] How does a search for a key in this B-Tree differ from one in the B-Tree studied in class?
   b) [5 marks] What needs to be done differently during an insertion that causes a split?
   c) [5 marks] What needs to be done when the highest key in one of the leaf nodes gets deleted?
   d) [5 marks] How is the minimum height of this tree different from the one we did in class?
   e) [10 marks] What are some advantages and disadvantages of implementing the above tree?
8. (worth 10 total)
   A) [5 marks]Re-Draw the tree after the following INSERTIONs: 65, 50, 45
   B) [5 marks]Re-draw the tree again (starting with the original tree) after the following DELETIONS:10, 5, 3

-CPSC 461: Copyright©x 2000 Katrin Becker 1998-2002 Last ModifiedOctober 20, 2001-10:16 PM