What is a Multi way tree A multi way or m way search tree of order m is a tree in which Each node has at most m subtrees where the subtrees may be empty Each node consists of at least 1 and at most m 1 distinct keys The keys in each node are sorted k1 k2 k3 km 2 km 1 T0 T1 T2 Tm 2 Tm 1 key k1 k1 key k2 k2 key k3 km 2 key km 1 key km 1 The keys and subtrees of a non leaf node are ordered as T0 k1 T1 k2 T2 km 1 Tm 1 such that All keys in subtree T0 are less than k1 All keys in subtree Ti 1 i m 2 are greater than ki but less than ki 1 All keys in subtree Tm 1 are greater than km 1 The node structure of a Multi way tree Note Corresponding to each key there is a data reference that refers to the data record for that key in secondary memory In our representations we will omit the data references The literature contains other node representations that we will not discuss 4000 keys n 5 At least 4000 5 1 nodes pages 1st level root 1 node 4 keys 5 sub trees 2nd level 5 nodes 20 keys 25 sub trees 3rd level 25 nodes 100 keys 125 sub trees 4th level 125 nodes 500 keys 525 sub trees 5th level 525 nodes 2100 keys 2625 subtress 6th level 2625 nodes 10500 keys tree height 6 including root E G M Petrakis B trees 3 Examples of Multi way Trees Note In a multiway tree The leaf nodes need not be at the same level A non leaf node with n keys may contain less than n 1 nonempty subtrees Operations on MSTs Search returns pointer to node containing the key and position of key in the node Insert new key if not already in the tree Delete existing key E G M Petrakis B trees 5 Insertions Search insert key it if not there a the tree grows at the leafs the tree becomes imbalanced not equal number of disk accesses for every key b the shape of the tree depends on the insertion sequence c low storage utilization many non full nodes E G M Petrakis B trees 6 insert 70 75 82 77 71 73 84 86 87 85 70 75 82 n 4 max 3 keys node B trees 7 70 75 82 n 4 max 3 keys node 70 75 82 77 E G M Petrakis B trees 8 insert 70 75 82 77 71 73 84 86 87 85 70 75 82 n 4 max 3 keys node 70 71 E G M Petrakis 75 73 82 77 B trees 9 insert 70 75 82 77 71 73 84 86 87 85 70 75 82 n 4 max 3 keys node 70 71 E G M Petrakis 75 73 82 77 84 B trees 86 87 10 insert 70 75 82 77 71 73 84 86 87 85 70 75 82 n 4 max 3 keys node 70 71 75 73 82 77 84 86 87 85 E G M Petrakis B trees 11 MST Deletions Find and delete a key from a node free the node if empty min value of right subtree or max value of left subtree If the key has right or and left sub trees find its successor or predecessor put this in the position of the key and delete the successor or predecessor The tree becomes imbalanced E G M Petrakis B trees 12 60 30 50 153 n 180 4 300 150 162 170 173 220 280 178 187 202 delete 150 180 E G M Petrakis B trees 13 60 30 50 162 n 180 4 300 153 170 173 220 280 178 187 202 delete 150 180 E G M Petrakis B trees 14 60 30 50 162 n 187 4 300 153 170 173 220 280 178 202 delete 150 180 E G M Petrakis B trees 15 What is a B Tree A B tree of order m or branching factor m where m 2 is either an empty tree or a multiway search tree with the following properties The root is either a leaf or it has at least two non empty subtrees and at most m non empty subtrees Each non leaf node other than the root has at least m 2 non empty subtrees and at most m non empty subtrees Note x is the lowest integer x The number of keys in each non leaf node is one less than the number of non empty subtrees for that node All leaf nodes are at the same level that is the tree is perfectly balanced What is a B tree cont d For a non empty B tree of order m This may be zero if the node is a leaf as well These will be zero if the node is a leaf as well Insertion in B Trees OVERFLOW CONDITION A root node or a non root node of a B tree of order m overflows if after a key insertion it contains m keys Insertion algorithm If a node overflows split it into two propagate the middle key to the parent of the node If the parent overflows the process propagates upward If the node has no parent create a new root node Note Insertion of a key always starts at a leaf node Deletion in B Tree Like insertion deletion must be on a leaf node If the key to be deleted is not in a leaf swap it with either its successor or predecessor each will be in a leaf The successor of a key k is the smallest key greater than k The predecessor of a key k is the largest key smaller than k IN A B TREE THE SUCCESSOR AND PREDECESSOR IF ANY OF ANY KEY IS IN A LEAF NODE Example Consider the following B tree of order 3 key predecessor successor 20 17 25 30 25 32 34 32 40 50 45 53 60 55 64 70 68 75 78 75 88 Deletion in B Tree UNDERFLOW CONDITION A non root node of a B tree of order m underflows if after a key deletion it contains m 2 2 keys The root node does not underflow If it contains only one key and this key is deleted the tree becomes empty Deletion in B Tree Deletion algorithm If a node underflows rotate the appropriate key from the adjacent rightor left sibling if the sibling contains at least m 2 keys otherwise perform a merging A key rotation must always be attempted before a merging There are five deletion cases 1 The leaf does not underflow 2 The leaf underflows and the adjacent right sibling has at least m 2 keys perform a left key rotation 3 The leaf underflows and the adjacent left sibling has at least m 2 keys perform a right key rotation 4 The leaf underflows and each of the adjacent …
View Full Document
Unlocking...