B-TreesAVL TreesRed-Black Treesm-way Search Trees4-Way Search TreeMaximum # Of PairsCapacity Of m-Way Search TreeDefinition Of B-Tree2-3 And 2-3-4 TreesB-Trees Of Order 5 And 2Minimum # Of PairsSlide 12Choice Of mInsertSplit An Overfull NodeSlide 16Insert Into A Leaf 3-nodeSlide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Slide 29B-Trees•Large degree B-trees used to represent very large dictionaries that reside on disk.•Smaller degree B-trees used for internal-memory dictionaries to overcome cache-miss penalties.AVL Trees•n = 230 = 109 (approx).•30 <= height <= 43.•When the AVL tree resides on a disk, up to 43 disk access are made for a search.•This takes up to (approx) 4 seconds.•Not acceptable.Red-Black Trees•n = 230 = 109 (approx).•30 <= height <= 60.•When the red-black tree resides on a disk, up to 60 disk access are made for a search.•This takes up to (approx) 6 seconds.•Not acceptable.m-way Search Trees•Each node has up to m – 1 pairs and m children. •m = 2 => binary search tree.4-Way Search Tree10 30 35 k < 10 10 < k < 30 30 < k < 35 k > 35Maximum # Of Pairs•Happens when all internal nodes are m-nodes.•Full degree m tree.•# of nodes = 1 + m + m2 + m3 + … + mh-1 = (mh – 1)/(m – 1). •Each node has m – 1 pairs.•So, # of pairs = mh – 1.Capacity Of m-Way Search Tree m = 2 m = 200 h = 3 7 8 * 106 - 1 h = 5 31 3.2 * 1011 - 1 h = 7 127 1.28 * 1016 - 1Definition Of B-Tree•Definition assumes external nodes (extended m-way search tree).•B-tree of order m.m-way search tree.Not empty => root has at least 2 children.Remaining internal nodes (if any) have at least ceil(m/2) children.External (or failure) nodes on same level.2-3 And 2-3-4 Trees•B-tree of order m.m-way search tree.Not empty => root has at least 2 children.Remaining internal nodes (if any) have at least ceil(m/2) children.External (or failure) nodes on same level.•2-3 tree is B-tree of order 3. •2-3-4 tree is B-tree of order 4.B-Trees Of Order 5 And 2•B-tree of order m.m-way search tree.Not empty => root has at least 2 children.Remaining internal nodes (if any) have at least ceil(m/2) children.External (or failure) nodes on same level.•B-tree of order 5 is 3-4-5 tree (root may be 2-node though).•B-tree of order 2 is full binary tree.Minimum # Of Pairs•n = # of pairs.•# of external nodes = n + 1.•Height = h => external nodes on level h + 1.level # of nodes112>= 23>= 2*ceil(m/2)h + 1>= 2*ceil(m/2)h-1 n + 1 >= 2*ceil(m/2)h-1, h >= 1Minimum # Of Pairs•m = 200. n + 1 >= 2*ceil(m/2)h-1, h >= 1height # of pairs2>= 1993>= 19,9994>= 2 * 106 – 15>= 2 * 108 – 1 h <= log ceil(m/2) (n+1)/2 + 1Choice Of m•Worst-case search time.(time to fetch a node + time to search node) * height(a + b*m + c * log2m) * hwhere a, b and c are constants.msearch time50 400Insert15 20841 3 5 6 30 409 Insertion into a full leaf triggers bottom-up node splitting pass.16 17Split An Overfull Node•ai is a pointer to a subtree.•pi is a dictionary pair. m a0 p1 a1 p2 a2 … pm am ceil(m/2)-1 a0 p1 a1 p2 a2 … pceil(m/2)-1 aceil(m/2)-1 m-ceil(m/2) aceil(m/2) pceil(m/2)+1 aceil(m/2)+1 … pm am•pceil(m/2) plus pointer to new node is inserted in parent.Insert15 20841 3 5 6 30 409• Insert a pair with key = 2.• New pair goes into a 3-node.16 17Insert Into A Leaf 3-node•Insert new pair so that the 3 keys are in ascending order.•Split overflowed node around middle key.1 2 3•Insert middle key and pointer to new node into parent.312Insert15 20841 3 5 6 30 409• Insert a pair with key = 2.16 17Insert15 20845 6 30 40916 17312• Insert a pair with key = 2 plus a pointer into parent.Insert• Now, insert a pair with key = 18.15 20812 45 6 30 40916 173Insert Into A Leaf 3-node•Insert new pair so that the 3 keys are in ascending order.•Split the overflowed node.16 17 18•Insert middle key and pointer to new node into parent.181617Insert• Insert a pair with key = 18.15 20812 45 6 30 40916 173Insert• Insert a pair with key = 17 plus a pointer into parent.15 20812 45 6 30 4093181617Insert• Insert a pair with key = 17 plus a pointer into parent.812 45 6 30 4093 1617151820Insert• Now, insert a pair with key = 7.12 45 6 30 4093 161518208 17Insert• Insert a pair with key = 6 plus a pointer into parent.30 4012 493 161518208 17576Insert• Insert a pair with key = 4 plus a pointer into parent.30 40193161518208 176425 7Insert• Insert a pair with key = 8 plus a pointer into parent.• There is no parent. So, create a new root.30 40193161518206825 7417Insert• Height increases by 1.30 4019316151820625