stored at such nodes thusit can be implemented to run in ( time as consequence of split operation on node va new overflow may occur at the parent of if such an overflow occursit triggers in turn split at node (see figure split operation either eliminates the overflow or propagates it into the parent of the current node hencethe number of split operations is bounded by the height of the treewhich is (lognby proposition thereforethe total time to perform an insertion in ( , tree is (lognfigure an insertion in ( , tree that causes cascading split(abefore the insertion(binsertion of causing an overflow(ca split(dafter the split new overflow occurs(eanother splitcreating new root node(ffinal tree removal