Author: Wang Xinhua

Why is an index needed? In a nutshell: Indexing is really to improve the efficiency of data query.

I. Index common models

Model: Hash tables, ordered arrays, and search trees

Hash table

  • Hash table is a kind of key-value storage data structure, we just enter the key to be looked up is the key, we can find its corresponding value is the value. The idea of hashing is very simple. You put the value in an array, use a hash function to convert the key to a certain position, and then put the value in that position in the array. Time complexity: 0(1)
  • Highlight: If the index values are duplicated, a hash collision will occur. This resolves the hash collision, but results in a less efficient query.
  • Scenario: The hash table structure is suitable for scenarios where there are only equivalent queries, not for lookup scopes. Similar to Redis Memcached and some other NoSQL engines.

Search tree

Before we know about search trees we need to know about binary trees, balanced binary trees, B trees, and B+ trees

Recommend a tool can clear understanding of the principle of the tree: https://www.cs.usfca.edu/~gal…

Binary tree

Binary tree properties: the key of the left subtree is less than the key of the root, and the key of the right subtree is greater than the key of the root.

The figure below is a binary tree

The current binary tree insertion order is: 3, 2, 4, 1, 5

If we insert it in the order 1, 2, 3, 4, 5, we get a binary tree that looks like this



If this is the binary tree query efficiency is too low. If the query efficiency of binary tree is as high as possible, the binary tree needs to be balanced, which leads to the new definition – balanced binary tree or AVL tree.

Balanced binary trees

Balanced binary tree features:

  • It satisfies the property of binary tree
  • The maximum height difference between two subtrees of any node is 1

After the above two combinations is the balanced binary tree, as shown in the figure below

When inserting the tree in the following order: 1, 2, 3, 4, 5, 6, 7, 8, the content is generated as shown in the figure, which is different from the completion in the figure 2. When generating the figure through the tool, it is obvious that no matter how the node data is inserted, it can meet the characteristics of balanced binary tree 2.

The AVL tree can also be satisfied when one node is removed, as shown in the figure below after the five nodes in Figure 3 are deleted.

So just to summarize the advantages of balanced binary trees

  • A good lookup performance (O (logn)), there is no extremely inefficient lookup.
  • B can realize range search, data sorting.

It looks like an AVL tree is a great data structure for data lookup, but AVL trees are not suitable for indexing MySQL databases, because consider this question:

Database query is the bottleneck of data disk IO, if you are using the AVL tree, each and every one of us data store only a tree node, a disk I/o we can only take one node of the data is loaded into the memory, that such as query id = 8 this data we are going to disk IO three times, this is very time consuming. So when we design a database index, we need to first consider how to minimize the number of disk IO.

A has a characteristic, disk I/o is read from disk 1 B and 1 KB data the time consumed is basic same, we can according to this idea, we can as much as possible on a tree node storing data, a disk I/o load more data to the memory, this is the B tree, the design principle of B + tree.

b-tree

B tree features:

  • All health values are distributed throughout the tree
  • The search may end at a non-leaf node
  • The root node has at least 2 subtrees
  • All the leaf nodes are on the same layer
  • The number of forks (ways) is always 1 more than the number of keywords
  • Nodes store keys and values

Demonstrates splitting and merging of B-tree indexes

For example, when Max Degree is 3, we insert data 1, 2, 3. When we insert 3, it should be in the first disk block, but if a node has three keywords, that means there are four Pointers, the child nodes will become four ways, so we have to split at this time. I’m going to take the data 2 in the middle, and I’m going to make 1 and 3 the children of 2.

If the node is deleted, there will be a reverse merge. Notice that this is splitting and merging, which is not the same as the AVL tree, which is left-handed and right-handed. So let’s go ahead and insert 4 and 5, and B Tree will split and merge again.



As you can see from this, there is a lot of index structure adjustment when updating indexes, node splitting and merging, which is InnoDB page splitting and merging.

B + tree

A B+ tree is an optimization done on a B tree

  • B+ trees can contain more node content per node. Why? The first is to reduce the height of the tree. The second is to change the data range into multiple intervals. The more intervals there are, the faster the retrieval speed will be
  • Non-leaf nodes store keys, leaf nodes store keys and data
  • The leaf node pointer is connected, so the sequential search is faster

What’s the difference between a B tree and a B+ tree?

First, a node in a B tree stores keys and data, while a B+ tree stores indexes (addresses), so a node in a B tree can’t store many data, but a node in a B+ tree can store many indexes, and a leaf node in a B+ tree stores all data.

Second, the leaf nodes of the B+ tree are linked together by a linked list in the data stage to facilitate range search.

By comparing B tree and B+ tree, we can see that B+ tree nodes store indexes. Under the condition of limited storage capacity of a single node, a single node can also store a large number of indexes, which reduces the height of the whole B+ tree and reduces disk IO. Second, the leaf nodes of the B+ tree are where the real data is stored. The leaf nodes are connected by a linked list, which is in itself ordered, making it more efficient to search within the data range. Therefore, MySQL uses B+ tree for index. B+ tree has very good performance in search efficiency and range search.

In summary, MySQL InnoDB selects B+ tree for index.

Question to consider

1, B+ tree leaves stored all the data, if 10 million data, then the linked list is too large, will not affect the performance?

You can use the data page, which is highlighted below

2. How many rows can InnoDB store in a B+ tree?

B+Tree does not store data in the root node and the branch node, only the leaf node stores data. Searching for a keyword will not be returned directly, but will go to the leaf node in the last layer. For example, if we search for id=3, even though it is a direct hit in the first layer, all the data is on the leaf node, so I have to continue to search until I reach the leaf child node. For example, if a record is 1K, a leaf node (a page) can store 16 records. How many Pointers can a non-leaf child store? Assume that the index field is of type BIGINT and is 8 bytes long. The pointer size is set to 6 bytes in the InnoDB source code, making a total of 14 bytes. Non-leaf nodes (one page) can store 1024* 16/14 = 1170 such cells (keys + Pointers), representing 1170 Pointers. When the tree depth is 2, there are 1170^2 leaf nodes, and the data that can be stored is: When looking up data, a page lookup represents an IO. That is to say, for a table of about 20 million, it needs to visit the disk three times at most to query data. So in InnoDB, the depth of B+ tree is usually 1-3 layers, and it can meet the data storage of tens of millions.

Second, InnoDB index analysis

In InnoDB, tables are stored in index form according to primary key order. This type of table is called index organized table.

Above we analyzed from different dimensions and finally InnoDB uses B+ tree index model, so all data is stored in B+ tree.

Each index in InnoDB corresponds to a B+ tree. Suppose we have a table with a primary key column of ID, a table with field k, and a regular index on k.

The construction sentence of this table is:

create table user(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;

The (ID,k) values in the first through fifth rows of the table are (100,1), (200,2), (300,3), (500,5), and (600,6), respectively. An example diagram of the two trees is shown below.

Above: Primary Health Index

Above: General index

Based on the above index structure description, let’s discuss a question: what is the difference between a query based on a primary key index and a normal index?

Select * from T where ID=500 select * from T where ID=500 select * from T where ID=500

SELECT * FROM T WHERE k=5 SELECT * FROM T WHERE k=5 SELECT * FROM T WHERE k=5 This process is called the return table. That is, a query based on a non-primary key index requires an extra index tree to be scanned. Therefore, we should try to use primary key queries in our applications.

In order to maintain index orderliness, the B+ tree needs to do the necessary maintenance when inserting new values. In the example shown in the diagram above, if you insert a new row with an ID value of 700, you simply insert a new record after the record in R5. As shown in figure

If the newly inserted ID value is 400, it will be relatively troublesome, and you need to logically move the data behind to make space, as shown in the figure.

Even worse, if the data page on which R5 is located is already full, according to the algorithm of B+ tree, a new data page needs to be applied at this time and part of the data needs to be moved to the past. This process is called page splitting. In this case, performance is naturally affected.

In addition to performance, page splitting operations affect the utilization of data pages. Data that used to be on one page is now split between two pages, reducing overall space utilization by about 50%. Of course, where there is division, there is merger.

When two adjacent pages are low in utilization due to the deletion of data, the data pages will be merged. The merging process can be considered as the reverse of the splitting process.

3. InnoDB data page

Page we mentioned in the above data, the concept of data pages, it is the basic unit of the MySQL storage space management, the size of a page is usually 16 KB, and we know that the record is being stored in the page, if the record line takes up too much space can also cause overflow phenomenon, this can lead to a record is stored separately in multiple pages.

The essence of pages is a block of 16KB of storage space. InnoDB divides pages into different types for different purposes. The pages for storing records are also called data pages. The 16KB storage space represented by the data page can be divided into several parts, and different parts have different functions, as shown in the figure:

As can be seen from the figure, the storage space of an InnoDB data page is divided into 7 parts, and each part can be divided into several small parts.

Let’s use the data page to analyze InnoDB index data.

We have a primary key index for example, each page default size 16 k, when we first page the user data area page when they are full of to apply for a new page is the second page Then there is the new data insert will be deposited in the second page of our user data such as shown in figure R4, involves the data retrieval of data in the page is similar to a linked list, Pages and pages are also linked lists, when the amount of data is large, in fact, the performance is relatively poor, this time we need to introduce the concept of page directory.

When there is a page directory after the retrieval performance will improve a lot, but if there are a lot of pages in fact, the performance will also have drawbacks, then how to deal with this time, at this time we need to add a linked list of page directory in the upper layer.