Next: B-Tree Index Files
Up: B-Tree Index Files
Previous: Updates on B-Trees
The B -tree structure is used not only as an index but also as an organizer
for records into a file.
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.
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.
However, the leaf node are still required to be at least half full.
Insertion and deletion from a B -tree file organization are handled in
the same way as that in a B -tree index.
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.
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
Mon Jul 13 13:28:03 PDT 1998