DOC PREVIEW
UMBC CMSC 341 - B- Trees

This preview shows page 1-2-15-16-17-32-33 out of 33 pages.

Save
View full document
Premium Document
Do you want full access? Go Premium and unlock all 33 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC 341 B Trees D Frey with apologies to Tom Anastasio Large 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 memory 8 3 2007 UMBC CMSC 341 BTrees 2 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 8 3 2007 UMBC CMSC 341 BTrees 3 20 40 12 8 1 2 5 7 17 9 10 12 15 33 18 19 27 29 20 45 33 37 40 41 45 Figure 1 A BST with data stored in the leaves 8 3 2007 UMBC CMSC 341 BTrees 4 Observations 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 leaf 8 3 2007 UMBC CMSC 341 BTrees 5 M 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 Mway 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 leaves 8 3 2007 UMBC CMSC 341 BTrees 6 An M Way Tree of Order 3 Figure 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 2007 UMBC CMSC 341 BTrees 7 5 1 2 4 9 5 7 10 11 12 12 20 15 18 15 16 26 18 19 21 24 27 30 34 42 Figure 2 An M Way tree of order 3 8 3 2007 UMBC CMSC 341 BTrees 8 Searching 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 increases 8 3 2007 UMBC CMSC 341 BTrees 9 Searching an M Way Tree Search MWayNode v DataType element boolean foundIt if v NULL return failure if v is a leaf search the list of values looking for element if found return success otherwise return failure else if v is an interior node search the keys to find which subtree element is in recursively search the subtree For real code see Dr Anastasio s postscript notes 8 3 2007 UMBC CMSC 341 BTrees 10 Search Algorithm Traversing the M way Tree Everything in this subtree is smaller than this key 10 1 2 9 32 22 28 13 18 10 11 13 14 16 18 23 24 25 39 28 30 32 35 38 39 44 In 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 2007 UMBC CMSC 341 BTrees 11 22 6 2 4 12 18 6 14 8 16 10 26 32 18 22 26 32 19 24 28 34 20 30 36 48 42 54 38 42 40 44 46 48 54 50 56 52 Figure 3 searching in an M way tree of order 4 8 3 2007 UMBC CMSC 341 BTrees 12 Is 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 2007 UMBC CMSC 341 BTrees 13 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 8 3 2007 UMBC CMSC 341 BTrees 14 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 8 3 2007 UMBC CMSC 341 BTrees 15 A Generic M Way Tree Node public class MWayNode code for public interface here constructors accessors mutators private private private private private private private boolean isLeaf int m int nKeys ArrayList Ktype keys MWayNode subtrees int nElems List Dtype data true if node is a leaf the order of the node nr of actual keys used array of keys size m 1 array of pts size m nr poss elements in leaf data storage if leaf 8 3 2007 UMBC CMSC 341 BTrees 16 B Tree Definition A B Tree of order M is an M Way tree with the following constraints 1 2 3 8 3 2007 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 UMBC CMSC 341 BTrees 17 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 …


View Full Document

UMBC CMSC 341 - B- Trees

Download B- Trees
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view B- Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view B- Trees and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?