CSC 457/557 Assignment 3

due Friday February 3, 2018

1. You are going to insert 3 Variable-length records into an empty block, using the folowing method:
  1. Put the first record at the END of the block, and right after the block header, put a pointer to where that record starts.
  2. Continue to insert blocks at the end of the unused space, and pointers to them.
  3. ... as space permits -- assume there is enough space.)
Draw a diagram showing how this would look.
Now suppose the middle record is updated and needs more length, and also another record with a shorter length than the original middle record is to be inserted. In the second box, show how you would change the block.

bheader
bheader

2. Using B+ tree blocks with 3 keys (and 4 pointers), draw a B+ tree with the keys: FM, GK, JN, JP, LV, RB, TC.
(print and use the blank tree mentioned below)
        a. Now continue to insert, splitting blocks as necessary: SR, SW. Draw the B+ Tree you have come up with.
        b. Next, delete FM, and indicate how the tree changes (Either X out what goes away, or by redrawing if necessary)

I have drawn a nice blank B+ Tree for your use (LibreOffice Draw - print, or select, move and/or copy/paste the blocks to get a nicer layout..) The book example is B-tree.gif.

3. Using hashing, do these same insertions and deletion in 5 blocks, using as hash function the sum of the two letters, MOD 5 (or MOD 4, your choice)
       By my calculation, with A=1 to Z=26, these are:
FM GK JN JP LV RB TC SR SW
19 18 24 26 34 20 23 37 42