Database Storage & Design Chapter 17 Homework Indexing Structures For Files Indexing Structures For Files Answers Selected

Unlock access to all the studying documents.

View Full Document

Chapter 17: Indexing Structures for Files

CHAPTER 17: INDEXING STRUCTURES FOR FILES

Answers to Selected Exercises

17.18 – Consider a disk with block size B=512 bytes. A block pointer is P=6 bytes long,

and a record pointer is P R =7 bytes long. A file has r=30,000 EMPLOYEE records

of fixed-length. Each record has the following fields: NAME (30 bytes), SSN (9

bytes), DEPARTMENTCODE (9 bytes), ADDRESS (40 bytes), PHONE (9 bytes),

BIRTHDATE (8 bytes), SEX (1 byte), JOBCODE (4 bytes), SALARY (4 bytes, real

number). An additional byte is used as a deletion marker.

(a) Calculate the record size R in bytes.

(b) Calculate the blocking factor bfr and the number of file blocks b assuming an

unspanned organization.

index on SSN. Calculate (i) the index blocking factor bfr i (which is also the index

fan-out fo); (ii) the number of first-level index entries and the number of first-level

index blocks; (iii) the number of levels needed if we make it into a multi-level

index; (iv) the total number of blocks required by the multi-level index; and

(v) the number of block accesses needed to search for and retrieve a record from

the file—given its SSN value—using the primary index.

(d) Suppose the file is not ordered by the key field SSN and we want to construct a

secondary index on SSN. Repeat the previous exercise (part c) for the secondary

index and compare with the primary index.

(e) Suppose the file is not ordered by the non-key field DEPARTMENTCODE and we want

to construct a secondary index on SSN using Option 3 of Section 18.1.3, with an extra

level of indirection that stores record pointers. Assume there are 1000 distinct

values of DEPARTMENTCODE, and that the EMPLOYEE records are evenly distributed

among these values. Calculate (i) the index blocking factor bfr i (which is also the

index fan-out fo); (ii) the number of blocks needed by the level of indirection that

stores record pointers; (iii) the number of first-level index entries and the

number of first-level index blocks; (iv) the number of levels needed if we make it a

multi-level index; (v) the total number of blocks required by the multi-level index

and the blocks used in the extra level of indirection; and (vi) the approximate

number of block accesses needed to search for and retrieve all records in the file

having a specific DEPARTMENTCODE value using the index.

(f) Suppose the file is ordered by the non-key field DEPARTMENTCODE and we want to

construct a clustering index on DEPARTMENTCODE that uses block anchors (every

new value of DEPARTMENTCODE starts at the beginning of a new block). Assume

there are 1000 distinct values of DEPARTMENTCODE, and that the EMPLOYEE

records are evenly distributed among these values. Calculate (i) the index blocking

factor bfr i (which is also the index fan-out fo); (ii) the number of first-level

index entries and the number of first-level index blocks; (iii) the number of levels

needed if we make it a multi-level index; (iv) the total number of blocks required

by the multi-level index; and (v) the number of block accesses needed to search for

and retrieve all records in the file having a specific DEPARTMENTCODE value using

the clustering index (assume that multiple blocks in a cluster are either contiguous

or linked by pointers).

Chapter 17: Indexing Structures for Files

(g) Suppose the file is not ordered by the key field Ssn and we want to construct a B + –

tree

access structure (index) on SSN. Calculate (i) the orders p and p leaf of the

B + -tree; (ii) the number of leaf-level blocks needed if blocks are approximately

69% full (rounded up for convenience); (iii) the number of levels needed if

internal nodes are also 69% full (rounded up for convenience); (iv) the total

number of blocks required by the B + -tree; and (v) the number of block accesses

needed to search for and retrieve a record from the file—given its SSN value—

using the B + -tree.

Answer:

(a) Record length R = (30 + 9 + 9 + 40 + 9 + 8 + 1 + 4 + 4) + 1 = 115 bytes

Index blocking factor bfr i = fo = floor(B/R i ) = floor(512/15) = 34

ii. Number of first-level index entries r 1 = number of file blocks b = 7500 entries

Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(7500/34)

(d) i. Index record size R i = (V SSN + P) = (9 + 6) = 15 bytes

Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/15)

= 34 index records per block

(This has not changed from part (c) above)

(Alternative solution: The previous solution assumes that leaf-level index blocks contain

block pointers; it is also possible to assume that they contain record pointers, in

Chapter 17: Indexing Structures for Files

(Alternative solution:

Number of first-level index entries r 1 = number of file records r = 30000

Number of first-level index blocks b 1 = ceiling(r 1 /bfr i ) = ceiling(30000/32)

= 938 blocks)

iii. We can calculate the number of levels as follows:

Number of second-level index entries r 2 = number of first-level index blocks b 1

= 883 entries

Number of second-level index blocks b 2 = ceiling(r 2 /bfr i ) = ceiling(883/34)

= 26 blocks

Number of third-level index entries r 3 = number of second-level index blocks b 2

(e) i. Index record size R i = (V DEPARTMENTCODE + P) = (9 + 6) = 15 bytes

Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/15)

= 34 index records per block

ii. There are 1000 distinct values of DEPARTMENTCODE, so the average number of

records for each value is (r/1000) = (30000/1000) = 30

Since a record pointer size P R = 7 bytes, the number of bytes needed at the level

Chapter 17: Indexing Structures for Files

(f) i. Index record size R i = (V DEPARTMENTCODE + P) = (9 + 6) = 15 bytes

Index blocking factor bfr i = (fan-out) fo = floor(B/R i ) = floor(512/15)

= 34 index records per block

ii. Number of first-level index entries r 1

= number of distinct DEPARTMENTCODE values= 1000 entries

Number of first-level index blocks b 1 = ceiling(r 1 /bfr i )

= ceiling(1000/34) = 30 blocks

iii. We can calculate the number of levels as follows:

(g) i. For a B + -tree of order p, the following inequality must be satisfied for each

internal tree node: (p * P) + ((p – 1) * V SSN ) < B, or

(p * 6) + ((p – 1) * 9) < 512, which gives 15p < 521, so p=34

For leaf nodes, assuming that record pointers are included in the leaf nodes, the

following inequality must be satisfied: (p leaf * (V SSN +P R )) + P < B, or

(p leaf * (9+7)) + 6 < 512, which gives 16p leaf < 506, so p leaf =31

17.19 – A PARTS file with Part# as key field includes records with the following Part# values:

23, 65, 37, 60, 46, 92, 48, 71, 56, 59, 18, 21, 10, 74, 78, 15, 16, 20, 24, 28, 39, 43, 47, 50,

69, 75, 8, 49, 33, 38. Suppose the search field values are inserted in the given order in a B +

Chapter 17: Indexing Structures for Files

-tree of order p=4 and p leaf =3; show how the tree will expand and what the final tree looks

like.

Answer:

A B + -tree of order p=4 implies that each internal node in the tree (except possibly the root)

should have at least 2 keys (3 pointers) and at most 4 pointers. For p leaf =3, leaf nodes

must have at least 2 keys and at most 3 keys. The figure on page 50 shows how the tree

17.20: No solution provided.

17.21 – Suppose that the following search field values are deleted, in the given order, from

the B + –tree of Exercise 18.19, show how the tree will shrink and show the final tree. The

deleted values are: 65, 75, 43, 18, 20, 92, 59, 37.

Answer:

An important note about a deletion algorithm for a B + -tree is that deletion of a key value

from a leaf node will result in a reorganization of the tree if: (i) The leaf node is less

than half full; in this case, we will combine it with the next leaf node (other algorithms

combine it with either the next or the previous leaf nodes, or both), (ii) If the key value

internal node leading to the following tree:

Deleting 43 causes a leaf node to be less than half full, and it is combined with the next

node. Since the next node has 3 entries, its rightmost (first) entry 46 can replace 43 in

Chapter 17: Indexing Structures for Files

both the leaf and internal nodes, leading to the following tree:

Next, we delete 18, which is a rightmost entry in a leaf node and hence appears in an

internal node of the B + -tree. The leaf node is now less than half full, and is combined

with the next node. The value 18 must also be removed from the internal node, causing

underflow in the internal node. One approach for dealing with underflow in internal

nodes is to reorganize the values of the underflow node with its child nodes, so 21 is

moved up into the underflow node leading to the following tree:

Deleting 20 and 92 will not cause underflow. Deleting 59 causes underflow, and the

remaining value 60 is combined with the next leaf node. Hence, 60 is no longer a

Chapter 17: Indexing Structures for Files

Finally, removing 37 causes serious underflow, leding to a reorganization of the whole

tree. One approach to deleting the value in the root node is to use the rightmost value in

the next leaf node (the first leaf node in the right subtree) to replace the root, and move

this leaf node to the left subtree. In this case, the resulting tree may look as follows:

17.22 – 17.28: No solutions provided.