Question

We want to build an optimal B-tree with the following assumptions: a) the block size of a disk is 4,096 bytes, b) Branches use 4 bytes, c) Keys use 16 bytes, c) The records (including the keys) are 128 bytes, d) There are 16m records.

Answer 1

Answer: For the optimal B-tree to be built, we select t so that a full node uses as much of a disk block as possible. In a full

node there are 2t−1 keys (4 bytes each), 2t−1 data record references (8 bytes each), 2t child

pointers (4 bytes each), a parent pointer (4 bytes), the number of keys (4 bytes) and the leaf

bit (which we’ll go ahead and assume takes 4 bytes though 1 bit would do). Hence we want to

pick t as large as we can so that 12(2t−1)+ 4(2t)+ 12 = 32t ≤ 4096. Solving for t yields that

we need t = 128. In class, we argued that the number of disk pages that must be read (d-1

using the notation from class) is at most logt(n + 1)/2. Since log128(n + 1)/2 = log128 ≈ 2.7

the number of levels below the root must be an integer, during a search at most 2 disk pages will need

to be brought into main memory.