B-tree

Introduction

Trees are data structures that implement operations on dynamic sets. I would like to single out of such operations - the search for an element, the search for the minimum (maximum) element, insertion, deletion, transition to the parent, transition to the child. Thus, the tree can be used both as an ordinary dictionary and as a priority queue.

The main operations in trees are performed in a time proportional to its height. Balanced trees minimize their height (for example, the height of a binary balanced tree with n nodes is log n). Most are familiar with such balanced trees as the “red-ebony tree”, “AVL-tree”, “Cartesian tree”, so we will not go deeper.

What is the problem with these standard search trees? Consider a huge database presented in the form of one of the mentioned trees. Obviously, we cannot store all this tree in RAM => it stores only a part of information, the rest is stored on third-party media (say, on a hard disk, the access speed to which is much slower). Trees like red-black or Cartesian will require us to log n calls to third-party media. For large n it is a lot. This is the problem that B-trees are supposed to solve!
')
B-trees are also balanced trees, so the time for performing standard operations in them is proportional to height. But, unlike other trees, they were created specifically for efficient work with disk memory (in the previous example, third-party storage media), or rather, they minimize the I / O type inversion.

Structure

When constructing a B-tree, the factor t is applied, which is called the minimal degree. Each node, except the root, must have at least t - 1, and no more than 2t - 1 keys. Denoted by n [x] - the number of keys in the node x.

Keys in a node are stored in non-decreasing order. If x is not a leaf, then it has n [x] + 1 children. If we number the keys in the node x as k [i], and children c [i], then for any key in the subtree with root c [i] (let k1), the following inequality holds: k [i-1] ≤k1≤ k [i] (for c [0]: k [i-1] = -∞, and for c [n [x]]: k [i] = + ∞). Thus, node keys define a range for their children's keys.

All the leaves of a B-tree should be located at the same height, which is the height of the tree. The height of a B-tree with n ≥ 1 nodes and a minimum degree t ≥ 2 does not exceed logt (n + 1). This is a very important statement (why - we will understand later)!

h ≤ logt ((n + 1) / 2) is the logarithm of the base t.

B-tree operations

As mentioned above, in the B-tree all the standard operations of searching, inserting, deleting, etc. are performed.

Search

Search in a B-tree is very similar to a search in a binary tree, only here we have to make a choice of the path to the descendant not from 2 options, but from several. The rest - no difference. The figure below shows the search for key 27. Let us explain the illustration (and, accordingly, the standard search algorithm):

• We go on the keys of the root, while less than necessary. In this case, reached 31.
• We get down to the child, which is located to the left of this key.
• We go through the keys of the new node, while less than 27. In this case, we found 27 and stopped.

The search operation is performed in O (t logt n) time, where t is the minimum degree. It is important here that we perform only O (logt n) disk operations!

Adding

In contrast to the search, the operation of adding is much more complicated than in a binary tree, since it is simply impossible to create a new sheet and insert the key there, since the properties of the B-tree will be violated. It is also impossible to insert a key into an already completed sheet => an operation is required to split the node into 2. If the sheet was filled, then there were 2t-1 keys => split into 2 by t-1, and the middle element (for which t-1 are the first the keys are smaller than it, and the last t-1 more) moves to the parent node. Accordingly, if the parent node was also filled - then we again have to break. And so on to the root (if the root is broken, then a new root appears and the depth of the tree increases). As in the case of ordinary binary trees, insertion is carried out in one pass from the root to the leaf. At each iteration (in search of a position for a new key - from root to leaf), we break all the filled nodes through which we pass (including the leaf). Thus, if, as a result, for insertion, it is necessary to break a node, we are sure that its parent is not filled!

The figure below illustrates the same tree as in the search (t = 3). Only now add the key "15". In search of a position for a new key, we stumble upon a filled node (7, 9, 11, 13, 16). Following the algorithm, we divide it - at the same time, “11” moves to the parent node, and the initial one is broken down into 2. Next, the key “15” is inserted into the second “breakaway” node. All properties of the B-tree are saved!





The add operation also occurs during O (t logt n). It is important again that we perform only disk operations O (h), where h is the height of the tree.

Deletion

Removing a key from a B-tree is an even more cumbersome and complicated process than inserting. This is due to the fact that removing from the internal node requires the restructuring of the tree as a whole. Similar to insertion, it is necessary to check that we save the properties of the B-tree, only in this case it is necessary to keep track of when the keys are t-1 (that is, if the key is deleted from this node, then the node cannot exist). Consider the deletion algorithm:
1) If deletion occurs from a sheet, then it is necessary to check how many keys are in it. If more than t-1, then just delete and nothing else to do. Otherwise, if there is a neighboring sheet (located next to it and having the same parent) that contains more than t-1 key, then we will choose a key from this neighbor, which is a separator between the remaining keys of the neighbor node and the source node (that is, no more all from one group and not less than all from another). Let it be the key k1. Select the key k2 from the parent node, which is the separator of the original node and its neighbor, which we chose earlier. Remove the desired key from the source node (which needed to be deleted), drop the k2 into this node, and instead of k2 in the parent node, put k1. To make it clearer, the figure below is shown (Fig. 1), where the key "9" is deleted. If all neighbors of our site have a t-1 key. Then we merge it with any neighbor, delete the desired key. And we will move that key from the parent node, which was the separator for these two "former" neighbors, to our newly formed node (obviously, it will be the median in it).
Fig. one.


2) Now consider removing the key k from the internal node x. If the child node preceding key k contains more than t-1 key, then we find k1 - the predecessor k in the subtree of this node. Remove it (recursively run our algorithm). Replace k in the source node with k1. We do the same work if the child node following the key k has more than t-1 key. If both (the next and previous child nodes) have a t-1 key, then we unite these children, transfer k to them, and then remove k from the new node (recursively run our algorithm). If the last 2 descendants of the root merge, then they become the root, and the previous root is released. The figure below is shown (Fig. 2), where “11” is removed from the root (the case when the next node has more than t-1 child).
Fig.2.


The delete operation occurs at the same time as the O (t logt n) insertion. And disk operations require only O (h), where h is the height of the tree.

So, we are convinced that the B-tree is a fast data structure (along with such as red-black, AVL). And one more important property that we have received, having considered standard operations, the automatic maintenance of the balance property, let us note that we do not balance it anywhere on purpose.

Database

Having analyzed, together with the speed of execution, the number of operations performed with disk memory, we can say that the B-tree is undoubtedly a more advantageous data structure for cases when we have a large amount of information.

Obviously, increasing t (the minimum degree), we increase the branching of our tree, and therefore reduce the height! What t choose? - Choose according to the size of RAM available to us (ie, how many keys we can view at a time). Usually this number is in the range from 50 to 2000. Let's see what the branching of the tree gives us with a standard example, which is used in all articles about B-tree. Suppose we have a billion keys, and t = 1001. Then we need only 3 disk operations to search for any key! At the same time, we take into account that we can store the root permanently. Now you can see how little it is!

Also, we do not read individual data from different places, but in whole blocks. Moving the tree node to the RAM, we move the allocated block of sequential memory, so this operation works fairly quickly.

Accordingly, we have a minimal load on the server, and at the same time a small waiting time. These and other advantages described have allowed B-trees to become the basis for indexes based on trees in a DBMS.

Upd: visualizer

Literature

“Algorithms. Building and Analyzing "Thomas Kormen, Charles Lazerson, Ronald Rivest, Clifford Stein (Second Edition)
“The art of programming. Sort and search »Donald Knut.