Indexing with 2-3 Trees: A Shallow Tree Strategy for Efficient Record Management, Study notes of Data Structures and Algorithms

Download Indexing with 2-3 Trees: A Shallow Tree Strategy for Efficient Record Management and more Study notes Data Structures and Algorithms in PDF only on Docsity! Data Structures and Algorithms Indexing Chris Brooks Department of Computer Science University of San Francisco Department of Computer Science — University of San Francisco – p.1/108 17-0: Indexing Often, when managing records, we want to do more than just find a record that matches a particular key. Find all records in a range, in order. Sort by one of several keys Also, records may not all fit into memory Department of Computer Science — University of San Francisco – p.2/108 17-3: Storing Records on Disk So far, we’ve assumed our entire data structure can fit into main memory. What if it’s too large? Need to minimize the number of disk accesses Speaking practically, reading from the disk is much slower than reading from memory RAM: 50 nanoseconds disk: 5 milliseconds (100,000 times slower) Strategies Keep tree as shallow as possible Store records with adjacent keys in adjacent blocks on disk Department of Computer Science — University of San Francisco – p.5/108 17-4: 2-3 Trees A 2-3 tree is a generalized Binary Search Tree Not typically implemented, but a good intro Each node has 1 or 2 keys Each (non-leaf) node has 2-3 children hence the name, 2-3 Trees All leaves are at the same depth Department of Computer Science — University of San Francisco – p.6/108 17-5: Example 2-3 Tree 6 16 3 8 13 18 7 11 12 14 17 202 5 Department of Computer Science — University of San Francisco – p.7/108 17-8: Inserting into 2-3 Trees Always insert at the leaves To insert an element: Find the leaf where the element would live, if it was in the tree Add the element to that leaf Department of Computer Science — University of San Francisco – p.10/108 17-9: Inserting into 2-3 Trees Always insert at the leaves To insert an element: Find the leaf where the element would live, if it was in the tree Add the element to that leaf What if the leaf already has 2 elements? Department of Computer Science — University of San Francisco – p.11/108 17-10: Inserting into 2-3 Trees Always insert at the leaves To insert an element: Find the leaf where the element would live, if it was in the tree Add the element to that leaf What if the leaf already has 2 elements? Split! Department of Computer Science — University of San Francisco – p.12/108 17-13: Splitting Nodes 4 1 2 5 6 7 Promote to parent Left child of 6 Right child of 6 Department of Computer Science — University of San Francisco – p.15/108 17-14: Splitting Nodes 4 6 1 2 5 7 Department of Computer Science — University of San Francisco – p.16/108 17-15: Splitting Root When we split the root: Create a new root Tree grows in height by 1 Department of Computer Science — University of San Francisco – p.17/108 17-18: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 2 3 Too many keys, need to split Department of Computer Science — University of San Francisco – p.20/108 17-19: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 2 3 Department of Computer Science — University of San Francisco – p.21/108 17-20: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 2 3 4 Department of Computer Science — University of San Francisco – p.22/108 17-23: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 2 4 3 5 6 Department of Computer Science — University of San Francisco – p.25/108 17-24: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 2 4 3 5 6 7 Too many keys need to split Department of Computer Science — University of San Francisco – p.26/108 17-25: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 2 4 6 3 5 7 Too many keys need to split Department of Computer Science — University of San Francisco – p.27/108 17-28: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 3 5 7 8 9 4 2 6 Too many keys need to split Department of Computer Science — University of San Francisco – p.30/108 17-29: 2-3 Tree Example Inserting elements 1-9 (in order) into a 2-3 tree 1 3 5 4 2 6 8 7 9 Department of Computer Science — University of San Francisco – p.31/108 17-30: Deleting from 2-3 Tree As with BSTs, we will have 2 cases: Deleting a key from a leaf Deleting a key from an internal node Department of Computer Science — University of San Francisco – p.32/108 17-33: Deleting Leaves 4 8 3 5 11 Deleting 7 Department of Computer Science — University of San Francisco – p.35/108 17-34: Deleting Leaves If leaf contains 1 key Cannot remove key without making leaf empty Try to steal extra key from sibling Department of Computer Science — University of San Francisco – p.36/108 17-35: Deleting Leaves 4 8 3 5 7 11 Deleting 3 – we can steal the 5 Department of Computer Science — University of San Francisco – p.37/108 17-38: Deleting Leaves 5 8 7 114 Steal key from sibling through parent Department of Computer Science — University of San Francisco – p.40/108 17-39: Deleting Leaves If leaf contains 1 key, and no sibling contains extra keys Cannot remove key without making leaf empty Cannot steal a key from a sibling Merge with sibling split in reverse Department of Computer Science — University of San Francisco – p.41/108 17-40: Merging Nodes 5 8 7 114 Removing the 4 Department of Computer Science — University of San Francisco – p.42/108 17-43: Merging Nodes Merge decreases the number of keys in the parent May cause parent to have too few keys Parent can steal a key, or merge again Department of Computer Science — University of San Francisco – p.45/108 17-44: Merging Nodes 1 3 5 4 2 6 8 7 9 Deleting the 3 – cause a merge Department of Computer Science — University of San Francisco – p.46/108 17-45: Merging Nodes 1 2 5 4 6 8 7 9 Deleting the 3 – cause a merge Not enough keys in parent Department of Computer Science — University of San Francisco – p.47/108 17-48: Merging Nodes 1 2 5 6 8 7 9 4 When we steal a key from an internal node, steal nearest subtree as well Department of Computer Science — University of San Francisco – p.50/108 17-49: Merging Nodes 1 2 5 6 8 7 9 4 When we steal a key from an internal node, steal nearest subtree as well Department of Computer Science — University of San Francisco – p.51/108 17-50: Merging Nodes 1 2 5 6 8 7 9 4 Deleting the 7 – cause a merge Department of Computer Science — University of San Francisco – p.52/108 17-53: Merging Nodes 1 2 5 8 9 4 6 Department of Computer Science — University of San Francisco – p.55/108 17-54: Deleting Interior Keys How can we delete keys from non-leaf nodes? HINT: How did we delete non-leaf nodes in standard BSTs? Department of Computer Science — University of San Francisco – p.56/108 17-55: Deleting Interior Keys How can we delete keys from non-leaf nodes? Replace key with smallest element subtree to right of key Recursively delete smallest element from subtree to right of key (can also use largest element in subtree to left of key) Department of Computer Science — University of San Francisco – p.57/108 17-58: Deleting Interior Keys 1 3 6 8 9 5 2 7 Department of Computer Science — University of San Francisco – p.60/108 17-59: Deleting Interior Keys 1 3 6 8 9 5 2 7 Deleting the 5 Department of Computer Science — University of San Francisco – p.61/108 17-60: Deleting Interior Keys 1 3 6 8 9 5 2 7 Deleting the 5 Replace the 5 with the smallest element in tree to right of 5 Department of Computer Science — University of San Francisco – p.62/108 17-63: Deleting Interior Keys 1 3 9 6 2 8 7 Department of Computer Science — University of San Francisco – p.65/108 17-64: Deleting Interior Keys 1 3 9 6 10 2 8 7 13 11 12 Removing the 6 Department of Computer Science — University of San Francisco – p.66/108 17-65: Deleting Interior Keys 1 3 9 6 10 2 8 7 13 11 12 Removing the 6 Replace the 6 with the smallest element in the tree to the right of the 6 Department of Computer Science — University of San Francisco – p.67/108 17-68: Deleting Interior Keys 1 3 8 9 7 2 13 10 11 12 Department of Computer Science — University of San Francisco – p.70/108 17-69: Generalizing 2-3 Trees In 2-3 Trees: Each node has 1 or 2 keys Each interior node has 2 or 3 children We can generalize 2-3 trees to allow more keys / node Department of Computer Science — University of San Francisco – p.71/108 17-70: B-Trees A B-Tree of maximum degree k: All interior nodes have dk/2e . . . k children All nodes have dk/2e − 1 . . . k − 1 keys 2-3 Tree is a B-Tree of maximum degree 3 Department of Computer Science — University of San Francisco – p.72/108 17-73: B-Trees 5 11 16 19 1 3 7 8 9 12 15 17 18 22 23 Inserting a 6 .. Department of Computer Science — University of San Francisco – p.75/108 17-74: B-Trees 5 11 16 19 1 3 6 7 8 9 12 15 17 18 22 23 Department of Computer Science — University of San Francisco – p.76/108 17-75: B-Trees 5 11 16 19 1 3 6 7 8 9 12 15 17 18 22 23 Inserting a 10 .. Department of Computer Science — University of San Francisco – p.77/108 17-78: B-Trees 16 19 1 3 9 10 12 15 17 18 22 236 7 5 8 11 Note that the root only has 1 key, 2 children All nodes in B-Trees with maximum degree 5 should have at least 2 keys The root is an exception – it may have as few as one key and two children for any maximum degree Department of Computer Science — University of San Francisco – p.80/108 17-79: B-Trees B-Tree of maximum degree k Generalized BST All leaves are at the same depth All nodes (other than the root) have dk/2e − 1 . . . k − 1 keys All interior nodes (other than the root) have dk/2e . . . k children Department of Computer Science — University of San Francisco – p.81/108 17-80: B-Trees B-Tree of maximum degree k Generalized BST All leaves are at the same depth All nodes (other than the root) have dk/2e − 1 . . . k − 1 keys All interior nodes (other than the root) have dk/2e . . . k children Why do we need to make exceptions for the root? Department of Computer Science — University of San Francisco – p.82/108 17-83: B-Trees Why do we need to make exceptions for the root? Consider a B-Tree of maximum degree 5 with only one element Consider a B-Tree of maximum degree 5 with 5 elements Even when a B-Tree could be created for a specific number of elements, creating an exception for the root allows our split/merge algorithm to work correctly. Department of Computer Science — University of San Francisco – p.85/108 17-84: B-Trees Deleting from a B-Tree (Key is in a leaf) Remove key from leaf Steal / Split as necessary May need to split up tree as far as root Department of Computer Science — University of San Francisco – p.86/108 17-85: B-Trees 5 11 16 19 1 3 7 8 9 12 15 17 18 22 23 Deleting the 15 Department of Computer Science — University of San Francisco – p.87/108 17-88: B-Trees 5 9 16 19 1 3 7 8 11 12 17 18 22 23 Department of Computer Science — University of San Francisco – p.90/108 17-89: B-Trees 5 9 16 19 1 3 7 8 11 12 17 18 22 23 Delete the 11 Department of Computer Science — University of San Francisco – p.91/108 17-90: B-Trees 5 9 16 19 1 3 7 8 12 17 18 22 23 Too few keys Department of Computer Science — University of San Francisco – p.92/108 17-93: B-Trees Deleting from a B-Tree (Key in internal node) Replace key with largest key in right subtree Remove largest key from right subtree (May force steal / merge) Department of Computer Science — University of San Francisco – p.95/108 17-94: B-Trees 5 16 19 1 3 7 8 9 12 17 18 22 23 Remove the 5 Department of Computer Science — University of San Francisco – p.96/108 17-95: B-Trees 5 16 19 1 3 7 8 9 12 17 18 22 23 Remove the 5 Department of Computer Science — University of San Francisco – p.97/108