chap indexing figure breaking the bst into blocks the bst is divided among disk blockseach with space for three nodes the path from the root to any leaf is contained on two blocks ( (bfigure an attempt to re-balance bst after insertion can be expensive (aa bst with six nodes in the shape of complete binary tree (ba node with value is inserted into the bst of (ato maintain both the complete binary tree shape and the bst propertya major reorganization of the tree is required it naturally leads to the -tree of section which is by far the most widely used indexing method today - trees this section presents data structure called the - tree the - tree is not binary treebut instead its shape obeys the following definition node contains one or two keys every internal node has either two children (if it contains one keyor three children (if it contains two keyshence the name all leaves are at the same level in the treeso the tree is always height balanced in addition to these shape propertiesthe - tree has search tree property analogous to that of bst for every nodethe values of all descendants in the left subtree are less than the value of the first keywhile values in the center subtree