MySQL tuning

Article Directory

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

Insert picture description here

(2) Insert H, n>4, the letter G in the middle element splits upward to the new node

Insert picture description here

(3) Inserting EKQ does not need to split

Insert picture description here

(4) Insert M, and the letter M in the middle element splits upwards to the parent node G

Insert picture description here

(5) Inserting FWLT does not need to split

Insert picture description here

(6) Insert Z, and the middle element T is split up to the parent node

Insert picture description here

(7) Insert D, and the middle element D wants to split up into the parent node. Then insert P, R, X, Y without splitting

Insert picture description here


(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

Insert picture description here

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

B+ tree diagram

Insert picture description here

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:

Insert picture description here