24-03-2012, 02:32 PM
B+ Tree and Hashing
302-B+tree-ind-hash.pdf (Size: 982.48 KB / Downloads: 293)
Underflow
– When number of search-key values < n/2-1
–Leaf Node
•Redistribute to sibling
•Right node not less than left node
•Replace the between-value in parent
by their smallest value of the right
node
•Merge (contain too few entries)
•Move all values, pointers to left node
•Remove the between-value in parent
Hash function returns b bits
• Only the prefix i bits are used to hash the item
• There are 2i entries in the bucket address table
• Let ij be the length of the common hash prefix for data bucket
j, there is 2(i-ij) entries in bucket address table points to j
Splitting (Case 1 ij=i)
– Only one entry in bucket address table points to data
bucket j
– i++; split data bucket j to j, z; ij=iz=i; rehash all items
previously in j;