recategorized by
2,097 views
2 votes
2 votes

Consider a table that describes the customers:

$\text{Customers(custid, name, gender, rating)}$

The rating value is an integer in the range $1$ to $5$ and only two values $\text{(male and female)}$
are recorded for $gender.$ Consider the query $\text{"how many male customers have a rating of 5" ?}$
The best indexing mechanism appropriate for the query is

  1. Linear hashing
  2. Extendible hashing 
  3. B+ tree
  4. Bit-mapped index
recategorized by

3 Answers

9 votes
9 votes

D) Bit-mapped index

This is because both the columns GENDER and RATING has less unique values or we can say columns with less cardinality. GENDER has only 2 values (M, F) while RATING has ( 1, 2, 3, 4, 5 ). Even though these columns have less frequent values, they are queried most often.

Why Bit-mapped Index?

Let's represent the columns using bits. Rules for creating bit-map index are:

a) #bits is equal to the #rows in the table. Say table has 10k rows then we'll have 10k bits for a single bitmap index.

b) For each unique value, we have a separate index. Say for Male in GENDER we've one bit-map index and another for Female, while for rating we've 5 bit-map indices.

c) If we have any matching value in the column for the row, then that row bit will have ‘1’, else ‘0’. Below example will illustrate the fact.

Customers
CUSTID NAME GENDER RATING
100 A M 5
200 B F 1
300 C M 2
400 D F 1

Bitmap indexes for Gender are:

 M: 1010

  F:  0101

1st bit is for 1st row and similarly thereafter.

Bitmap indexes for RATING are:

1: 0101

2: 0010

3: 0000

4: 0000

5: 1000

The query will search the bitmap index for both of this columns and perform logical ‘AND’ operation on those indexes to get the actual address of the result.

Bitmap index for M: 1010

                                         AND

Bitmap index for 5:  1000


                                        1000 => Implies that the first row has the result of the query. 

Here fetching the bitmap index and performing the logical ‘AND’ operation to get the result is comparatively faster. Hence this method of storage is used for this kind of data.

Having said that bitmap indexes are not that useful in this scenarios:

  • When there is multiple insert/update/delete on the table from different users, it may cause deadlock on the tables. It will take time to perform the DML transaction and then to update the bitmap index. Hence when there is multiple DML transaction from different users, it will not be able to perform transaction quickly and causing the deadlock.
  • When there is a large number of records, there is an overhead to maintain this bitmap indexes. Each time a new record is entered, we have to modify the bitmap index throughout, which is a tedious and time consuming.
5 votes
5 votes

The best indexing mechanism appropriate for the query is Bit-mapped index.
bitmap index is a special kind of database index that uses bitmaps.
Bitmap indexes are used when the number of distinct values in a column is relatively low.

Customers
Custid Name Gender Rating
120 Joe M 3
121 Rude M 5
122 Woe F 5
123 Ram M 4

Bit Map for Gender- 

M F
1 0
1 0
0 1
1 0

Bit map for Rating- 

1 2 3 4 5
0 0 1 0 0
0 0 0 0 1
0 0 0 0 1
0 0 0 1 0


Now consider the query-
“How many male customers have a rating of 5?”
Take the first bit vector for gender and do a bitwise AND with the fifth bit vector for the rating to obtain a bit vector that has 1 for every male customer with rating 5. We can then count the number of 1s in this bit vector to answer the query.

The benefits of using a bitmap index over a B tree index are storage (with low cardinality, bitmap indexes are pretty compact), and when filtering on multiple columns, then the corresponding indexes can be merged with bitwise operations before actually selecting the data.

2 votes
2 votes

In My point Only Possible is  Bit Map Index

Why is It Is Used When  optimize search and retrieval for low-variability data

 Although a B-tree or B+tree is the standard index structure used for highly variable data, such as identity values, names, and street addresses, this type of index structure doesn't work well with data that has low variability, such as gender (M, F) or nullable (Y, N). So bit map index is used in this type of situation.

pls Correct me i Done Mistaken 

Answer:

Related questions

5 votes
5 votes
2 answers
3
gatecse asked Dec 17, 2017
2,738 views
Consider the following schema:$\text{Sailors(sid,sname,rating,age)}$$\text{Boats(bid,bname,colour)}$$\text{Reserves(sid,bid,day)}$Two boats can have the same name but the...
5 votes
5 votes
1 answer
4
gatecse asked Dec 17, 2017
4,291 views
Consider the schema$\text{Sailors(sid,sname,rating,age) with the following data}$$\begin{array}{|l|l|l|l|} \hline \textbf{sid} & \textbf{sname} & \textbf{rating} & \textb...