# 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?

Answer.

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

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?

Answer.

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

You'll get a 325.6KB .ZIP file.