- B-Trees are a special category of trees, defined by the property according to which each node can hold multiple keys;
- The nodes of a B-tree are called pages;
- There is an internal sorting mechanism for the pages of the B-tree, which makes a page very easy to find;
- The keys are usually sorted within a page, which makes finding a certain key possible with a binary search.
- The number of children of a page is always equal to the maximum number of pages + 1.
Here is how a B-tree looks like:
In this particular tree, the maximum number of keys in a page is, so the maximum number of children for a key is 5 (4 + 1). We observe the following property:
- The left children of 8 (2, 3, 5) contains only keys that are smaller than 8. Similarly, the right children of 8 (which is also the left children of 19, the element (10, 12, 14, 17)) contains only keys that are larger than 8. This is valid for all keys in a B-tree.
Suppose we want to look for ‘12’ in the tree above. The steps are as follows:
- We use binary tree to search for the key in the root of the tree;
- 12 is not there, so we then look for the interval in which 12 fits. In this case this interval is [8, 19], so we then move to the page that is common to these 2 keys, which in our case is the second page of the second level (10, 12, 14, 17).
- We perform a binary search again and this time we find the key.
Next, inserting a key in a B-tree is done by firstly finding the page in which the key fits and then checking whether we can add it or not. If the page is already full, then we have to make some changes, as follows:
For example, if we wanted to add the key 18 in the B-tree above, then normally it would go in the second page of the first level, which is already full. Remember that a page cannot contain more than 4 keys in this case. The solution in this case would be to insert the new value in the place of the parent node (19 in this case), and then re-insert the value just replaced. The final tree would look as follows:
Finally, deleting a key from a B-Tree is always done from a leaf. We firstly look for the key to be deleted by using the searching algorithm described above, and then update the page accordingly. For example, deleting ‘3’ from the tree above would result in the page (2,5) on the first level.