Assume that you have just built a dense B+ tree containing100,000 records, with
ID: 670361 • Letter: A
Question
Assume that you have just built a dense B+ tree containing100,000 records, with one record per disk sector. The key field is a 20 byte string. Pointers (i.e. record ids) are 4 byte values. The size of one disk sector is 1024 bytes. The index was built in a bottom-up fashion using the bulk-loading algorithm and that the nodes at each level were filled up as much as possible. A node corresponds to a disk sector.
a. How many key/pointer pairs fit within a B+ node?
b. How many levels does the resulting tree have?
c. How many leaf nodes are used by the tree?
d. How many total nodes (root, internal, leaf) are required?
Explanation / Answer
Initially calculate tree order size
O=B+K/P+K
B=size of block, P=size of pointer, K=size of key, O=order of tree
=1024 + 20/20+4
=1044/24
=43.5
(b)
Maximum tree levels are calculated by following formula
= log[43] (100000/42)+1
= 2.067+1
=3.067
Therefore it has 3 maximum levels.
(a)
Average number of pointers = 0.69 x 43.5 = 30.015
for three levels...30*30*30 = 900 * 30 = 27000 pointers
(c)
Leaf node = 30*30*30
= 900 * 30
= 27000
(d)
Total node = Total Pointer +(0.69 * Order)
= 27000 +(0.69 * 43.5)
= 27000+30
= 27030