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.

Question

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.

Answer 1

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
ii. Assuming that nodes are 69% full on the average, the average number of key
values in a leaf node is 0.69*p leaf = 0.69*31 = 21.39. If we round this up for
convenience, we get 22 key values (and 22 record pointers) per leaf node. Since the
file has 30000 records and hence 30000 values of SSN, the number of leaf-level
nodes (blocks) needed is b 1 = ceiling(30000/22) = 1364 blocks
iii. We can calculate the number of levels as follows:
The average fan-out for the internal nodes (rounded up for convenience) is
fo = ceiling(0.69*p) = ceiling(0.69*34) = ceiling(23.46) = 24
number of second-level tree blocks b 2 = ceiling(b 1 /fo) = ceiling(1364/24)
= 57 blocks
number of third-level tree blocks b 3 = ceiling(b 2 /fo) = ceiling(57/24)= 3
number of fourth-level tree blocks b 4 = ceiling(b 3 /fo) = ceiling(3/24) = 1
Since the fourth level has only one block, the tree has x = 4 levels (counting the
leaf level). Note: We could use the formula:
x = ceiling(log fo (b 1 )) + 1 = ceiling(log 24 1364) + 1 = 3 + 1 = 4 levels
iv. total number of blocks for the tree b i = b 1 + b 2 + b 3 + b 4
= 1364 + 57 + 3 + 1 = 1425 blocks
v. number of block accesses to search for a record = x + 1 = 4 + 1 = 5