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

The following is to understand what is the principle of MySQL index, I believe that we will benefit a lot after reading, the text is not much in the essence, hope that what is the principle of MySQL index this short content is what you want.

The principle of Index & essence

MySQL official explanation: index is a data structure for MySQL to improve the efficiency of obtaining data, in order to query data quickly. An index is a data structure that satisfies a specific search algorithm, and these data structures point to the data in some way, so as to find the data efficiently.

B + tree

MySQL generally uses B + tree as its index structure, so what are the characteristics of B + tree?

If the tree degree is n, the upper limit of the pointer of each node is 2n+1.

Non-leaf nodes do not store data, only pointer indexes; leaf nodes store all data, not pointers

A sequential access pointer is added to the classical B+ tree, and each leaf node has a pointer to the next adjacent leaf node, as shown in the figure. The main purpose is to improve the performance of interval access, for example, to find all the data with a key of 20 to 50, as long as all the data nodes are accessed at once according to the sequential access route.

B + Tree Diagram with Sequential access

Locality principle and disk pre-reading

So why do database systems generally use B + trees as index structures instead of other structures such as red-black trees?

First of all, we should first introduce the principle of locality and the concept of disk pre-reading.

Generally speaking, the index itself is large and will not be all stored in memory, but will be stored on disk in the form of index files. Therefore, disk IO operations will occur in the process of index lookup data, and disk IO access is very slow relative to memory, so the index structure should minimize the number of disk IO access.

In order to reduce the disk IO, the disk often carries out data pre-reading, which starts from a certain location and reads a certain length of data in advance and backward into memory, that is, the locality principle. Because sequential disk reads are more efficient and do not require seek time, IO efficiency can be improved.

The pre-read length is generally an integral multiple of the page, and the main memory and disk exchange data in pages as units. When the data to be read is not in memory, a page fault interrupt is triggered, and the system sends a request to the disk to read the disk data. The disk finds the starting position of the data and continuously reads one or more pages of data back into memory, and then interrupts and returns. The system continues to run. In general, the size of the Btree node is set to one page when the database system is designed, so that each node only needs to be loaded once IO.

After reading this article on what is the principle of MySQL indexing, many readers will want to know more about it. For more industry information, you can 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.