A B-Tree is a self-balancing tree data structure that can have more than two child nodes. Keys are stored in a sorted fashion, allowing insertion, traversal, and deletion to be executed in logarithmic time.
All leaf nodes are at the same height, and each node has its keys sorted. The first child pointer contains values less than the first key, the last child pointer contains values greater than the last key, and the remaining child pointer points to the values who range is in between two keys: Ki-1 < k(child) < Ki, where K is a set of keys and kchild is the keys of the subtree.
Why B-Tree
Tree data structures such as binary trees, binary search trees, AVL trees existed long before B-Trees. These data structures are designed for in-memory use by optimizing time and space complexities, allowing data to be accessed and modified quickly. While these data structures are efficient for in-memory storage, the same is not necessarily true for persistent storage.
Binary trees have one key (and a value) in each node. Every newly created node is not necessarily adjacent to the rest of the nodes in the disk. The data locality is negatively affected when nodes are not grouped together, which is a major problem when storing these data structures on disks.
Disk operations, such as reading a sector in HDD or reading a page from SSD, are time consuming processes. When data is not grouped together in a single block or sector, every pointer traversal requires a page fetch.
To reduce the time spent on fetching data from storage, data must be grouped together. Low-fanout structures like a binary tree will have a height ranging from O(log(n)) for balanced tree to O(n) for a skewed tree. Each traversal is a page fetch, which is very inefficient process. Hence, a high-fanout structure such as the B tree is more suitable.
The degree of a B-tree depends on the page size, and usually decided by the database. Each node is usually matches the page size which results in 1 disk read. Typically, the degree is between 100 and 200 which results in a height between 3 to 4.
Operations
B-trees have the same operations as any other tree like addition, deletion, traversal , searching. There are a set of rules for the tree to maintain balance.
Rules include:
- For degree m, each node should have a minimum of ⌊m/2⌋ to maximum of m-1keys.
- For degree m, each node should have a minimum of ⌊m/2⌋+1 children to a maximum ofmchildren.
- Only exception to the above rule is the root, which does not have a restriction.
Insertion
Insertion happens in a bottom-up fashion where values are inserted at the leaf level. If an overflow occurs, the node splits into two, and the middle point is promoted to the parent node. Below is a step-by-step visualization.
Each insertion occurs at the leaf node. The keys are stored in a sorted manner.
Once a node has maximum number of keys, the node is split as left node, right node and middle key. The middle key is promoted to the parent.
The node splitting can propagate up to the root node if every preceding node is full. When an internal node splits, the median key is chosen to be promoted to its parent. For m-1 keys in an internal node, the left and right sub nodes will have m/2 keys. If there was an even number of keys, then after split, one new node will contain one extra key. The child nodes are also transferred to the new nodes.
Searching
Searching is similar to searching in a binary search tree. However, within each node, a binary search must be performed to identify either find the element itself or the child node which contains the target key.
Deletion
Deletion is slightly complicated due to the rules of the B-Tree.
- From leaf node
- If the leaf node maintains a minimum offloor(m/2)after deletion, then no other process is required.
- if the node does not have the minimum number of keys after deletion:
- If sibling nodes has more than minimum number of keys, pull down the parent into the deficient node. Then, find either the least significant key of right sibling or most significant key of left sibling and promote it to the parent.
- If both the sibling nodes have minimum number of keys, pull down the parent key to the deficient node and merge it with a sibling.
- From internal node
- When a key is deleted from an internal node, find a child which has more than the minimum number of keys and promote the key into the parent.
- If both the children nodes have only minimum number of keys, merge the children nodes into one.
B+ Trees
B+ Trees are a modification of B-Trees where the root and internal nodes store only separator key and pointer to child nodes. The actual value associated with the key is stored only in the children node. In a B-Tree, a key appears only once (either in an internal node or a leaf). In a B+ Tree, all keys must exist in the leaf nodes, even if they also act as separators in the internal nodes.
This reduces the size of the internal nodes, allowing more keys to be stored per page. Each leaf node has a pointer to its sibling node, while some implementations have a double pointer between leaf nodes. Since all the leaf nodes are connected via pointers, range queries are performed as a linear operation compared to B-Trees which required jumping up and down the tree.
Visit Visualizer to play around with B-Trees.