Problem with Hashing... (cont)
Important concept for flexible hashing: splitting
- consider one page (all tuples have same hash value)
- recompute page numbers by considering one extra bit
- if current page is
101, new pages have hashes 0101 and 1101
- some tuples stay in page
0101 (was 101)
- some tuples move to page
1101 (new page)
- also, rehash any tuples in overflow pages of page
101
Result: expandable data file, never requiring a complete file rebuild
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}