Consider a disk with block size B 512 bytes A block pointer

Consider a disk with block size B = 512 bytes. A block pointer is P = 6 bytes long, and a record pointer is PR = 7 bytes long. A file has r = 80,000 EMPLOYEE records of fixed length. Each record has the following fields: NAME (25 bytes), SSN (9 bytes), DEPARTMENTCODE (9 bytes), ADDRESS (40 bytes), PHONE (8 bytes), BIRTHDATE (8 bytes), SEX (1 byte), JOBCODE (4 bytes), SALARY (4 bytes).

Q: You are building a primary index on SSN using B+ tree. Calculate (i) the order p for the B+ tree, (ii) the number of levels needed if blocks are approximately 69% full (round up for convenience), and (iii) the worst-case number of blocks needed to search for and retrieve a record from the file—given its SSN value—using the B+ tree you are estimating.

Solution

(i) The order p for the B+ tree,

for each internal tree node,the following inequality must be satisfied

  (p * P) + ((p - 1) * V SSN ) < B, or (p * 6) + ((p - 1) * 9) < 512,

implies 15p < 521

so p=34

for leaf nodes,

(p leaf * (V SSN +P R )) + P < B, or (p leaf * (9+7)) + 6 < 512,

which gives 16p leaf < 506,

so this implies p =31

(ii) If blocks are approximately 69% full,

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 record pointers per leaf node.

Since the file has 30000 records and hence 30000 values of SSN,

( ceiling(30000/22)

the number of levels needed is 1364 blocks

(iii)  number of block accesses to search for a record is x + 1,where x is number of levels.

So to find x,

The average fan-out for the internal nodes = ceiling(0.69*p) = ceiling(0.69*34) = ceiling(23.46) = 24

number of second-level tree blocks = ceiling(b 1 /fo) = ceiling(1364/24) = 57 blocks

number of third-level tree blocks = 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

So,number of block accesses to search for a record = x + 1 = 4 + 1 = 5