# Information reprinting instructions

All screenshot knowledge points in this blog are from https://www.bilibili.com/video/BV1UQ4y1P7Xr?p=1

# B tree

## 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.

# B+ tree

## 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

## 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: