DESCO; Assistant Engineer (CSE) Written Exam: 2016প্রশ্ন ও সমাধান

A hash table/hash index stores data using a hash function that maps a key directly to a bucket/slot address, giving O(1) average-case lookup instead of a tree index's O(log n).

How databases use hashing:

• Hash indexing: a hash function applied to the indexed column's value gives the exact bucket/disk block holding the row — no multi-level tree traversal needed.
• Hash joins: to join two large tables, the DBMS builds an in-memory hash table on the smaller table's join key, then probes it while scanning the larger table — far faster than a nested-loop join.
• Hash partitioning: distributes rows across partitions/shards by hashing the partition key, balancing load in distributed databases.

Example: hash("101") -> bucket 4 directly locates the row where emp_id = 101.

graph LR
  K["Key: emp_id = 101"] --> H["Hash Function h(k)"]
  H --> B4["Bucket 4"]
  B4 --> Rec[(Row data)]

Limitation: Hash indexes support only equality lookups (=), not range queries (BETWEEN, <, >) — B-Tree indexes are still required for those.

Takeaway: Hashing gives the fastest possible exact-match lookup (O(1) average) but no range/sort support — production databases combine hash and B-Tree indexes depending on the query pattern.