Databases Reference
In-Depth Information
Figure 2.2
Dynamic maintenance for a B+tree row insertion.
Insert cost for a single row (B+tree)
= search cost + rewrite data block + rewrite index block
= (
h
+ 1) + 1 + 1
=
h
+ 3 block accesses,
2.5
plus additional writes, if necessary, for splitting.
Occasionally, the split operation of an leaf index node necessitates a split of the next
higher index node as well, and in the worst case the split operations may cascade all the
way up to the index root node. The probability of additional splits depends on the type
of splitting algorithm and the dynamics of insertions and deletions in the workload.
Database statistics can be collected to determine these probabilities.
