fig node insertion in bb-tree remember that -trees have the characteristic of growing from the bottom toward the root and that the property of all leafs being at the same level must be maintained the simplest case ( is when the right subtree of node grows and when is the only key on its (hypotheticalpage thenthe descendant merely becomes the sibling of ai the vertical pointer becomes horizontal pointer this simple raising of the right arm is not possible if already has sibling then we would obtain page with nodesand we have to split it (case its middle node is passed up to the next higher level now assume that the left subtree of node has grown in height if is again alone on page (case ) its right pointer refers to descendantthen the left subtree (ais allowed to become ' sibling ( simple rotation of pointers is necessary since the left pointer cannot be horizontalifhoweverb already has siblingthe raising of yields page with three membersrequiring split this split is realized in very straightforward mannerc becomes descendant of bwhich is raised to the next higher level (case it should be noted that upon searching keyit makes no effective difference whether we proceed along horizontal or vertical pointer it therefore appears artificial to worry about left pointer in case becoming horizontalalthough its page still contains not more than two members indeedthe insertion algorithm reveals strange asymmetry in handling the growth of left and right subtreesand it lets the bbtree organization appear rather artificial there is no proof of strangeness of this organizationyet healthy intuition tells us that something is fishyand that we should remove this asymmetry it leads to the notion of the symmetric binary -tree (sbb-treewhich was also investigated by bayer [ - in on the average it leads to slightly more efficient search treesbut the algorithms for insertion and deletion are also slightly more complex furthermoreeach node now requires two bits (boolean variable lh and rhto indicate the nature of its two pointers since we will restrict our detail considerations to the problem of insertionwe have once again to distinguish among four cases of grown subtrees they are illustrated in fig which makes the gained symmetry evident note that whenever subtree of node without siblings growsthe root of the subtree becomes the sibling of this case need not be considered any further the four cases considered in fig all reflect the occurrence of page overflow and the subsequent page split they are labelled according to the directions of the horizontal pointers linking the three siblings in the middle figures the initial situation is shown in the left columnthe middle column illustrates the fact that the lower node has been raised as its subtree has grownthe figures in the right column show the result of node rearrangement