An introduction to the Properties of B-Tree

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

Here, the concept needs to be clarified. What's the difference between a B tree, a B-tree, and a B+ tree? What's their relationship?

In fact, there are only two types of data structures, namely B-trees and B+ trees. Sometimes, B-trees are called B-trees, and they are one thing. Note that the "-" in the middle of the B-tree is a hyphen, not a "minus sign." English is B-Tree, translated into Chinese, that is, B-tree, some translations like to hyphen "-" also with, so it becomes B-tree, and B-tree is misunderstood by some readers as B-minus tree.

Before introducing B-trees, 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 most nodes have 5 child nodes, then the order of this tree is 5.

From this point of view, the binary tree order is 2.

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

Each node has at most m children. There are at least m/2 (rounded up) nodes. Or put it this way: m/2