External Memory DictionaryTask: Given a large amount of data thatdoes not fit into main memory, process it intoa dictionary data structure.• Need to minimize number of disk accesses• With each disk read, read a whole blockof data• Construct a balanced search tree thatuses one disk block per tree node• Each node needs to contain more thanone key1From Binary to k-aryA k-ary search tree T is defined as follows:For each node x of T :• x has at most k children• x stores an ordered list of pointers to itschildren• x stores an ordered list of keys• x fulfils the search tree property: keys inthe subtree rooted at i-th child ≤ keys insubtree rooted at (i + 1)-st child.2Chapter 18: B-TreesA B-tree is a balanced tree scheme in whichbalance is achieved by permitting the nodesto have multiple keys and more than twochildren.3Definition Let t ≥ 2 be an integer. A tree Tis called a B-tree having minimum degree tif the leaves of T are at the same depth andeach node u has the following properties:1. u has at most 2t − 1 keys.2. If u is not the root, u has at least t − 1keys.3. The keys in u are sorted in the increasingorder.4. The number of u’s children is preciselyone more than the number of u’s keys.5. For all i ≥ 1, if u has at least i keys andhas children, then every key appearing inthe subtree rooted at the i-th child of u isless than the i-th key and every keyappearing in the subtree rooted at the(i + 1)-st child of u is greater than thei-th key.4SRPDYWVMNQTXHLKJF GB C Zroot[T]5NotationLet u be a node in a B-tree. By n[u] wedenote the number of keys in u. For each i,1 ≤ i ≤ n[u], keyi[u] denotes the i-th key of u.For each i, 1 ≤ i ≤ n[u] + 1, ci[u] denotes thei-th child of u.TerminologyFor the sake of simplicity we will introducesome terminology.We say that a node is full if it has 2t − 1 keysand we say that a node is lean if it has theminimum number of keys, that is t − 1 keys inthe case of a non-root and 1 in the case ofthe root.2-3-4 TreesB-trees with minimum degree 2 are called2-3-4 trees to signify that the number ofchildren is two, three, or four.6Depth of a B-treeTheorem A Let t ≥ 2 and n be integers.Let T be an arbitrary B-tree with minimumdegree t having n keys. Let h be the heightof T . Then h ≤ logtn+12.Proof The height is maximized when all thenodes are lean. If T is of that form, thenumber of keys in T is1+hXi=12(t−1)ti−1= 2(t−1)th− 1t − 1+1 = 2th−1.Thus the depth of a B-tree is at most1lg tofthe depth of an RB-tree.7Searching for a key k in a B-treeStart with x = root[T ].1. If x = nil, then k does not exist.2. Compute the smallest i such that the i-thkey at x is greater than or equal to k.3. If the i-th key is equal to k, then thesearch is done.4. Otherwise, set x to the i-th child.The number of examinations of the key isO((2t − 1)h) = O(t logt(n + 1)/2).Binary search may improve the search withina nodeHow do we search for apredecessor?CSR8B-tree searching runtime• O(t) per node• Path has height h = O(logtn)• CPU-time: O(tlogtn)Disk accesses: O(logtn). Disk accesses aremore expensive than CPU time9B-Tree-Predecessor(T, x, i)1: Find a pred. of keyi[x] in T2: if i ≥ 2 then3: if ci[x] = nil then return keyi−1[x]4: If i ≥ 2 & x is a leaf5: return the (i − 1)st key6: else {7: If i ≥ 2 & x is not a leaf8: find the rightmost key in the i-th child9: y ← ci[x]10: repeat11: z ← cn[y]+112:if z 6= nil then y ← z13: until z = nil14: return keyn[y][y]15: }1016: else {17: Find y and j ≥ 1 such that18: x is the leftmost key in cj[y]19: while y 6= root[T ] and c1[p[y]] = y do20: y ← p[y]21: j ← 122: while cj[p[y]] 6= y do j ← j + 123: if j = 1 then return “No Predecessor”24: return keyj−1[p[y]]25: }11Basic Operations, Split & MergeSplit takes a full node x as part of the input.If x is not the root, then its parent should notbe full. The input node is split into threeparts: the middle key, a node that haseverything to the left of the middle key, and anode that has everything to the right of themiddle key. Then the three parts replace thepointer pointing to x. As a result, in theparent node the number of children and thenumber of keys are both increased by one.12XR BF D HFN PH mLJB XN P QRmDLJ K QKt=4insertednode y node y node znode x13B-Tree-Split(T, x)1: if n[x] < 2t − 1 then return “Can’t Split”2: if x 6= root[T ] and n[p[x]] = 2t − 1 then3: return “Can’t Split”4: Create new nodes y and z5: n[y] ← t − 16: n[z] ← t − 17: for i ← 1 to t − 1 do {8: keyi[y] ← keyi[x]9: keyi[z] ← keyi+t[x]10: }11: for i ← 1 to t do {12: ci[y] ← ci[x]13: ci[z] ← ci+t[x]14: }15: If x is the root then create a new root16: if x = root[T ] then {17: Create a new node v18: n[v] ← 019: c1[v] ← x20: p[x] ← v21: root[T ] ← v22: }1423: Find the spot for insertion24: j ← 125: while cj[p[x]] 6= x do j ← j + 126: Open up space for insertion27: if j ≤ n[p[x]] then28: for i ← n[p[x]] downto j do {29: keyi+1[p[x]] ← keyi[p[x]]30: ci+2[p[x]] ← ci+1[p[x]]31: }32: Insertion33: keyj[p[x]] ← keyt[x]34: cj[p[x]] ← y35: cj+1[p[x]] ← z36: n[p[x]] ← n[p[x]] + 137: p[y] ← p[x]38: p[z] ← p[x]39: Return the pointer to the parent40: return p[x]15Merge takes as input a node and the positionof a key. Then it merges the key and the pairof children flanking the key into one node.What kind of properties mustthe input node and thechildren satisfy for such anoperation be possible?CSR16LaGWell, the input node must notbe lean, and the two childrenmust be lean.That’s right.CSR17HD F B HDB RN PF XLJX RLJ Km N P QQmKnode znode ynode xdroppednode xnode yt=418B-Tree-Merge(T, x, i)1: Merge the i-th key of x and the two2: children flanking the i-th key3: y ← ci[x] y is the left child4: z ← ci+1[x] z is the right child5: if (n[y] > t − 1 or n[z]] > t − 1) then6: return “Can’t Merge”7: keyt[y] ← keyi[x] Append the middle key8: for j ← 1 to t − 1 do Copy keys from z9: keyt+j[y] ← keyj[z]10: for j ← 1 to t do {11: ct+j[y] ← cj[z] Copy children from z12: p[cj[z]] ← y Fix the parent pointers13: }14: n[x] ← n[x] − 1 Fix the n-tag15: if (n[x] = 0) then { If x was the root16: root[T ] ← y and was lean, then17: p[y] ← nil y becomes the root18: }1919: If the middle key is not the last key20: Fill the gap by moving things21: else if i ≤ n[x] then …