The number of disk accesses performed by an insertion operation in a B-tree of…

Concept — in a B-tree the unit of work is the disk block: each node is stored in exactly one block, so bringing a node in or writing it back costs one disk access. The cost of a B-tree operation is therefore counted as the number of NODES it must touch, not the number of key comparisons it makes — comparisons happen in main memory once the block is resident and are not charged. Any operation that walks from the root down to a leaf must touch one node per level, so its disk-access count is proportional to the number of levels, that is, to the height h.

Applying this to insertion

1. Descend. Insertion starts at the root and moves down one node per level until it reaches the leaf that must receive the new key. That descent brings in at most h + 1 nodes, one per level, so it costs O(h) disk reads.

2. Split proactively. The standard B-TREE-INSERT does not wait to discover an overflow on the way back up; whenever the descent meets a node that is already full (2t − 1 keys for minimum degree t), it splits that node immediately. A split writes the full node, its new sibling, and its parent — and the parent is already in memory from the previous level — so one split costs O(1) disk writes.

3. Count the splits. Because the descent visits each level once, at most one split can occur per level, so every split performed during a single insertion adds at most O(h) writes in total. Proactive splitting also removes the need for a second, upward pass.

4. Add the two parts. O(h) reads on the way down plus O(h) writes for the splits gives O(h) + O(h) = O(h) disk accesses for the whole insertion.

Cross-check

• The CPU time is a separate quantity: each visited node costs O(t) in-memory comparisons for minimum degree t, so the CPU cost is O(t·h). Keeping the two counts apart — O(h) accesses, O(t·h) time — is exactly the point of the B-tree analysis, since the disk access is the expensive operation.

• Because a B-tree with n keys and minimum degree t has height h ≤ logt ((n + 1) / 2), the same count is often quoted as O(logt n). Expressed in terms of h itself it is linear in h, and deletion and search have the same O(h) disk-access bound.

• A logarithmic-in-h count would require each access to remove a constant fraction of the remaining depth, but a root-to-leaf descent can only step down one level per node it reads. A constant count would require insertion to reach a leaf without touching the levels above it, which is impossible in a tree whose height grows with n.