B-Trees (continued)Worst-Case Disk AccessesSlide 3Average Disk AccessesDelete (2-3 tree)Delete From A LeafSlide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Delete A PairDisk AccessesSlide 19Slide 20Slide 21Worst CaseInternal Memory B-TreesNode StructureNode Operations For InsertNode Operations For DeleteSlide 27Complexity Of B-Tree Node OperationsB-Trees (continued)•Analysis of worst-case and average number of disk accesses for an insert.•Delete and analysis.•Structure for B-tree nodeWorst-Case Disk Accesses15 2041 3 5 6 30 401316 177 129810Insert 2.Insert 18.Insert 14.Worst-Case Disk Accesses•Assume enough memory to hold all h nodes accessed on way down.•h read accesses on way down.•2s+1 write accesses on way up, s = number of nodes that split.•Total h+2s+1 disk accesses.•Max is 3h+1.Average Disk Accesses•Start with empty B-tree.•Insert n pairs.•Resulting B-tree has p nodes.•# splits <= p –2, p > 2.•# pairs >= 1+(ceil(m/2) – 1)(p – 1).•savg <= (p – 2)/(1+(ceil(m/2) – 1)(p – 1)).•So, savg < 1/(ceil(m/2) – 1).•m = 200 => savg < 1/99.•Average disk accesses < h + 2/99 + 1 ~ h + 1.•Nearly minimum.Delete (2-3 tree)• Delete the pair with key = 8.• Transform deletion from interior into deletion from a leaf.• Replace by largest in left subtree.15 20812 45 6 30 40916 173Delete From A Leaf• Delete the pair with key = 16.• 3-node becomes 2-node.15 20812 45 6 30 40916 173Delete From A Leaf• Delete the pair with key = 17.• Deletion from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• If so borrow a pair and a subtree via parent node.15 20812 45 6 30 409317Delete From A Leaf• Delete the pair with key = 20.• Deletion from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• If not, combine with sibling and parent pair.15 30812 45 6 932040Delete From A Leaf• Delete the pair with key = 30.• Deletion from a 3-node.• 3-node becomes 2-node.30 40812 45 6 9315Delete From A Leaf812 45 6 931540• Delete the pair with key = 3.• Deletion from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• If so borrow a pair and a subtree via parent node.Delete From A Leaf812 5941540• Delete the pair with key = 6.• Deletion from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• If not, combine with sibling and parent pair.6Delete From A Leaf814 5 91540• Delete the pair with key = 40.• Deletion from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• If not, combine with sibling and parent pair.2Delete From A Leaf814 5• Parent pair was from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• If not, combine with sibling and parent pair.29 15Delete From A Leaf14 5• Parent pair was from a 2-node.• Check an adjacent sibling and determine if it is a 3-node.• No sibling, so must be the root.• Discard root. Left child becomes new root.9 152 8Delete From A Leaf14 5• Height reduces by 1.9 152 8Delete A Pair•Deletion from interior node is transformed into a deletion from a leaf node.•Deficient leaf triggers bottom-up borrowing and node combining pass.•Deficient node is combined with an adjacent sibling who has exactly ceil(m/2) – 1 pairs.•After combining, the node has [ceil(m/2) – 2] (original pairs) + [ceil(m/2) – 1] (sibling pairs) + 1 (from parent) <= m –1 pairs.Disk Accesses Borrow.Combine.Minimum.15 2045 6 30 401316 177 1298103Worst-Case Disk Accesses•Assume enough memory to hold all h nodes accessed on way down.•h read accesses on way down.•h – 1 sibling read accesses on way up.•h – 2 writes of combined nodes on way up.•3 writes of root and level 2 nodes for sibling borrowing at level 2.•Total is 3h.Average Disk Accesses•Start with B-tree that has n pairs and p nodes.•Delete the pairs one by one.•n >= 1+(ceil(m/2) – 1)(p – 1).•p <= 1 + (n – 1)/(ceil(m/2) – 1).•Upper bound on total number of disk accesses.Each delete does a borrow.The deletes together do at most p –1 combines/merges. •# accesses <= n(h+4) + 2(p – 1).Average Disk Accesses•Average # accesses <= [n(h+4) + 2(p – 1)]/ n~ h + 4.•Nearly minimum.Worst Case•Alternating sequence of inserts and deletes.•Each insert does h splits at a cost of 3h + 1 disk accesses.•Each delete moves back up to root at a cost of 3h disk accesses.•Average for this sequence is 3h + 1 for an insert and 3h for a delete.Internal Memory B-Trees•Cache access time vs main memory access time.•Reduce main memory accesses using a B-tree.Node Structure•Node operations during a search.Search the node for a given key. q a0 p1 a1 p2 a2 … pq aqNode Operations For InsertFind middle pair.3-way split around middle 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Insert a dictionary pair and a pointer (p, a).Node Operations For Delete•Delete a dictionary pair.•Borrow.Delete, replace, insert.•Combine.3-way join.Node Structure•Each B-tree node is an array partitioned into indexed red-black tree nodes that will keep one dictionary pair each.•Indexed red-black tree is built using simulated pointers (integer pointers).Complexity Of B-Tree Node Operations•Search a B-tree node … O(log m).•Find middle pair … O(log m).•Insert a pair … O(log m).•Delete a pair … O(log m).•Split a B-tree node … O(log m).•Join 2 B-tree nodes … O(m).Need to copy indexed red-black tree that represents one B-tree node into the array space of the other B-tree