14.9

The leaf nodes of a B+-tree file organization may lose sequentiality after a sequence of inserts.

1. Explain why sequentiality may be lost.

2. To minimize the number of seeks in a sequential scan, many databases allocate leaf pages in extents of $n$ blocks, for some reasonably large $n$. When the first leaf of a B+-tree is allocated, only one block of an $n$-block unit is used, and the remaining pages are free. If a page splits, and its $n$-block unit has a free page, that space is used for the new page. If the $n$-block unit is full, another $n$-block unit is allocated, and the first $n/2$ leaf pages are placed in one $n$-block unit and the remaining one in the second $n$-block unit. For simplicity, assume that there are no delete operations.

3. What is the worst-case occupancy of allocated space, assuming no delete operations, after the first $n$-block unit is full?

2. Is it possible that leaf nodes allocated to an $n$-node block unit are not consecutive, that is, is it possible that two leaf nodes are allocated to one $n$-node block, but another leaf node in between the two is allocated to a different $n$-node block?

3. Under the reasonable assumption that buffer space is sufficient to store an $n$-page block, how many seeks would be required for a leaf level scan of the B+-tree, in the worst case? Compare this number with the worst case if leaf pages are allocated a block at a time.

4. The technique of redistributing values to siblings to improve space utilization is likely to be more efficient when used with the preceding allocation scheme for leaf blocks. Explain why.

---

1. Explain why sequentiality may be lost.

In a B+-tree index or file organization, leaf nodes that are adjacent to each other in the tree may be located at different places on disk. When a file organization is newly created on a set of records, it is possible to allocate blocks that are mostly contiguous on disk to leaf nodes that are contiguous in the tree. As insertions and deletions occur on the tree, sequentiality is increasingly lost, and sequential access has to wait for disk seeks increasingly often.

2. To minimize the number of seeks in a sequential scan, many databases allocate leaf pages in extents of $n$ blocks, for some reasonably large $n$. When the first leaf of a B+-tree is allocated, only one block of an $n$-block unit is used, and the remaining pages are free. If a page splits, and its $n$-block unit has a free page, that space is used for the new page. If the $n$-block unit is full, another $n$-block unit is allocated, and the first $n/2$ leaf pages are placed in one $n$-block unit and the remaining one in the second $n$-block unit. For simplicity, assume that there are no delete operations.

3. What is the worst-case occupancy of allocated space, assuming no delete operations, after the first $n$-block unit is full?

In the worst case, each $n$-block unit and each node of the B+-tree is half filled. This gives the worst-case occupancy as 25 percent.

2. Is it possible that leaf nodes allocated to an $n$-node block unit are not consecutive, that is, is it possible that two leaf nodes are allocated to one $n$-node block, but another leaf node in between the two is allocated to a different $n$-node block?

No. While splitting the $n$-block unit, the first $n/2$ leaf pages are placed in one $n$-block unit and the remaining pages in the second $n$-block unit. That is, every $n$-block split maintains the order. Hence, the nodes in the $n$-block unit are consecutive.

3. Under the reasonable assumption that buffer space is sufficient to store an $n$-page block, how many seeks would be required for a leaf level scan of the B+-tree, in the worst case? Compare this number with the worst case if leaf pages are allocated a block at a time.

In the regular B+-tree construction, the leaf pages might not be sequential and hence in the worst-case, it takes one seek per leaf page. Using the block at a time method, for each $n$-node block, we will have at least $n/2$ leaf nodes in it. Each $n$-node block can be read using one seek. Hence the worst-case seeks come down by a factor of $n/2$.

4. The technique of redistributing values to siblings to improve space utilization is likely to be more efficient when used with the preceding allocation scheme for leaf blocks. Explain why.

Allowing redistribution among the nodes of the same $n$-block unit does not require additional seeks, whereas in regular B+-trees we require as many seeks as the number of leaf pages involved in the redistribution. This makes redistribution for leaf blocks efficient with this scheme. Also, the worst-case occupancy comes back to nearly 50 percent. (Splitting of leaf nodes is preferred when the participating leaf nodes are nearly full. Hence nearly 50 percent instead of exact 50 percent.)