B-trees

Question 1

Describe the four properties for an m-way b-tree (a b-tree of order m).

Answer 1

1) All leaves are on the same level.

2) All internal nodes except the root have at most m non empty children and at least
ceil (m / 2 ) nom empty children.

3) The number of keys in each internal node is equal to 1 less the number of its
nonempty children.

4) The root has at most m children.

Question 2

Describe inserting an element into the b-tree.

Answer 2

1) Search for a position in the b-tree where the new element would fit.
2) Try inserting it.
3) Observe which of the properties the insertion violates.
4) Fix the problems.

The problems can usually be fixed by splitting the current node into three nodes (Left, right and middle), and propagating the middle element upwards. This might mean the children of this node need be split and moved either to the resulting left/right subtrees independent of each other.

Question 3

Describe deleting an element from a b-tree.

Answer 3

1) Try deleting the element.
2) Observe which properties the deletion violates.
3) Observe what we can change to make up for the problem.
4) Implement those changes.

A deletion can usually be