B-Trees

• An M-ary search tree allows M-way branching. As branching increases, the depth decreases.
• We can create an M-ary search tree in much the same way as a binary search tree. In a binary search tree, we need one key to decide which of two branches to take. In an M-ary search tree, we need M − 1 keys to decide which branch to take.
• we need to ensure that the M-ary search tree is balanced in some way. We can implement this by using a B-tree
• A B-tree of order M is an M-ary tree with the following properties:

  The data items are stored at leaves.

  The nonleaf nodes store up to M − 1 keys to guide the searching; key i represents the smallest key in subtree i + 1.

  The root is either a leaf or has between two and M children.

  All nonleaf nodes (except the root) have between ⌈M/2⌉ and M children.

  All leaves are at the same depth and have between ⌈L/2⌉ and L data items, for some L (the determination of L is described shortly).
• In a B-tree each node represents a disk block.
• When inserting into a B-Tree and the leaf is full, we can split the nodes.
• Although splitting nodes is time-consuming because it requires at least two additional disk writes, it is a relatively rare occurrence.
• Deletion

  1. Find the item that needs to be removed

  2. Remove the item

  3. If the leaf it was in had the minimum number of data items, then it is now below the minimum

  4. Adopt a neighboring item, if the neighbor is not itself at its minimum

  5. If the neighbor is at its minimum, combine with the neighbor to form a full leaf

  6. The parent has lost a child

  7. If this loss causes the parent to fall below its minimum, then it follows the same strategy

  8. This process could percolate all the way up to the root