Partitioned Hashing

1. • An alternative approach to multiple-key queries.
   • To construct a structure for queries on deposit involving bname and cname, we construct a hash structure for the key (cname, bname).
   • We split this hash function into two parts, one for each part of the key.
   • The first part depends only on the cname value.
   • The second part depends only on the bname value.
   • Figure 11.32 shows a sample partitioned hash function.
   • Note that pairs with the same cname or bname value will have 3 bits the same in the appropriate position.
   • To find the balance in all of Williams' accounts at the Perryridge branch, we compute h(Williams, Perryridge) and access the hash structure.
2. The same hash structure can be used to answer a query on one of the search keys:
   • Compute part of partitioned hash.
   • Access hash structure and scan buckets for which that part of the hash coincides.
   • Text doesn't say so, but the hash structure must have some grid-like form imposed on it to enable searching the structure based on only some part of the hash.
3. Partitioned hashing can also be extended to n-key search.