B-Trees

By the end, you can

• Explain why a B-Tree dramatically reduces disk reads compared to a binary search tree.
• Calculate the minimum and maximum number of keys and children for a node given t.
• Trace a search from root to leaf and identify which child pointer is followed at each node.
• Walk through an insertion that causes a split and identify the promoted median key.
• Describe how splits cascade upward and why only a root split adds a new level.
• Apply the borrow and merge strategies for deletion and identify when each is used.
• Explain how deleting a key from an internal node is handled using the in-order predecessor.
• Distinguish a B+-tree from a plain B-Tree and explain why linked leaves speed up range queries.
• Give two concrete examples of real systems that rely on B-Trees or B+-trees.