Mysql index basic principles

Locality principle

In order to understand the underlying principle of mysql indexing, you must know the local principle. In order to read data from disk, the user must pass through disk I/O. As we all know, I/O reads disk data are time-consuming. To improve the read efficiency, you must reduce THE I/O count. Disk read data, therefore, is not as required reading, but every time to proofread a part of the data, even if only one byte, disk will begin from the bytes, length of data read back into memory Behind this part of the read data is not redundant, because after scientists experiment, a data to be used by that time, Near its data can be used normally, this is the principle of locality Because of the high efficiency of the order of the disk read (for mechanical drive, once you find the data, after its near the data read do not need to seek, the rotation of the little time), so for the application of the principle of locality, disk read ahead can improve the efficiency of the IO. Therefore, the operating system reads disks in the unit of pages. The size of a page is usually 4K. An I/O operation usually reads an integer multiple of the page

select * from user where name='zhangsan';
Copy the code

Why don’t indexes be stored in binary or red-black trees

Because the index itself is very big, so the index is often in the form of index files stored on disk, in this case, the index lookup can produce disk IO consumption, more memory lookup, disk IO on the higher consumption of several orders of magnitude, so the evaluation of a data structure to store the index in the process of the pros and cons of important indicators is to find the number of disk I/o

Data structures such as binary trees and red-black trees are stored on disk. Nodes that are logically close to each other may actually be too far apart to take advantage of the locality principle. Therefore, it takes one IO to read a node. Using red-black trees to store data, even a small amount of data will make the tree too deep, requiring many I/OS, so this data structure is not suitable

B+ tree advantage

B + Tree is an optimization on B Tree. The optimization is as follows:

• Non-leaf nodes do not store data. The advantage of this is that non-leaf nodes can store more Pointers and keys, which will split the data into more data segments, reducing the depth of the tree and speeding up retrieval
• A bidirectional linked list is established between disk blocks of leaf nodes, which conforms to the preread feature of disk and is more suitable for scope and paging search
• If a key and pointer are 10B and a disk block is 16K, a disk block can store 1600 keys and Pointers, and 1600 * 1600 data can be indexed in two IO. Therefore, millions of data can be indexed in three IO, which is very efficient

MyISAM index implementation

MyISAM storage engine also uses B+ tree to store indexes, but its index files and data are separate, and the leaf nodes in the index store the address of the actual data, so this kind of index is called non-clustered index





In MyISAM, there is no difference in storage structure between a primary key index and a normal index, except that a primary key index requires a unique primary key, while a normal index can be repeated