of ( treewe must have at least nodes at depth at least nodes at depth and so on thusthe number of external nodes in is at least in additionby proposition the number of external nodes in is thereforewe obtain < < taking the logarithm in base of the terms for the above inequalitieswe get that <log( < hwhich justifies our claim (formula when terms are rearranged proposition states that the size and depth properties are sufficient for keeping multiway tree balanced moreoverthis proposition implies that performing search in ( tree takes (log ntime and that the specific realization of the secondary structures at the nodes is not crucial design choicesince the maximum number of children dmax is constant maintaining the size and depth properties requires some effort after performing insertions and deletions in ( treehowever we discuss these operations next insertion to insert new item (kv)with key kinto ( tree we first perform search for assuming that has no item with key kthis search terminates unsuccessfully at an external node let be the parent of we insert the new item into node and add new child (an external nodeto on the left of our insertion method preserves the depth propertysince we add new external node at the same level as existing external nodes neverthelessit may violate the size property indeedif node was previously -nodethen it would become -node after the insertionwhich causes the tree to no longer be ( tree this type of violation of the size property is called an overflow at node wand it must be resolved in order to restore the properties of ( tree let be the children of wand let be the keys stored at to remedy the overflow at node wwe perform split operation on as follows (see figure )replace with two nodes and where is -node with children storing keys and is -node with children storing key if is the root of create new root node uelselet be the parent of insert key into and make and children of uso that if was child of uthen and become children and of urespectively as consequence of split operation on node wa 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 we show sequence of insertions in ( tree in figure