2-3 Trees and B-Trees

February 13, 2015 6.046J/18.410J Recitation 2 Design and Analysis of Algorithms Massachusetts Institute of Technology Profs. Erik Demaine, Srini Devadas and Nancy Lynch 2-3 Trees and B-Trees 1 Recap 1.1 Balanced Binary Search Trees Binary Search Trees that guarantee O(log(n)) height by rebalancing after Insert/Delete operations. 1.2 Example Insertion and Rotation 7 Insert 1 4 2 11 7 4 6 Rotate 11 2 4 7 2 6 1 6 11 1 2 2-3 Trees 2.1 Properties 2-3 Trees are balanced search trees. Every node with children (non-leaf) has either two children (2-node) and consists of one piece of data, or has three children (3-node) and consists of 2 pieces of data. 3-Node A C 2-Node B D A E • Every non-leaf is a 2-node or 3-node • All leaves are at the same level • All non-leaves branch B C 2 Recitation 2: 2-3 Trees and B-Trees • All data is kept in sorted order • Every leaf node will contain one or two fields • Height ≤ lgn (More dense than BST) 2.2 Example 2-3 Tree 30 10 3 2.3 7 17 38 14 20 24 32 41 48 Search Very similar to Binary Search. Start at the root node, and traverse down tree in order. Tree is sorted so only need to look at one node for each level of tree. Because of this Search runtime is O(lg(n)) Search(14) 30 10 3 7 17 14 38 20 24 32 41 48 Recitation 2: 2-3 Trees and B-Trees 2.4 3 Insert Insert(X) Steps: • Search for element X for where it would go in a leaf of the tree. • Insert element X into where it would go. • While there is overflow, a node has more than 3 elements, Split node into left half, median, and right half Then promote median up a level. If there is a parent, add it to the node. If there is no parent, create a new node of just the Median node as the new root. • Runtime is O(lg(n)) 4 Recitation 2: 2-3 Trees and B-Trees 2.5 Delete Delete(X) Steps: • Swap item to delete with inorder successor if item is not already a leaf. • Redistribute and merge nodes if there is underflowing in order to get back to a correct 2-3 tree • Runtime is O(lg(n)) Recitation 2: 2-3 Trees and B-Trees 2.5.1 5 Redistribute Example     'HOHWH            'HOHWH                     'HOHWH    'HOHWH           'HOHWH 6 Recitation 2: 2-3 Trees and B-Trees 2.5.2 Merge Example 24 Delete 30 10 32 7 20 30 41 10 24 7 3 20 Delete 30 32 41 B-Trees B-Trees are tree data structures that store sorted data. B-Trees can be seen as a generalization of Binary Search Trees where nodes can have more than one key/value and more than two children. Similar to BSTs, they support search, insertion and deletion in logarithmic time. 3.1 Properties A B-tree has a parameter called the minimum degree or branching factor. For the purposes of our discussion let the branching factor be B. • For any non leaf node, the number of children is one greater than the number of keys in that node. • Every non-root node contains at least B − 1 keys. Consequently, all internal (non-leaf and non-root) nodes have at least B children. • Every node contains at most 2B − 1 keys. Consequently, all nodes have at most 2B children. • All the leaves are at the same depth. Recitation 2: 2-3 Trees and B-Trees 7 The keys is a B-tree are sorted in a similar fashion to BSTs. Consider a node x with C children. Let’s say that x has keys k1 < k2 < ... < kC . For ease of notation, we define k0 = ∞ and kn + 1 = −∞. If K belongs to the ith (1 ≤ i ≤ n + 1) sub-tree of x, then ki−1 ≤ K ≤ ki . • Search time is O(lg(n)) • Insert/Delete time is O(lg(n)) if B = O(1) 3.2 Why B-Trees • Caches read whole blocks of data, and want entire block useful • Set parameter B equal to block size • O(logb (n)) block reads per Search, Insert, Delete operations. B-Trees are used by most databases and filesystems: -Databases: Sleepycat/BerkelyDB, MySQL, SQLite -Filesystems: MacOS HFS/HFS+, ReiserFS, Windows NTFS, Linux ext3, shmfs