CMSC 341Large TreeTextbook ErrorsAn alternative to BSTsSlide 5ObservationsM-Way TreesAn M-way tree of order 3Slide 9Searching in an M-way treeSearching an M-way treeSlide 12Slide 13Is it worth it?An exampleHow can this be worth the price?A generic M-Way Tree NodeB-Tree DefinitionA B-Tree exampleSlide 20Designing a B-TreeStudent Record ExampleCalculating LCalculating MPerformance of our B-TreeInsertion of X in a B-TreeInsert 33 into this B-TreeInserting 33Slide 29Now insert 35Slide 31Inserting 21Slide 33Slide 34CMSC 341B- TreesD. Frey with apologies to Tom AnastasioLarge Tree•Tailored toward applications where tree doesn’t fit in memory–operations much faster than disk accesses–want to limit levels of tree (because each new level requires a disk access)–keep root and top level in memoryTextbook Errors•Please check the textbook web page for typos and other errors.•In particular, the section on B-Trees (4.7) has a couple of typos (pages 166 and 167)•Page 166 – numbered item 5 right margin should be “…and L data items…”, not “…L children...”•Page 167 – ½ way down, left margin, change “and the first level” to “and the next level”An alternative to BSTs•Up until now we assumed that each node in a BST stored the data.•What about having the data stored only in the leaves? The internal nodes just guide our search to the leaf which contains the data we want.•We’ll restrict this discussion of such trees to those in which all leaves are at the same level.1071694 14 194 71 9 14 1610 19Figure 1 - A BST with data stored in the leavesObservations•Store data only at leaves; all leaves at same level–interior and exterior nodes have different structure–interior nodes store one key and two subtree pointers–all search paths have same length: lg n–can store multiple data elements in a leafM-Way Trees•A generalization of the previous BST model–each interior node has M subtrees pointers and M-1 keys•the previous BST would be called a “2-way tree” or “M-way tree of order 2”–as M increases, height decreases: lgM n–perfect M-way tree of height h has Mh leavesAn M-way tree of order 3Figure 2 (next page) shows the same data as figure 1, stored in an M-way tree of order 3. In this example M = 3 and h = 2, so the tree can support 9 leaves, although it contains only 8.One way to look at the reduced path length with increasing M is that the number of nodes to be visited in searching for a leaf is smaller for large M. We’ll see that when data is stored on the disk, each node visited requires a disk access, so reducing the nodes visited is essential.4 71 9 14 1610 199 164 7 10 14 19Figure 2 -- An M-Way tree of order 3Searching in an M-way tree•Different from standard BST search–search always terminates at a leaf node–might need to scan more than one element at a leaf–might need to scan more than one key at an interior node•Trade-offs–tree height decreases as M increases–computation at each node during search increases as M increasesSearching an M-way treeSearch (MWayNode *v, DataType element, bool& foundIt)if v == NULL return failureif v is a leafsearch the list of values looking for elementif found, return success otherwise return failure else if v is an interior nodesearch the keys to find which subtree element is inrecursively search the subtree•For “real” code, see Dr. Anastasio’s postscript notes4 71 9 14 1610 199 164 7 10 14 19Search Algorithm: Traversing the M-way TreeEverything in this subtree is smaller than this keyIn any interior node, find the first key > search item, and traverse the link to the left of that key. Search for any item >= the last key in the subtree pointed to by the rightmost link. Continue until search reaches a leaf.22 36 486 12 18 26 32 42 54246810121416181920222426283032343638404244464850525456Figure 3 – searching in an M-way tree of order 4Is it worth it?•Is it worthwhile to reduce the height of the search tree by letting M increase?•Although the number of nodes visited decreases, the amount of computation at each node increases.•Where’s the payoff?An example•Consider storing 107 items in a balanced BST and in an M-way tree of order 10.•The height of the BST will be lg(107) ~ 24.•The height of the M-Way tree will be log(107 ) = 7 (assuming that we store just 1 record per leaf)•However, in the BST, just one comparison will be done at each interior node, but in the M-Way tree, 9 will be done (worst case)How can this be worth the price?•Only if it somehow takes longer to descend the tree than it does to do the extra computation•This is exactly the situation when the nodes are stored externally (e.g. on disk)•Compared to disk access time, the time for extra computation is insignificant•We can reduce the number of accesses by sizing the M-way tree to match the disk block and record size. See Weiss text, section 4.7, page 165 for an example.A generic M-Way Tree Nodetemplate <class Ktype, class Dtype>class MWayNode{public:// constructors, destructor, accessors, mutatorsprivate:bool isLeaf; // true if node is a leafint m; // the “order” of the nodeint nKeys; // nr of actual keys usedKtype *keys; // array of keys (size = m - 1)MWayNode *subtrees; // array of pts (size = m)int nElems; // nr possible elements in leafList<Dtype> data; // data storage if leaf};B-Tree DefinitionA B-Tree of order M is an M-Way tree with the following constraints–The root is either a leaf or has between 2 and M subtrees–All interior node (except maybe the root) have between  M / 2 and M subtrees (I.e. each interior node is at least “half full”–All leaves are at the same level. A leaf must store between L / 2 and L data elements, where L is a fixed constant >= 1 (I.e. each leaf is at least half full,except when the tree has fewer than L/2 elements)A B-Tree example•The following figure (also figure 3) shows a B-Tree with M = 4 and L = 3•The root node can have between 2 and M=4 subtrees•Each other interior node can have between  M / 2 =  4 / 2 = 2 and M = 4 subtrees and up to M – 1 = 3 keys.•Each exterior node (leaf) can hold between  L / 2 =  3 / 2 = 2 and L = 3 data elements22 36 486 12 18 26 32 42 54246810121416181920222426283032343638404244464850525456Figure 4 – A B-Tree with M = 4 and L = 3Designing a B-Tree•Recall that M-way trees (and therefore B-trees) are often used when there is too much