Hashing is a data structure which can be used to implement Index of any database just like B-Tree, B+ tree etc. Strictly speaking, if a file itself is organized using hashing, there is no need for a separate hash index structure on it.
Index :
Databases spend a lot of their time finding things — and so finding needs to be as fast as possible. A crucial element of current database management systems is the index, which speeds up searches. Just like we have Index in Our books to find our desired topic in the book faster.
Index types:
1. Ordered indices — Based on sorting database values
2. Hash indices — Based on a uniform distribution of values across a range of buckets, as determined by a hash function
Ordered Indices :
An index is associated with some search key — that is, one or more attributes in a file/table/relation for which the index provides fast access.
Two types of orders or sorting here :
- Ordering of the index (based on its search key)
- Ordering of the file/table/relation as it is stored
A single file/table/relation may have multiple indices, each using different search keys.
A clustering,clustered, or primary index is an index whose search key also defines the ordering of the file/ table/relation (Not to be confused with primary keys — a clustering index’s search key is often the primary key, but doesn’t necessarily have to be so)
A nonclustering, nonclustered, or secondary index specifies an order that is different from the file/table/relation’s sequential order.
HASH INDICES :
Alternative to sequential file organization and indices.
Terminology : A bucket is a unit of storage for one or more records.
If $K$ is the set of all search-key values, and $B$ is the set of all bucket addresses, we define a hash function as a function h that maps $K$ to $B$ . To search for records with search-key value $K_i$, we calculate $h(K_i)$ and access the bucket at that address. Can be used for storing data (hash file organization) or for building indices (hash index organization).
When hashing is used for index structures, buckets store (search-key values + pointer) tuples instead of data. The pointer records then refer to the underlying data, in the same way as with a B+-tree . Hash index lookups are a matter of hashing the desired search-key value, retrieving the bucket, then dereferencing the appropriate pointer in the bucket. Primarily used for secondary indices, since a hash file organization already functions as a clustering index.
More about HASHING or HASH Data Structures can be studied from Cormen and More about Indexes can be learned from any Database book like Korth or Navathe.
