Notes

14.2.7 Efficiency of B-Trees
B-trees allow lookup, insertion, and deletion of records using very few disk I/O ’s
per file operation. First, we should observe that if n, the number of keys per
block, is reasonably large, then splitting and merging of blocks will be rare
events. Further, when such an operation is needed, it almost always is limited
to the leaves, so only two leaves and their parent are affected. Thus, we can
essentially neglect the disk-I/O cost of B-tree reorganizations.
However, every search for the record(s) with a given search key requires us
to go from the root down to a leaf, to find a pointer to the record. Since we
are only reading B-tree blocks, the number of disk I/O ’s will be the number
of levels the B-tree has, plus the one (for lookup) or two (for insert or delete)
disk I/O ’s needed for manipulation of the record itself. We must thus ask:
how many levels does a B-tree have? For the typical sizes of keys, pointers,
and blocks, three levels are sufficient for all but the largest databases. Thus,
we shall generally take 3 as the number of levels of a B-tree. The following
example illustrates why.