The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 votes

Consider a relational table $r$ with sufficient number of records, having attributes $A_1, A_2, \dots ,A_n$ and let $1 \leq p \leq n$. Two queries $Q1$ and $Q2$ are given below.

  • $Q1: \pi_{A_1, \dots ,A_p} \left(\sigma_{A_p=c}\left(r\right)\right)$ where $c$ is a constant
  • $Q2: \pi_{A_1, \dots ,A_p} \left(\sigma_{c_1 \leq A_p \leq c_2}\left(r\right)\right)$ where $c_1$ and $c_2$ are constants.

The database can be configured to do ordered indexing on $A_p$ or hashing on $A_p$. Which of the following statements is TRUE?

  1. Ordered indexing will always outperform hashing for both queries
  2. Hashing will always outperform ordered indexing for both queries
  3. Hashing will outperform ordered indexing on $Q1$, but not on $Q2$
  4. Hashing will outperform ordered indexing on $Q2$, but not on $Q1$
asked in Databases by Veteran (97.7k points)
edited by | 2.6k views

4 Answers

+40 votes
Best answer

(C) Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too. For ex consider B+ Tree, once you have searched a key in B+ tree , you can find range of values via the block pointers pointing to another block of values on the leaf node level.

answered by Active (2.2k points)
edited by

Have you mistakenly written the word "too" in the statement "Hashing works well on the 'equal' queries, while ordered indexing works well better on range queries too"


Hey Actually I am not getting the language

Hashing will outperform ordered indexing on Q1??

Outperform? == not working fine

Here hashing will be work fine for same value data. while B+ tree works for sequential as well as duplicate data. 

outperform == perform better.
Can someone please share any good reference for this concept,

Hashing Vs Ordered Indexing

Hope it helps a bit.

If record are accessed for a particular value from table, hashing will do better.

If records are accessed in a range of values, ordered indexing will perform better.

+7 votes
answered by Junior (997 points)

@vijju532 Thanx !

+5 votes

Typically, ordered indexing is used unless it is known in advance that range queries will be infrequent, in which case hashing is used like Q2:πA1,…,Ap(σc1≤Ap≤c2(r)) . Hash organizations are particularly useful for temporary files created during query processing, if lookups on a key value are required and no ranges queries will be performed like Q1:πA1,…,Ap(σAp=c(r)).

c is correct

answered by Active (4.3k points)
+1 vote

Hashing is generally better at retrieving records having a specified value of the key.

If range queries are common, ordered indices are to be preferred.

answered by Active (1.5k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,811 questions
54,533 answers
75,585 users