Software Design & Engineering Chapter 14 For the sparse index we need a key-pointer

Solutions Manual

Chapter 14

Section 14.1

Exercise 14.1.1

(a) For dense index we need a key-pointer pair for each record, and so will need

n

10 blocks. For the data, we will need n

3blocks, and so the total number of

Exercise 14.1.2

(a) For dense index we need a key-pointer pair for each record, and so will need

(b) For the sparse index we need a key-pointer pair for each of the data block,

2

Exercise 14.1.3

(a) We need the same amount of blocks for the data as in 14.1.1 (a). We will

need log10nlevels of the index with total number of blocks of 1 +10 +102+

Exercise 14.1.4

Since the records could start at any location in the block the number of blocks

needed is m

10+1 (e.g. for m=0 we would need one block and for m=10 we

Exercise 14.1.5

(a) We would need 1000 (for records) +3000

50 (for pointers) +300

10 (for pointer-

value pairs), for the total of 1090.

Exercise 14.1.6

In the best case, we will only need to read one index file block to locate the key-

value pair we need. Further, in the best case, the records with the same value

would be clustered (i.e. 3 records per block). Therefore, we would need 1 (for

3

index) +1 (for pointers) +&10

3‘=6 I/O’s.

In the worst case, we would need to read all of the index file to locate the key-

Exercise 14.1.7

(a) The average number of words per document is

10000

X

n=1

100000

√n

1000 ≈20000

(b) In the worst case, each word will appear in each document at least once,

10 (for the word-pointer pairs) =201000.

(c) There are total of 20000000 word occurrences (from (a)), so we would need

20000000

50 (for the bucket pointers) +10000

10 (for the word-pointer pairs) =

401000.

Exercise 14.1.8

(a) We could first construct a relation C containing the bucket entries for ”cat”,

and relation D, containing the bucket entries for ”dog”. Then we would

4

join C and D picking only the document pointers such that D.type =C.type

Section 14.2

Exercise 14.2.1

(a) We would need 1000000

10 =100000 blocks for the data +1000000

69 =14493

blocks for the leaf nodes +14493

70 =208 blocks for the next B-tree level,

208

70 =3 for the next level, and one block for the root. The total would be

114705 blocks. We would need 5 I/O’s (4 for the B-tree levels +data page).

4 I/O’s (4 for the B-tree levels).

5

(e) We would need 1000000

15 =66667 blocks for the primary data +66667 for

the overﬂow blocks, 66667

Exercise 14.2.2

Note that the number of blocks does not change. We only need to calculate the

average number of disk I/O’s.

(a) We would need 4 I/O’s to get to the first leaf block. To match 1000 records

we need to examine 1000

Exercise 14.2.3

12n+4(n+1) 616384, so 1023 keys and 1024 pointers.

Exercise 14.2.4

(a) 5 keys and 6 pointers for the interior nodes, 5 keys and 5 pointers in the leaf

nodes

6

(b) 5 keys and 6 pointers for the interior nodes, 6 keys and 6 pointers in the leaf

nodes

Exercise 14.2.5

(a) Start at the root. 41 >13 so follow the second pointer. 31 641 <43 so

follow the third pointer. We find one of the keys is 41 so we follow the third

pointer to the data block.

(d) Start at the root. Follow leftmost pointers until the leaf node. For each of

the keys, if it less than 30, follow the pointer to the data block. Thus we

will follow data pointers for keys 2, 3, 5. Since 30 >5 follow the next leaf

pointer and repeat. Thus we will follow the data pointers for keys 7, 11,

then next leaf, 13, 17, 19, next, 23, 29, next. 30 <31 so we are done.

(e) Start at the root. 30 >13 so follow the second pointer. 23 630 <31 so

follow the second pointer. We find none of the keys is greater than 30 so we

7

(g) We search for the key 14, this brings us to the leave with keys 13,17,19.

There is no room for 14 so we split. We create new block and move keys

17 and 19 there. The parent interior node (keys 23,31,43) has no room so

Next we search for the key 15. This brings us to the leave with keys 13,14.

We insert 15. No other changes.

Next we search for the leave for key 16. This brings us to the leave with

(h) We search for the key 23. This brings us to the leave node with keys 23,

29. We delete key 23 and borrow the highest key (19) from the neighboring

leave node. We also update the parent interior node to include key 19. The

result is:

8

(i) As in (h) we locate the leave node with keys 23,29. We delete the node

and all leave nodes that follow. We also update the parent interior node

Exercise 14.2.6

(a) Follow the same lookup procedure as for ”non-duplicate” B-tree. If the key

is found, follow through the current (and subsequent leaves to the right)

Exercise 14.2.7

When borrowing from the left adjacent non-sibling node, no additional logic in

the existing algorithm is required. When borrowing from the right adjacent non-

Exercise 14.2.8

Interior nodes must have at least 2 pointers and at least 1 key and leaf nodes must

have at least 2 pointers and at least 2 keys (the max is 3 keys).

(a) The only possible layouts for the leaf nodes are 2-2-2 and 3-3. For both

cases the next level must be the root. So there are two diﬀerent B-trees.

(b) The only possible layouts for the leaf nodes are: 2-2-2-2-2, 2-2-3-3, 2-3-

2-3, 2-3-3-2, 3-2-2-3, 3-2-3-2, 3-3-2-2. For the case with 4 leaves, we can

(c) The maximum number of leaf nodes we could have is 7 where one node

must have 3 keys and the rest of the nodes must have 2 keys (e.g. 2-2-2-2-2-

2-3). There are 7C1=7 combinations. For each of these combinations we

Exercise 14.2.9

When we split the leaf blocks we divide pointers 2 and 2, so at the time of 4th level

added we will have only pairs of keys at each leaf. Similarly, because we split 3

Section 14.3

Exercise 14.3.1

(a) —

d

0—

g

—

(b) —

d

0—

g

11

(c) —

d k

0—

g

—

(d) —

g

0—

k

—

f n

3—

j

—

Exercise 14.3.2

For deletion, we would locate the record by applying hash function and then

searching within the bucket (following the overﬂow linked list if needed). If delet-

Exercise 14.3.3

(a) For lookup and deletion we simply need to continue looking for other records

with the same key in the current bucket. No changes for insert.

(b) For lookup and deletion we not only need to continue looking for other

records with the same key in the current bucket, but also check other buckets

13

Exercise 14.3.4

(a) Since each integer can be represented as 10a+bwhere 0 6b<10 and so

its square modulo 10 is the same as b2modulo 10. The squares of 0 to 9

Exercise 14.3.5

In order for all members of the block to go to the same created block, they must

Exercise 14.3.6

(a) —

0000

000

0001

—

1000

100

1001

—

1010

101

(b) i = 3, n = 6, r = 16

—

0000

000 1000

15

—

(c) —

0001

000

0000

—

0011

001

0010

—

101

1010

—

1101

110

1100

16