B-Trees

Definition

A m-way tree in which

• The root has at least one key
• Non-root nodes have at least m/2 subtrees (i.e., at least (m - 1)/2 keys)
• All the empty subtrees (i.e., external nodes) are at the same level

B-tree of order 3	not a B-tree

B-trees are especially useful for trees stored on disks, since their height, and hence also the number of disk accesses, can be kept small.

The growth and contraction of m-way search trees occur at the leaves. On the other hand, B-trees grow and contract at the root.

Insertions

• Insert the key to a leaf
• Overfilled nodes should send the middle key to their parent, and split into two at the location of the submitted key.

add 19
add 21

Deletions

• Key that is to be removed from a node with non-empty subtrees is being replaced with the largest key of the left subtree or the smallest key in the right subtree. (The replacement is guaranteed to come from a leaf.)

  remove 26
• If a node becomes under staffed, it looks for a sibling with an extra key. If such a sibling exist, the node takes a key from the parent, and the parent gets the extra key from the sibling.

  remoce 22
• If a node becomes under staffed, and it can’t receive a key from a sibling, the node is merged with a sibling and a key from the parent is moved down to the node.

  remove 18