B-Tree.md (2185B)
1 # B-Tree 2 3 **Definition:** A B-Tree is a self-balancing data structure that facilitates log time search, sequential access, insertion, and deletion. This is a generalization of binary search trees that allows nodes to have >2 children. 4 5 A B-tree of order m is defined as follows (according to Knuth): 6 7 1. Every node has at most m children 8 2. Every node, except for the root and the leaves has at least ceil(m/2) children 9 3. The root has at least two children unless it is a leaf 10 4. A non-leaf node with k children contains k-1 keys 11 12 ## Algorithms 13 14 ### Search 15 16 Start at the root node. Each key in the root node is ordered so find min(key) s.t. key >= root. We then go to the child i, corresponding to the index of the min key. If there are no smaller keys, we travel to node i+1. We repeat this until finding the key we are searching for. 17 18 ### Insertion 19 20 Search for the location the key should reside. Insert the key. If this insertion results in |key| > m then split the current node in half with the center-most key being propagated to the parent node. 21 22 This process is then applied to the parent if it breaks the node key count invariant until the B-tree is in a valid state. 23 24 ### Deletion 25 26 #### Deletion From A Leaf 27 28 1) Find the key in the tree 29 2) Remove the key 30 31 #### Deletion From an Internal Node 32 33 1) Find the key in the tree 34 2) Remove the key 35 3) If the leaf now has fewer than t-1 keys, rebalance the tree 36 37 #### Deletion From an Internal Node 38 39 1) Find the key k in the tree 40 2) If: 41 - The left child of k has at least t keys: 42 - Find the predecessor of k in that subtree and recursively delete it, replacing k with the predecessor 43 - Else if the right child of k has at least t keys: 44 - Find the successor of k in that subtree and recursively delete it, replacing k with the successor 45 - Else if both children have exactly t-1 keys: 46 - Merge k and both children into one node, then recursively delete k from the merged node 47 48 #### Rebalancing (node has < t-1 keys) 49 50 - Try to borrow from a sibling 51 - Else merge the node with a sibling and pull down the separating key from the parent 52 - If the parent now has too few keys, recursively rebalance upward