27
C H A P T E R 1 1
I
nd
e
x
i
n
g
and
H
a
s
h
i
n
g
E
x
e
r
c
i
s
e
s
11.1 Why are B-trees, which have a very large fanout (i.e., number of children),
preferred
over binary trees (having at most two children) in the context of disk-
based databases?
. .
.3
11.4 Name two factors that affect the decision of the page size of a
B
+
-tree (e.g.,
should the page be 1KB or 16 KB).
. .
.2
11.5 Give three
alternative
ways of
evaluating
a selection of the form
σ
A
=
$1
∧
B
=
$2
(
r
)
if secondary indices are available on A and on B.
. .
.3
11.6 Suppose I store two dimensional points as the location attribute of a relation,
and queries ask for tuples whose location is at exactly a given point. What sort
of index is best for this case?
. .
.2
28 Chapter 11 Indexing and
Hashing
11.9 The textbook description of static hashing assumes that a large contiguous
stretch of disk blocks can be allocated to a static hash table. Suppose you can
only allocate C contiguous blocks. Briefly sketch how to implement the hash
table, if it can be much larger than C blocks. Access to a block should still be
efficient.
. .
.3
11.10 What should you do to make sure that the worst case occupancy of a
B
+
-tree
is at least 75%?
. .
.2
11.11 Suppose I have a relation with
n
r
tuples on which I want to build a secondary
11.12 Suppose you want to efficiently support queries of the following form
select sum(A) from r where v1 < r.B and v2 > r.B
11.13 In extendible hashing, if the occupancy of a bucket is too low, what bucket(s)
are you allowed to merge the underfull bucket with?
. .
.2
11.14 Suppose we insert the following records into an extendible hash structure in
the order shown: (B,1), (D,1), (D,2), (M,1), (P,1), (P,2), (P,3). Assume that
B
11.15 Suppose that we are using extendible hashing on a file containing records with
the following search key values: 2,3,5,7,11,17,19,23,29
Show the extendible hash structure for this file if the hash function is h(x)
= x mod 8 and buckets can hold three records. Further, assume that we con–
Exercises
29
11.16 a. Outline the steps in building a
B
+
-tree bottom–up (that is, directly from
a
given
relation without performing a series of inserts).
. . .4
11.17 a. Is it always a good idea to have an index. In other words, what are the
pros
and
cons for creating an index.
. . .1
b. Given an SQL query of the form
select
L
from
r
1
, . . .
r
n
where
P
where P
represents a predicate, list indices that may potentiay be useful for an- swering
the query.
. .
.3
11.18 Suppose access to some key values in a
B
+
-tree
is very common relative to others,
11.19 Describe an efficient algorithm to build a
B
+
-tree on a file which is sorted on the
indexed attribute. Also, outline the cost of the algorithm in terms of
I
/
O’s.
Assume