- Information reprinting instructions
- B tree
- The concept and characteristics of B-tree
- 5-ary tree examples to illustrate the characteristics of B-trees
- B+ tree
- The difference between B+ tree and B tree
- B+ tree diagram
- Advantages of B+ tree
- B+ tree in MySQL
Information reprinting instructions
All screenshot knowledge points in this blog are from https://www.bilibili.com/video/BV1UQ4y1P7Xr?p=1
The concept and characteristics of B-tree
The B-tree is also called a multi-path balanced search tree. The characteristics of an m-forked B-tree are as follows:
- Each node in the tree contains at most m children.
- Except for the root node and leaf nodes, each node has at least [ceil(m/2)] children.
- If the root node is not a leaf node, it has at least two children.
- All leaf nodes are in the same layer.
- Each non-leaf node is composed of n keys and n+1 pointers, where [ceil(m/2)-1]<= n <= m-1
5-ary tree examples to illustrate the characteristics of B-trees
5-ary tree, according to the characteristics, each non-leaf node is composed of n keys and n+1 pointers, where [ceil(m/2)-1]<= n <= m-1
calculates 2<= n <=4 . When n>4, the intermediate node splits to the parent node, and the two nodes split.
Insert CNGAHEKQMFWLTZDPRXYS data as an example. The
evolution process is as follows:
(1) Insert the first 4 letters of CNGA
(2) Insert H, n>4, the letter G in the middle element splits upward to the new node
(3) Inserting EKQ does not need to split
(4) Insert M, and the letter M in the middle element splits upwards to the parent node G
(5) Inserting FWLT does not need to split
(6) Insert Z, and the middle element T is split up to the parent node
(7) Insert D, and the middle element D wants to split up into the parent node. Then insert P, R, X, Y without splitting
(8) Finally insert S, NPQR node>5, intermediate node Q split upward, but after splitting the parent node DGMT n>5, intermediate node M split upward
At this point, the B-tree has been constructed. Compared with the binary tree, the B-tree is more efficient to query data, because for the same amount of data, the hierarchical structure of the B-tree is smaller than the binary tree, so the search speed is faster.
The difference between B+ tree and B tree
B+ tree is a variant of B number. The difference between B+ tree and B tree is:
- The n-ary B+ tree contains at most n keys, and the B tree contains at most n-1 keys
- The leaf nodes of the B+ tree store all key information, arranged in order of key size
- All non-leaf nodes can be regarded as the index part of the key
B+ tree diagram
Advantages of B+ tree
Since the B+ tree only has leaf nodes to store key information, and any key query must go from the root to the leaf, the query efficiency of the B+ tree is more stable.
B+ tree in MySQL
The MySQL index data structure is optimized for the classic B+ number. On the basis of the original B+ tree, adding a linked list pointer to adjacent leaf nodes forms a B+ tree with sequential pointers, which improves the performance of interval access.
Schematic diagram of the B+ tree index structure in MySQL: