Mysql-index data structure

1. Foreword:

In our lives, we export applications that can see the index effect, such as train schedules viewed at train stations, dictionary directories, etc. Their function is the function of indexes. They filter out the final desired results by continuously narrowing the scope of data to be obtained, and at the same time turn random events into sequential events, that is, we always use the same search method to lock Data (A-Z lookup of dictionary).

Life example-taking a train: I go to take a train back to my hometown. If there is no train schedule when I want to take the train, the worst result is that I have to go to every train stop to find the train I want to take; but there is With the timetable, I can quickly know where the train I want to go stops, and I can go directly there instead of going one by one to see if the train I want to go to, thus speeding up my visit. This train schedule is the index of the database.

2. Disk Principle:

This part has a lot of text and theory, and it gives me a headache just to read it. You can read it if you are interested. It doesn’t matter if you are not interested. When reading the following chapters, just remember one conclusion of this part:

Read data as much as possible [reduce the number of I/O interactions with the operating system].

Okay, if you are not interested, you can skip it and go to the next part.

The database implementation is relatively complex. The data is stored on the disk. In order to improve performance, part of the data can be read into the memory for calculation each time, because we know that the cost of accessing the disk is about 100,000 times that of accessing the memory. Or so, so a simple search tree is difficult to meet complex application scenarios. Accessing the disk was mentioned earlier, so here is a brief introduction to disk IO and pre-reading. Reading data from the disk relies on mechanical movement. The time spent each time reading data can be divided into three categories: seek time, rotation delay, and transmission time. Part,
a)·Seek time: the time required for the magnetic arm to move to the specified track, mainstream disks are generally less than 5ms; b) Rotation delay: it is the disk speed we often hear, such as a disk 7200 rpm, It means it can rotate 7200 times per minute, which means it can rotate 120 times per second, and the rotation delay is 1/120/2 = 4.17ms; c). Transmission time: refers to reading from the disk or writing data to the disk The time is generally a few tenths of a millisecond, which is negligible compared to the first two times.
(I have read a very detailed article: http://wdxtub.com/2016/04/16/thin-csapp-3/)

Then the time it takes to access a disk is a disk IO The time is approximately equal to 5+4.17 = 9ms, which sounds pretty good, but you must know that a 500-MIPS (Million Instructions Per Second) machine can execute 500 million instructions per second, because Instructions rely on the nature of electricity. In other words, 400,000 instructions can be executed in one IO execution time. The database often contains hundreds of thousands, millions or even tens of millions of data. Each time it takes 9 milliseconds, it is obviously a disaster.

So, conclusion: Reduce the number of operating system I/O interactions.

(We call the data read by IO each time a page. The specific size of data on a page depends on the operating system, usually 4k or 8k, that is, we read the data in a page. When data is collected, only one IO actually occurs)

3. What is an index:

During the use of the database system, data query is the most frequently used data operation.

The most basic query algorithm is of course linear search. It traverses the table and then matches row by row whether the row value is equal to the keyword to be searched. Its time complexity is O(n). However, algorithms with a time complexity of O(n) can also achieve good performance with small tables and lightly loaded databases. But when the data increases, the algorithm with a time complexity of O(n) is obviously bad, and the performance drops quickly.

Fortunately, the development of computer science has provided many better search algorithms, such as binary search and binary search. tree search) etc. If you do a little analysis, you will find that each search algorithm can only be applied to a specific data structure. For example, binary search requires that the retrieved data be ordered, while binary tree search can only be applied to binary search trees, but the data itself The organizational structure cannot completely satisfy various data structures (for example, it is theoretically impossible to organize both columns in order at the same time), so in addition to the data, the database system also maintains data structures that satisfy specific search algorithms. Structures reference (point to) data in some way, allowing advanced search algorithms to be implemented on these data structures. This data structure is an index.

4. MySQL’s B-Tree index (technically B+Tree)

Okay, here comes the core of this article!

In MySQL, there are four main types of indexes, namely: B-Tree index, Hash index, Fulltext index and R-Tree index. We mainly analyze B-Tree indexes. (B: balance means balance, not binary tree)

1. Detailed explanation of b+ tree data structure

The picture above is a b+tree, (under the innodb engine, it is different from the B+ structure under the myisam engine. To put it bluntly, it is the difference between clustered index and non-clustered index. For details, see:

Mysql-Clustered Index

The light blue block is called a disk block. You can see that each disk block contains several data items (shown in dark blue, range: [(M /2)-1, M-1] M is the total data) and pointers (shown in yellow). For example, disk block 1 contains data items 17 and 35, including pointers P1, P2, and P3. P1 represents disk blocks less than 17. P2 represents disk blocks between 17 and 35, and P3 represents disk blocks greater than 35. The real data exists in leaf nodes, namely 3, 5, 9, 10, 13, 15, 28, 29, 36, 60, 75, 79, 90, 99. Non-leaf nodes do not store real data (a characteristic of B+), but only data items that guide the search direction. For example, 17 and 35 do not actually exist in the data table.

##2.B+ tree search process

As shown in the figure, if you want to find data item 29, then disk block 1 will first be loaded from the disk to the memory, and this will happen once IO, use binary search in memory to determine 29 between 17 and 35, lock the P2 pointer of disk block 1, the memory time is negligible because it is very short (compared to the IO of the disk), pass the P2 pointer of disk block 1 to the disk The address loads disk block 3 from disk to memory. The second IO occurs. 29 is between 26 and 30. The P2 pointer of disk block 3 is locked. Disk block 8 is loaded into the memory through the pointer. The third IO occurs. At the same time, the memory Do a binary search and find 29, end the query, a total of three IOs

The real situation is that a 3-layer b+ tree can represent millions of data. If millions of data are searched, only three IOs are needed. The performance improvement will be huge. If there is no index, one IO will occur for each data item, so a total of millions of IOs will be required. Obviously, the cost is very, very high. (Question???, as mentioned above. As mentioned above, INNOBD's B+ tree is a clustered index type, and the real data is placed together with the index leaf nodes. So the question is, if I have multiple indexes, is it possible that there is data stored under each index? Waste of disk storage? If not, I guess it uses a pointer to point to the past. How to express it in a data structure? )

Answer: Each table can only have one clustered index, but there can be multiple. Auxiliary index. The auxiliary index is also a secondary index. The root node stores not data but a pointer pointing to the primary index where the data is stored.

3.b+Tree properties

1). From the above analysis, we know that the number of IOs depends on b + the height h of the number. Assume that the data in the current data table is N, and the number of data items in each disk block is m, then h=㏒(m+1)N, when When the amount of data N is constant, the larger m is, the smaller h is; while m = The size of the disk block/the size of the data item. The size of the disk block is the size of a data page, which is fixed. If the space occupied by the data item is smaller, the number of data items is more, and the height h of the tree is lower. There is also less I/O. This is why each data item, that is, the index field, must be as small as possible.

As a negative example, int occupies 4 bytes, which is half less than bigint 8 bytes. This is why the b+ tree requires real data to be placed in leaf nodes instead of inner nodes. Once placed in inner nodes, the data items of the disk blocks will drop significantly (see the principle in Part 2 above), causing the tree to increase in height. When the data item is equal to 1, it will degenerate into a linear table. As follows:

If it is the structure on the left, the number of I/Os is three times; if it is the linear table on the right, the number of I/Os is 6 times. It is obvious that the IO changes There are more

Mapping two conclusions:

1. The field len to be set as an index must be small;

2. Do a union When indexing, the number of combined fields should also be less

2). When the data items of the b+ tree are composite data structures ( Multi-column index), such as (name, age, sex), b+ numbers are used to build the search tree in order from left to right.

For example, when data like (Zhang San, 20, F) is retrieved, the b+ tree will first compare the name to determine the next search direction. If the names are the same, age and sex will be compared in turn, and finally The retrieved data is obtained; but when data without name such as (20, F) comes, the b+ tree does not know which node to check next, because name is the first comparison factor when building the search tree, and it must be Search based on name first to know where to search next.

For example, when retrieving data like (Zhang San, F), the b+ tree can use name to specify the search direction, but the next field age is missing, so it can only retrieve the data whose name is equal to Zhang San. Find and then match the data whose gender is F. This is a very important property, that is, the leftmost matching characteristic of the index.

Map two conclusions:

1. The leftmost matching feature, the joint index is read from left to right

2. If there is a multi-column index, then the index from left to right does not need to be established (a,b,c), then (a), (a,b) does not need to be established

3. More conclusions : Mysql-index summary http://blog.csdn.net/ty_hf/article/details/53526405

The above is the content of Mysql-index data structure. For more related content, please pay attention to the PHP Chinese website (www.php.cn)!