GATE CS 2011 Q39 — File Organization and Indexing (B and B+ Trees)

To determine which indexing technique is better suited for each query, let's analyze how Hashing and Ordered Indexing handle equality and range searches:

1. Query $Q1$ (Equality Search): $$\pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$$ This query searches for records where the attribute $A_p$ is exactly equal to a constant $c$.
   • Hashing: A hash index uses a hash function to map the search key directly to its bucket, requiring $O(1)$ average-case disk I/O operations.
   • Ordered Indexing (e.g., B+ Tree): Finding a specific key requires traversing the tree from the root to a leaf, which takes $O(\log N)$ disk I/O operations.
   • Conclusion: Hashing outperforms ordered indexing for equality queries like $Q1$.


2. Query $Q2$ (Range Search): $$\pi_{A_1, \dots ,A_p} \left(\sigma_{c_1 \leq A_p \leq c_2}\left(r\right)\right)$$ This query retrieves records where the attribute $A_p$ falls within a range $[c_1, c_2]$.
   • Hashing: Hash functions do not preserve the ordering of keys. To answer a range query, hashing cannot easily locate the range boundaries, often requiring a full scan of the index or table.
   • Ordered Indexing: Since the keys are stored in sorted order, we can locate the starting point $c_1$ in $O(\log N)$ time and then sequentially traverse the leaf nodes to retrieve all records up to $c_2$.
   • Conclusion: Ordered indexing outperforms hashing for range queries like $Q2$.

Thus, hashing will outperform ordered indexing on $Q1$, but not on $Q2$.