This is the 8th day of my participation in the August More Text Challenge

B tree is also called multi-path balanced search tree. The maximum number of children in all nodes of the B tree is called the order of the B tree, which is usually expressed by M. Generally, m>=3 is required for search efficiency.

concept

An M-order B-tree is either an empty tree or an N-fork tree that meets the following characteristics:

  • Each node in the tree has at most m subtrees, that is, at most m-1 keywords

  • If the root node is not terminal, there are at least two trees

  • All non-leaf nodes except the root node have at least [m/2] (rounded up) subtrees, that is, at least [m/2] (rounded up) -1 keyword

  • The structure of all non-leaf nodes is as follows: where Ki (I = 1,2… , n) is the keyword of the node, Pi (I = 1,2… , n) is the pointer to the child root node

n P0 K1 P1 K2 P2 … Kn Pn

  • All leaf nodes appear at the same level with no information (can be regarded as external nodes or search failure nodes similar to split search decision tree, in fact these nodes do not exist, pointer to these nodes is null).

  • B tree is a multi-path equilibrium search tree whose equilibrium factor of all nodes is equal to 0.

B tree height

The height of the B-tree does not include the layer where the last leaf with no information is located.

If n>=1, then for any B tree containing n keywords, height h and order M:

Because each node in a B-tree has at most m subtrees and m-1 keywords, the number of keywords in an m-order B-tree of height H should satisfy n<= (m-1) (1+ M +m^2 +… Plus m to the h minus 1 is equal to m to the h minus 1, so h is greater than =logm of n plus 1.

If the number of keywords in each node is minimized, the height of b-tree containing the same number of keywords will reach the maximum. According to the definition of B-tree: the first layer has at least one node; The second layer has at least 2 nodes; Every non-terminal node except the root node has at least [m/2] subtrees, then the third layer has at least 2 [m/2] nodes… H +1 has at least 2 (m/2) ^(h-1)),

Notice that layer H +1 is a leaf that contains no information. For key word number for n B tree, leaf nodes that search is not successful for the n + 1, thus there are n + 1 > 2 (m / 2) ^ (h – 1), or h < log [m / 2] ((n + 1) / 2) + 1

To find the

Looking up a B tree is similar to looking up a binary sort tree, except that each node is an ordered list of multiple keywords, and instead of making a two-way branching decision at each node, a multi-way branching decision is made based on the node’s subtree.

B tree lookup consists of two basic operations:

  1. Look for nodes in the B tree

  2. Find the keyword in the node.

Because b-trees are often stored on disk, the first lookup is performed on disk and the second lookup is continued in memory. That is, after finding the target node, the node information is first read into the memory, and then the sequential search method or half search method is used in the node.

After a node is found in B tree, it is searched in the ordered table first. If it is found, the search is successful; otherwise, it is searched in the indicated subtree according to the corresponding pointer information. If the leaf node is found (the corresponding pointer is a null pointer), it indicates that there is no corresponding keyword in the tree and the search fails.