Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
The running time of the downward pass of the insertion algorithm is identical to that of an unsuccessful search (assuming the item to be inserted is not already in the tree). I.e., for a B-tree of height h, the worst-case running time of the downward pass is
The second pass of the insertion algorithm does the insertion
and balances the tree if necessary.
In the worst case,
all of the nodes in the insertion path up to the root need to be balanced.
Each time the InsertPair routine is invoked,
it calls FindIndex which has running time
in the worst case.
The additional time required to balance a node is O(M).
Therefore, the worst-case running time of the upward pass is
Therefore, the total running time for insertion is
According to Theorem 
,
the height of a B-tree is 
,
where n is the number of keys in the B-tree.
If we assume that two keys can be compared in constant time,
i.e., 
,
then the running time for insertion in a B-tree is simply 
.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.