Introduction to the properties of B-Tree

B-tree is a common data structure. Along with him is the B+ tree.

Here, we need to clarify the concept. What is the difference between B-tree, B-tree and B+tree? What is their relationship?

In fact, there are only two types of data structures, namely B-tree and B+ tree. Sometimes, B-tree is also called B-tree, they are the same thing. Note that the "-" in the middle of a B-tree is a hyphen, not a "minus sign". In English, it is B-Tree, which is translated into Chinese as B-tree. Some translators like to include a hyphen “-”, so it becomes B-tree, and B-tree is misread by some readers as B-minus tree.

Before introducing B-tree, let's first look at an important concept: order.

The order of a tree is the maximum number of child nodes of each node in the tree. That is to say, if some nodes have 2 child nodes, some nodes have 4 child nodes, and the maximum number of child nodes is 5, then the order of the tree is 5.

From this perspective, the order of a binary tree is 2.

Next, we introduce the main properties of B-tree. We assume that the order of the B-tree is m. A B-tree of order m is either an empty tree or a tree with the following properties:

1. Each node has at most m child nodes. There are at least m/2 (rounded up) nodes. Or it can be expressed this way: m/2 <= number of child nodes <= m. But the root node is an exception. The root node can have at least 2 child nodes.

2. The number of child nodes of each node is 1 more than the number of keywords stored in the node. That is, when k keywords are stored in a node, the node will have k + 1 child nodes (subtrees).

3. The k keywords in each node are arranged from small to large, and are recorded as k1, k2, k3, ... kk. Then the node will have k+1 pointers, denoted as p0, p1, p2, ... pk. Moreover, all elements in the child nodes pointed to by p3 are greater than k3 and less than k4, as shown in the following figure. This is also relatively easy to understand and remember. Each pointer p is located exactly at the gap between the keyword k. Therefore, the value of the element of the child node pointed to by the pointer at the gap should naturally be greater than the element to the left of the pointer and less than the element to the right of the pointer.

4. B-tree is a strictly balanced search tree, and the heights of its left and right subtrees are equal. The leaf nodes are at the same layer and can be represented by empty nodes.

An example of a B-tree:

Summarize

The above is the full content of this article. I hope that the content of this article will have certain reference learning value for your study or work. Thank you for your support of 123WORDPRESS.COM. If you want to learn more about this, please check out the following links