All you need to know about deleting keys from B trees

B tree is a self-balancing search tree (the tree adjusts itself so that all the leaves are at the same depth) and contains multiple nodes which keep data in sorted order. Each node has 2 or more children and consists of multiple keys.

Following are the 5 properties of a B tree.

1. Every node x has the following:

— x.n (Number of keys)

— x.key_i (The keys stored in ascending order)

— x.leaf (Whether x is a leaf or not)

2. Every node x has (x.n + 1) children.

3. The keys x.key_i separate the ranges of keys stored in each sub-tree.

4. All the leaves have the same depth, which is the tree height.

5. Nodes have lower and upper bounds on the number of keys that can be stored. Here we consider a value t>=2, called minimum degree (or branching factor) of the B tree.

— The root must have at least one key.

— Every other node must have at least (t-1) keys and at most (2t-1) keys. Hence, every node will have at least t children and at most 2t children. We say the node is full if it has (2t-1) keys.

Figure 2: B Tree with root, internal nodes and leaf nodes

So now we have an idea what B trees are, let’s look in to the delete operation, which is much…