B -Tree File Organization

1. The B -tree structure is used not only as an index but also as an organizer for records into a file.
2. In a B -tree file organization, the leaf nodes of the tree store records instead of storing pointers to records, as shown in Fig. 11.17.
3. Since records are usually larger than pointers, the maximum number of records that can be stored in a leaf node is less than the maximum number of pointers in a nonleaf node.
4. However, the leaf node are still required to be at least half full.
5. Insertion and deletion from a B -tree file organization are handled in the same way as that in a B -tree index.
6. When a B -tree is used for file organization, space utilization is particularly important. We can improve the space utilization by involving more sibling nodes in redistribution during splits and merges.
7. In general, if m nodes are involved in redistribution, each node can be guaranteed to contain at least entries. However, the cost of update becomes higher as more siblings are involved in redistribution.