1. Introduction
The data structure of mysql index is a tree, and the commonly used storage engine innodb uses B Tree. Here is a brief introduction to B Tree and its related
search trees.
2. Various search trees
1. Binary sorting tree (also called binary search tree)
Binary sorting tree is the simplest search tree. Characteristics:
a) It is a binary tree;
b) The value of all nodes of the left subtree is less than that of its parent node Value, the value of all nodes in the right subtree is greater than the value of its parent node.
2. Balanced binary tree (also known as AVL tree)
The balanced binary tree is based on the binary sorting tree and limits the depth of the tree, thereby reducing Find the number of comparisons,
Features:
a) It is a binary tree;
b) The value of all nodes in the left subtree is less than the value of its parent node , the value of all nodes of the right subtree is greater than the value of its parent node;
c) The depth difference between the left subtree and the right subtree is within -1, 0, 1, otherwise the subtree is Rotation adjustment.
3. B-Tree (B-Tree)
B-tree is a multi-way balanced search tree. Compared with the balanced binary tree, the direct children of the parent node The number of nodes is no longer limited to 2.
You can specify m (custom), so that more nodes can be saved without greatly increasing the depth of the tree.
B-tree is commonly used in file systems.
Features:
a) Each node of the tree has at most m (custom) child nodes;
b) If the root node is not a leaf node, Then there are at least two child nodes;
c) All non-leaf nodes except the root node, at least m/2, take the entire child node;
d) Parent node The values of all nodes in the leftmost subtree are less than the minimum value of the parent node,
The values of all nodes in the rightmost subtree are greater than the maximum value of the parent node,
The remaining middle values The values of all nodes in the subtree are between the values on both sides of the parent node of the pointer;
e) All leaf nodes are on the same level;
Note: All nodes have Value
4. B Tree (B Tree)
B tree is a variant of B-tree. Compared with B-tree, the value of leaf node contains all The value of all parent nodes repeats the value of the leaf node.
The parent node only plays the role of index search, and all leaf nodes also form an ordered linked list.
The storage engine in mysql is the index of innodb, and the data structure used is the B-tree.
Features:
a) The parent node with m child nodes has m keywords;
b) All leaf nodes contain all keywords ( value), and form an ordered linked list from small to large;
c) All non-leaf nodes serve as indexes, and the nodes only contain the maximum value of all nodes in the subtree;
d) All leaf nodes are on the same level;
Note: Leaf nodes contain all keywords (values).
5. B*Tree (B*Tree)
B* tree is a variant of B tree. Compared with B tree, it adds support for non-leaf nodes of the same layer. Pointers to points, that is, non-leaf nodes at the same level, also form a linked list.
3. Summary
In summary, the above search trees are related to each other.
It comes down to the innodb index in mysql, which uses B-tree, such as clustered index, which aggregates data through the primary key and uses B-tree to implement it.
This is an index and also A data storage structure of MySQL. Leaf nodes contain all data, and non-leaf nodes only serve as indexes (if
does not define a primary key, InnoDB will implicitly define a primary key as a clustered index ).
For more technical articles related to MySQL, please visit theMySQL Tutorialcolumn to learn!
The above is the detailed content of What is the data structure of mysql index. For more information, please follow other related articles on the PHP Chinese website!