Mysql > select B+ tree (top); mysql > select B+ tree (top); mysql > select B+ tree (top);
- Why is the index stored on hard disk
First, understand a few concepts. The server stores memory and hard disk. The size of memory is very small compared to hard disk. Memory access is nanosecond fast, while hard disk access is slow compared to memory.
The operating system reads only one page of data for each access to the disk or memory. A page of data is about 4 KB. The operation of reading data from the disk is called disk I/O.
Mysql index is not stored in memory. It is fast to access memory, but the memory is usually small and does not hold much data. In addition, mysql needs to keep data persistent.
- How to make binary search tree support interval query
The binary search tree was mentioned in the previous article. In order to make the binary search tree also support interval query, we connect the leaf nodes of the binary tree through a bidirectional linked list, and the list is ordered. Note that the leaf nodes are different from ordinary nodes, and pay attention to the following figure.
Therefore, we only need to find the position of the starting value of the interval in the linked list, and then iterate until we reach the end value of the interval to complete the interval query. Find the data in the range 7-30 as shown below.
- How to improve query speed
Because the binary search tree is stored in the hard disk, every time we visit a node, it corresponds to a hard disk IO operation. As mentioned above, it is slow to read data from the hard disk. Therefore, the height of the tree represents the number of DISK I/O operations, so we need to find a way to reduce the height of the tree to reduce disk I/O.
To make the tree shorter, put more forks into the tree and make it a multi-fork tree. Let’s store 16 pieces of data in a binary tree and a quintuple tree, and see how the height of the tree changes.
The root node is stored in memory, while common nodes and leaf nodes are stored in disks. Therefore, the height of a binary tree is 5 and requires 5 DISK I/OS, while the height of a five-tree is 2, and it takes only 2 DISK I/OS to query a data.
Of course, this is only a small data example, if there are 100 million data, we build a 100-fork tree, the height of the tree is only 3, so the multi-fork tree can greatly reduce the DISK I/O, improve the query speed.
So the question is, for the same amount of data, is it better to build a multi-fork tree with as many forks as possible, because the more forks, the lower the height of the tree.
As mentioned above, the operating system accesses disks by data page size. Each I/O reads only one data page size. If the data to be read is larger than one data page, multiple I/OS will occur. Therefore, we try to make the data size of each node exactly equal to the size of a data page, that is, each node is accessed only once IO.
- What about inserting and deleting data
Mysql > insert and delete mysql > insert and delete mysql > insert and delete mysql > insert and delete
Here we call the multi-fork tree m-fork tree. The M value is calculated by the data page size and the number of nodes. Try to ensure that each node visited is the size of a data page, and each node has at most M child nodes.
Now we need to insert new data into the database, that is, we need to insert new nodes into the M-tree, which may cause the number of children of some nodes to be larger than M, which will cause the size of the node to be larger than one data page, and it will take many IO to access the node.
To solve this problem, the m-tree will split the node into two nodes, and then the operation will cause the number of children of the parent node to exceed M. We will split the node again in the same way, until the root node is affected.
Delete operation is a similar idea. If nodes are frequently deleted, some nodes will have too few children, which will waste storage space and reduce query efficiency. Therefore, it is necessary to find a way to merge these nodes, which may cause the number of child nodes to exceed M, and then use the above splitting method to split the child nodes.
That’s all you have to say about node splitting and merging, and I don’t have to draw a picture, but it’s good to know the idea.
Here’s a summary of B+ trees:
B+ tree is a kind of multi-fork tree, which is constantly evolved from binary search tree. In order to satisfy the interval fast query, the leaf nodes of B+ tree are connected in series by bidirectional linked list.
Bidirectional lists are used to support sequential and reverse queries. Although bidirectional lists waste twice as much pointer space as unidirectional lists, this space is almost insignificant in hard disk, and it is worth exchanging time for space.
The number of child nodes in a B+ tree should not exceed m and should not be less than M /2. If the number of child nodes exceeds m, the tree should be split and if the number of child nodes is less than M /2, the tree should be merged.
This is why mysql InnoDB engine chose B+ tree. The image is from geek Time’s Beauty of Data Structures and Algorithms. If you have any questions about the article, you are welcome to leave a message. If the article has improper description, you are also expected to criticize it. If the article is helpful to you, click a “like” and then go, thank you for your support.