# B-Tree nodes

1. (4 pt) Suppose we have B-tree nodes with room for three keys and four pointers, as in the
examples of this section. Suppose also that when we split a leaf, we divide the pointers 2 and 2,
while when we split an interior node, the first 3 pointers go with the first (left) node, and the last
2 pointers go with the second (right) node. We start with a leaf containing pointers to records
with keys 1, 2, and 3. Then add in order, records with keys 4, 5, 6, and so on. At the insertion of
what key will the B-tree first reach four levels?
Draw the final tree.
Answer. Since we are always adding at the right extreme of the B-tree, once split, the first (left)
of the pair never changes. Thus, the leaf blocks will each have two keys only: (1,2), (3,4), (5,6),
and so on.
At the second level, we divide pointers 3 to the left, and 2 to the right, so each except the
rightmost node at that level has three pointers; the leftmost has two. The same holds for any
other level.
Thus, when we first get four levels, the root has two pointers. At the third level, there are blocks
with 3 and 2 pointers, respectively. At the second level, there are five blocks, with 3, 3, 3, 3, and
2 pointers. These 14 pointers go to leaf blocks with two pointers each, for a total of 28 pointers
to records.
Thus, when the record with key 28 is inserted, the 4th level is created.
2. (3 pt)
Redo the example in slides titled “Attempt at using B-trees for MD-queries” under the
assumption that the range query asks for a square in the middle that is 𝑛 𝑥 𝑛 for some n between
1 and 1000. How many disk I/O's are needed? For which values of n do indexes help?
We obtain 1,000,000/(1000/n) pointers to follow from each index.
Doing pointer intersection, we obtain 1,000,000/((1000/n)*(1000/n)) pointers to finally follow,
i.e. we need that many I/Os once we obtain the pointers.
Now, what is the number of I/Os for obtaining the pointers from each index?
We need to traverse 2*(1,000,000/(1000/n)) /200 leaves (blocks) +2 (for intermediate B-tree
level).
Total: 1,000,000/((1000/n)*(1000/n)) + 2*(1,000,000/(1000/n))/200 +2
For this number to be less or equal to the number of blocks of the relation, 10,000, we need to
solve:
1,000,000/((1000/n)*(1000/n)) + 2*(1,000,000/(1000/n))/200 +2 = 10,000
n^2 + 10n + 2 = 10,000
n= 95, i.e. n<=95 in order to be beneficial to use the two B-Tree indexes.
https://www.coursehero.com/file/23287669/assign2-sol/
This study resource was
shared via CourseHero.com