Shulou(Shulou.com)06/01 Report--

This article is mainly about what is the data structure of mysql index. if you are interested, let's take a look at this article. I believe it is of some reference value to you after reading what is the data structure of mysql index.

I. brief introduction

The data structure of mysql index is tree, and the commonly used storage engine innodb uses B+Tree. Here for B+Tree and its related

Find the tree for a brief introduction.

2. Various search trees

1. Binary sort tree (also known as binary search tree)

The binary sort tree is the simplest search tree with the following features:

A) is a binary tree

B) the value of all nodes of the left subtree is less than that of its parent node, and the value of all nodes of the right subtree is greater than that of its parent node.

2. Balanced binary tree (also known as AVL tree)

On the basis that the balanced binary tree is a binary sort tree, the depth of the tree is limited, thus the number of search and comparison is reduced.

Features:

A) is a binary tree

B) the value of all nodes of the left subtree is less than that of its parent node, and the value of all nodes of the right subtree is greater than that 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 rotated.

3. B-tree (B-Tree)

The B-tree is a multi-path balanced search tree. Relative to the balanced binary tree, the number of direct children of the parent node is no longer limited to 2.

You can specify m (custom) so that you can save more nodes without significantly increasing the depth of the tree.

B-trees are 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, there are at least two child nodes

C) all non-leaf nodes except the root node, with at least the whole sub-node on mmax 2

D) the values of all nodes in the leftmost subtree under the parent node 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 values of all nodes in the rest of the intermediate subtree are between the values of the parent node of the pointer.

E) all leaf nodes are in the same layer

Note: all nodes have values

4. B + tree (B+Tree)

The B + tree is a variant of the B-tree. Relative to the B-tree, the values of the leaf nodes contain all the values, and the values of all the parent nodes repeat the values of the leaf nodes.

The parent node only plays the role of index lookup, and all the leaf nodes also form an ordered linked list.

The index of innodb is the storage engine in mysql, and the data structure adopted is B+ tree.

Features:

A) the parent node with m child nodes has m keywords

B) all leaf nodes contain all keywords (values) and form an ordered list from small to large

C) all non-leaf nodes act as indexes, and the nodes contain only the maximum values of all nodes in the subtree

D) all leaf nodes are in the same layer

Note: the leaf node contains all keywords (values).

5. B* tree (B*Tree)

The B* tree is a variant of the B + tree, which adds a pointer to the non-leaf nodes in the same layer, that is, the non-leaf nodes in the same layer also form a linked list.

III. Summary

To sum up, 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, to aggregate data through primary key, and uses B + tree to implement.

This is not only an index, but also a data storage structure of mysql. The leaf node contains all the data, and the non-leaf node only acts as an index (if

If no primary key is defined, innodb implicitly defines a primary key as a clustered index).

Is it helpful to you that the above details about what is the data structure of mysql index? If you want to know more about it, you can continue to follow our industry information section.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.