Introduction to database management systems

Hashing is transformation of a string of characters into a usually shorter fixed-length value or key that represents original string. Hashing is used to index and retrieve items in a database because it is faster to find item using shorter hashed key than to find it using original value.

Hash Organization

• Bucket – The hash file stores data in bucket format. A bucket typically stores one complete disk block, which in turn can store one or more records. 

• Hash Function − A hash function, h, is a mapping function that maps all set of search-keys K to address where actual records are placed.

Static Hashing

• A bucket is a unit of storage containing one or more records (a bucket is typically a disk block).
• In a hash file organization we obtain bucket of a record directly from its search-key value using a hash function.
• Hash function h is a function from set of all search-key values K to the set of all bucket addresses B.
• Hash function is used to locate records for access, insertion as well as deletion.
• Records with different search-key values may be mapped to same bucket; thus entire bucket has to be searched sequentially to locate a record.

Dynamic Hashing 

• Good for database that grows and shrinks in size
• Allows hash function to be modified dynamically
• Extendable hashing – one form of dynamic hashing
• Hash function generates values over a large range — typically b -bit integers, with b= 32.
• At any time use only a prefix of hash function to index into a table of bucket addresses.
• Let length of prefix be i bits, 0 ≤ i ≤ 32. 
• Value of i grows and shrinks as the size of database grows and shrinks.
• Multiple entries in bucket address table may point to a bucket.