All About B-Trees

Before diving right into B-Trees and its properties, let’s review a few other tree data structures with which we are familiar.

In computer science, a Binary tree is a tree data structure in which each node can have at most two children, which we refer to as the left child and the right child. A special type of binary tree is the Binary Search Tree, in which nodes are assigned values. Each left subtree can only have values that are less than the node and each right subtree can only have values greater than the node.

For example:

Binary Tree (not a BST) vs. Binary Search Tree (balanced)

What is a B Tree?

B-Trees are an extension of a binary search tree since nodes can have more than two children. So, what is a B-Tree? A B-Tree is defined as a self-balancing tree data structure that maintains sorted data, allows for searches, insertions, and deletions in logarithmic time.

B-Trees of order m (the maximum number of children) have the following properties:

• each node has at most m children
• each internal node has at least ⌈m/2⌉ children
• root has at least two children if it is not a leaf
• a non-leaf node with k children has k -1 keys
• all leaves must appear at the same level

In the following example, the B-Tree is of order 3, since each node can have at most 3 children. This maximum number of keys is m -1 = 2. For instance, the root node contains keys 4 and 7. Additionally, the leaves are all at the same level.

Created by BTree Visualization https://www.cs.usfca.edu/~galles/visualization/BTree.html

Searching a B-Tree

Similar to the way we search a Binary Search Tree, we can search a B-Tree, that is, we would start at the root node and then recursively traverse the tree from top to bottom. Using the above example, suppose we wanted to search for the value 11, we can follow these steps:

1. Start from the root node at the left-most key: 4
2. Since 11 is greater than 4 and it is not between 4 and 7, we need to look to the right child node of the key:7
3. Traverse down to the right child node of 7, and start at the left-most key: 9
4. Since 11 is greater than 9, look to the right of that key
5. Finally, the right-most key for this node is 11, a match to the value we are searching for

Insertions

In order to add a new element to a B-Tree, search the tree to find the leaf where it should be added. Then follow these steps:

1. If the node does not exceed the maximum number of allowed elements, there is room to insert the new element
2. If the node is full, the node must be split by a separation value (median).

• Using the leaf’s elements and the new element, find the median

• Values less than the median are put in the new left node and values greater than the median are put in the new right node

• The median is inserted into the node’s parent, which may cause another split. If the node is the root node with no parent, the height of the tree is increased by creating a new root node above that root node.

Using the same figure shown above, suppose we wanted to insert the values, 8 and 10.

To insert 8, 8 is placed in the same node containing the keys 9 and 11. The node lists the three keys in sorted order, but the node was already full, so the node must be split by the median which is 9. 9 is moved up to the parent node listed after 4 and 7. Again, three is too many, so 7 is moved up to become a new root node with child nodes 4 and 9. Now, the tree is balanced.

To insert 10, we know it must be placed in the right child node of 9. Since the right child only contains one key-value equal to 11, there is room to insert the key equal to 10. Thus, the new right child node of 9 contains 10 and 11.

Why use B-Trees?

Although B-Trees seem pretty complicated, they are quite elegant and really useful. So, how are they used exactly? A great use-case for B-Trees is for storing large amounts of data. For this reason, it is a data structure that is commonly used in databases and filesystems. It has a time complexity of O(log(n)) and space complexity of O(n).

Other Resources and References: To learn more about B-Trees, refer to the following resources and references listed below.

1. B-Tree, Wikipedia https://en.wikipedia.org/wiki/B-tree
2. B-Trees Visualization, https://www.cs.usfca.edu/~galles/visualization/BTree.html
3. B-Tree Set 2 (Insert) https://www.geeksforgeeks.org/b-tree-set-1-insert-2/
4. B-Tree Set 3 (Delete) https://www.geeksforgeeks.org/b-tree-set-3delete/
5. Know Thy Complexities, Eric Rowell http://bigocheatsheet.com/