Software Design & Engineering Chapter 14 This Means That Picking The First Index

—

(d) i = 3, n = 8, r = 16

—

1000

000 0000

—

1100

100 0100

—

1101

101 0101

17

—

Exercise 14.3.7

We could use double indirection by having hash table point to pointers to records

Exercise 14.3.8

(a) The number of buckets with twice as many keys would be n−2⌊log2n⌋and

so the number of overﬂow blocks would be cnk −nk

Exercise 14.3.9

In the best case, all buckets will have a number of records that is divisible by 100.

Then, the number of blocks needed is 10000.

Section 14.5

Exercise 14.5.1

(a) hd dimension: 210, speed dimension: 1.9, 2.15, 2.7, 3.0

Exercise 14.5.2

hd dimension: partition among grids 210 and 260, speed dimension: partition

Exercise 14.5.3

We could use the same function as in 14.5.1 (c), adding a third bit to the result. the

third bit would be zero for ram values less than 1024 and would be one otherwise.

Exercise 14.5.4

Exercise 14.5.5

(a) 25

Exercise 14.5.6

(a) p2m+(1 −p)2n−m

Section 14.6

Exercise 14.6.1

(a) 1.42 –> 512

1.86 –> 2048

(b) 512 –> 80

250

1024 –> 160

(c) 1.42 –> 512 –> 80

1.86 –> 2048 –> 160

2.00 –> 1024 –> 250

20

2048 –> 300

Exercise 14.6.2

speed 2.30

ram 2000

ram 1000

22

speed 2.30

ram 1000

23

speed 2.30

hd 280

hd 210

speed 2.05

2.80, 300

3.20, 320

speed 2.70

speed 2.00

24

Exercise 14.6.3

(a) For the dense index on xwe would need 100/10 =10 blocks, and so for

the sparse index of xwe would need 1 block. Therefore, we need two disk

(b) For the dense index on ywe would need 1000/10 =100 blocks, and so for

the sparse index on ywe would need two levels (10 blocks and 1 block).

Exercise 14.6.4

To evaluate 20 6x635 we need to read the root, then 3 blocks for the range (11-

Exercise 14.6.5

Exercise 14.6.6

The changes would be: 1) right child of the ”Salary 80” would be a new node

Exercise 14.6.7

(a) Since the tree is balanced, n=2k, where kis some natural number repre-

senting the number of levels in the tree (not counting the root)(really log2n).

(b) This is a generalization of (a) where we will reduce the number of leafs we

(c) For partitioned hash table, we will only need to examine 2xof the buckets,

where xis the number of bits used for all ddimensions minus the number

of bits used in mdimensions that are for the specified attributes. Note that

26

Exercise 14.6.8

3, 2000

2, 2750 2, 1250

NW

NE SE

SW

3.20, 512

NW

SW

NW

2, 2750

27

Exercise 14.6.9

We use the compass designations for the quadrants and for the children of the

3, 2000, 200

NWF

SWF

SWB

1.42, 512, 80

1.86, 2048, 160

SEBNWB

2.20, 2048, 250

3.20, 512, 250

2, 1250, 300

29

Exercise 14.6.10

Exercise 14.6.11

The R-tree would have a root and three levels. Since the overlays do not aﬀect the

Section 14.7

Exercise 14.7.1

All keys are in ascending order.

(a) uncompressed:

001000000000

000000000010

compressed:

1010

30

00

101111010101

11010000

(b) uncompressed:

011010000000

(c) uncompressed:

001000000000

000000000011

Exercise 14.7.2

100000001000 OR 000000010000 = 100000011000

31

Exercise 14.7.3

(a) 125000m

Exercise 14.7.4

Exercise 14.7.5

(a) 0100110111110101