CMSC 341Large TreesAn Alternative to BSTsSlide 4ObservationsM-Way TreesAn M-Way Tree of Order 3Slide 8Searching in an M-Way TreeSearching an M-Way TreeSlide 11Slide 12Is it worth it?An exampleHow can this be worth the price?A Generic M-Way Tree NodeB-Tree DefinitionA B-Tree exampleSlide 19Designing a B-TreeStudent Record ExampleCalculating LCalculating MPerformance of our B-TreeInsertion of X in a B-TreeInsert 33 into this B-TreeInserting 33Slide 28Now insert 35Slide 30Inserting 21Slide 32Slide 33CMSC 341B- TreesD. Frey with apologies to Tom Anastasio8/3/2007UMBC CMSC 341 BTrees2Large Trees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 memory8/3/2007UMBC CMSC 341 BTrees3An 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.8/3/2007UMBC CMSC 341 BTrees4201240178 33 459101215125718193337404127292045Figure 1 - A BST with data stored in the leaves8/3/2007UMBC CMSC 341 BTrees5Observations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(assuming one element per leaf)can store multiple data elements in a leaf8/3/2007UMBC CMSC 341 BTrees6M-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 (assuming one element per leaf)A perfect M-way tree of height h has Mh leaves8/3/2007UMBC CMSC 341 BTrees7An 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.8/3/2007UMBC CMSC 341 BTrees8571011124121819212415162730344212 205 9 15 18 26Figure 2 -- An M-Way tree of order 38/3/2007UMBC CMSC 341 BTrees9Searching 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 increases8/3/2007UMBC CMSC 341 BTrees10Searching an M-Way TreeSearch (MWayNode v, DataType element, boolean foundIt)if (v == NULL) return failure;if (v is a leaf)search the list of values looking for elementif found, return success otherwise return failure else (if v is an interior node)search the keys to find which subtree element is inrecursively search the subtreeFor “real” code, see Dr. Anastasio’s postscript notes8/3/2007UMBC CMSC 341 BTrees111011131416129182830323538232425394418 3210 13 22 28 39Search 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.8/3/2007UMBC CMSC 341 BTrees1222 36 486 12 18 26 32 42 5424681014161819202224262830323438404244464850525456Figure 3 – searching in an M-way tree of order 48/3/2007UMBC CMSC 341 BTrees13Is 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?8/3/2007UMBC CMSC 341 BTrees14An 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)8/3/2007UMBC CMSC 341 BTrees15How 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.8/3/2007UMBC CMSC 341 BTrees16A Generic M-Way Tree Nodepublic class MWayNode{ // code for public interface here // constructors, accessors, mutatorsprivate boolean isLeaf; // true if node is a leafprivate int m; // the “order” of the nodeprivate int nKeys; // nr of actual keys usedprivate ArrayList<Ktype> keys; // array of keys(size = m - 1)private MWayNode subtrees[ ]; // array of pts (size = m)private int nElems; // nr poss. elements in leafprivate List<Dtype> data; // data storage if leaf}8/3/2007UMBC CMSC 341 BTrees17B-Tree DefinitionA B-Tree of order M is an M-Way tree with the following constraints1. The root is either a leaf or has between 2 and M subtrees2. All interior node (except maybe the root) have between M / 2 and M subtrees (i.e. each interior node is at least “half full”)3. 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)8/3/2007UMBC CMSC 341 BTrees18A 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