--------------------------------------------------------------------
B+ tree
--------------------------------------------------------------------

Build a B+ tree from the following keys. Insert the keys into the tree in the given order.
39,15,50,70,79,83,72,43,75,45,60,80  
Let's suppose that a node (block) can contain 3 keys and 4 pointers.
For some help we show the first split of a block:

                       15|39|50
insert 70

                          50
                    15|39    50|70

Hint:
----

When a leaf block overflows we split it into two. We put half of the keys into the first block,
the other half into the second (new) one. We create a pointer pointing to the new block and put 
this into the parent block with an appropriate key (preserving the B+ tree properties).

When a non-leaf block overflows we split it into two. Half of the keys goes into the first one,
the other half into the second one. But one key in the middle doesn't go into either of them.
It goes up into the parent block with an appropriate pointer.

If there is no parent block (when we split the root) we create a new root block having one key 
(the up rising) and the two pointers pointing to the just splitted parts.


--------------------------------------------------------------------
Extensible hash table
--------------------------------------------------------------------

The size of the bucket array is always a power of 2.
Let's suppose we can put two records into a block, k=4 (the hash function computes k bits), 
i=1 (the bucket numbers use the first i bits); j (in the nub of the blocks) indicates how many bits of 
the hash function' sequence is used in this block. 

i=1
     ----      0001
 0   | -|--->  ----1
     |  |     
 1   | -|--->  1001
     ----      1100
               ----1 
  
  bucket dir   blocks

Insert the following values into the hash table 

0011, 0110, 1011, 0111, 1110, 1111, 0100


A litthe hint:
-------------

To insert a record with search key K , we compute h(K ), take the first i bits of this bit sequence, 
and go to the entry of the bucket array indexed by these i bits, then follow the pointer in this entry
and arrive at a block B. If there is no room in the block B we do the following:
1. If j < i we split B into two; distribute records in B to the two blocks based on the (j+1)st bit;
   put j+1 into the block's nub; adjust the pointers in the bucket array 
2. If j = i we increment i by 1; double the length of the bucket array; put new pointers into the array;
   finally we proceed to split block B as in case 1.


--------------------------------------------------------------------
Linear hash table
--------------------------------------------------------------------

Let's suppose we can put two records into a block and the blocks contain the following records:

0000   0101
1110   
----   ----   
 0      1    

n = 2 (the current number of buckets); i = 1 (we use the last i bits from the sequence)
r/n = 2.4 (predefined threshold, where r is the current number of records)

Insert the following values into the hash table 

0001, 0110, 1011, 0111, 1100, 1111, 0100


A little hint:
-------------

To insert a record with search key K , we compute h(K ), take the last i bits of this bit sequence.
If a bucket with this number (last i bits) exists, we put the record in it. If there is no room
in the last block of this bucket, we chain a new block to the bucket.
If the bucket with this number (last i bits) doesn't exist, we put the record in the bucket
which differs in the first bit.
If r/n is greater than a threshold, we add a new bucket to the structure.
If n exceeds 2**i we increment i by 1.