Detailed Introduction to MySQL Innodb Index Mechanism

1. What is an index?

An index is a data structure that the storage engine uses to quickly find records.

2. What data structures does the index have?

• Sequential search structure: This search efficiency is very low and the complexity is O(n). The query efficiency is very low when the amount of data is large.
• Ordered data arrangement: Binary search is also called half search.

By comparing once, the search range is reduced by half. The data in MySQL is not an ordered sequence.

• Binary search tree: The key value of the left subtree is always less than the key value of the root, and the key value of the right subtree is always greater than the key value of the root. The sequence obtained by in-order traversal is an ordered sequence, but if the binary search tree is not well constructed, it is no different from a sequential search.

• Balanced binary tree: If the binary search tree needs to be balanced, a balanced binary tree is derived. A balanced binary tree must first satisfy the definition of a binary search tree, and secondly, the maximum difference in height between the two subtrees of any node must be 1. Obviously the tree above is not a balanced binary tree. An example of a balanced binary tree is as follows:

The time complexity of a balanced binary search tree is O(logN). The query speed is indeed very fast, but the cost of maintaining a balanced binary tree is also very high. Typically, one or more left and right rotations are required to achieve balance after an insertion or update.

• B-tree: The difference between B-tree and balanced binary tree is that B-tree is a multi-way tree, also known as balanced multi-way search tree:

1. The root node has at least two child nodes (each node has M-1 keys, arranged in ascending order) and other nodes have at least M/2 child nodes.
2. The leaf nodes are all on the same layer.

• B+ Tree

B+ tree is a variant of B tree, which evolved from B tree and index sequential access method (B tree is rarely used in real life).
The B+ tree is a balanced search tree designed for disks or other direct storage auxiliary devices.
In a B+ tree, all record nodes are placed on the leaf nodes of the same layer in order of key values ​​and connected by leaf node pointers.
All queries must find leaf nodes, and the query performance is stable.
All leaf nodes form an ordered linked list to facilitate range queries. Each leaf node stores pointers to adjacent leaf nodes, and the leaf nodes themselves are linked in ascending order according to the size of the keyword (bidirectional linked list)

3. Why does Innodb use B+ tree as index?

1. The system can effectively utilize the block reading characteristics of the disk to load as much index data as possible while reading the same disk block to improve the index hit efficiency, thereby reducing the number of disk IO reads (locality principle and disk pre-reading).
2. The disk read and write cost of B+ tree is lower: the internal nodes of B+ tree do not have pointers to the specific information of keywords (only leaf nodes store it), so its internal nodes are smaller than those of B-tree. If all keywords of the same internal node are stored in the same disk block, the disk block can accommodate more keywords, and more keywords need to be searched at one time in the memory, so the relative IO read and write times are reduced.
3. The query efficiency of B+ tree is more stable. Since the non-terminal point is not the node that ultimately points to the file content, it is just an index of the keyword in the leaf node. Therefore, any keyword search must take a path from the root node to the leaf node. The path lengths of all keyword queries are the same, resulting in comparable query efficiency for each piece of data.
4. B+ trees support range queries, while B trees do not.

4. Index classification

Classification from the storage structure: BTree index, Hash index, full-text index

Classification from the application: primary key index, unique index, composite index

From the perspective of physical storage: clustered index and non-clustered index (auxiliary index)

Let's talk about what is a clustered index and what is a non-clustered index:

• Clustered Index

A B+ tree is constructed according to the primary key of each table, and the row record data of the entire table is stored in the leaf node. The leaf nodes of the clustered index are also called data pages, and each data page is linked through a doubly linked list.

Clustered indexes are very fast for sorted and range searches of the primary key.

• Auxiliary index

In addition to storing the index column, the pointer to the leaf node is also stored.

The above is the full content of this article. I hope it will be helpful for everyone’s study. I also hope that everyone will support 123WORDPRESS.COM.