Definition 1.

Indexes are designed to improve the efficiency of data query, just like book catalogs.

2. Common models for indexing

Indexes appear to improve query efficiency, but there are many ways to achieve indexes, so the concept of index model is introduced here. There are many data structures that can be used to improve read and write efficiency. Here are some common data structures: hash table, ordered array, binary search tree.

2.1 a hash table

Hash table is a kind of key-value storage structure. As long as we input the key to be searched, we can find its corresponding value, namely value. The idea of hashing is very simple, you put the value in an array, you use a hash function to convert the key to a certain location, and then you put the value in that location in the array.

Inevitably, when multiple keys are converted to hash functions, the same value will occur. One way to handle this is to pull out a linked list.

Suppose you are maintaining a table of ID information and names and need to find the corresponding name based on id number. In this case, the corresponding hash index would look like this:

In the figure, User2 and User4 both have values of N based on their ID numbers, but it doesn’t matter, there’s a linked list. Suppose you want to find out what the name of ID_card_n2 is, and the way to do that is: first, you hash ID_card_n2 to find N; Then, iterate through in order to find User2.

The hash table structure is suitable for scenarios where there are only equivalent queries, not range queries, such as Memcached and some other NoSQL engines.

2.2 Ordered Array

Ordered arrays perform very well in both equivalent query and range query scenarios. Ordered arrays are a good data structure if you just look at query efficiency. However, when you need to update the data, the trouble is that you insert one record in the middle and have to move all the records behind it, which is too expensive.

If we use an ordered array, it looks like this:

We assume that the id numbers are not duplicated, and that the array is stored in ascending order. So if you want to look up the name of ID_card_n2, you can quickly get it by dichotomy, and it’s order log of N.

Therefore, ordered array indexes are only suitable for static storage engines

2.3 Binary search tree

Binary search trees are also classic data structures in textbooks. If we use a binary search tree to achieve the above example, the schematic diagram is as follows:

Binary search tree is characterized by: the value of all nodes in the left subtree of the parent node is less than that of the parent node, and the value of all nodes in the right subtree is greater than that of the parent node. So if you want to look up ID_card_n2, the search sequence is UserA -> UserC -> UserF -> User2. This is order log N.

Of course, in order to maintain order log(N) query complexity, you need to keep this tree balanced binary. And to do that, the update time is order log(N).

Imagine a balanced binary tree of 1 million nodes, 20 tall. A query may require access to 20 data blocks. In the days of mechanical hard disks, reading a block of data randomly from a disk took about 10 ms of addressing time. That is, for a 1 million row table, if stored in a binary tree, it might take 20 10 ms to access a single row, which is a really slow query.

In order for a query to read as little disk as possible, the query process must access as few blocks of data as possible. Then, instead of using binary trees, we should use “n-fork” trees. Here, the “N” in the “n-cross” tree depends on the size of the data block.

3. B tree and B+ tree

As mentioned above, in order to reduce disk I/O, the introduction of n-tree data structure, so let’s analyze B tree and B+ tree.

3.1 B tree

3.1.1 defines

A balanced tree of Order M is a balanced m-way search tree. It is either an empty tree or a tree that satisfies the following properties:

  • The root node has at least two children
  • Each node has m-1 keys and is arranged in ascending order
  • The values of the children of m-1 and M key are between the values of m-1 and M key
  • Other nodes have at least M/2 children

The following is a schematic diagram of a B-tree with M=4:

3.1.2 Characteristics of B-tree

  • The leaf nodes have the same depth and the pointer to the leaf node is null
  • All index elements are not duplicated
  • The data index in the node is arranged in ascending order from left to right
  • Both leaf and non-leaf nodes store indexes and data

3.1.3 Disadvantages of B tree

Since the leaf of B tree has no pointer, there is no pointer connection between leaf nodes, so the efficiency of range query is not high.

A page is the smallest unit of disk management in InnoDB. The default size of each page is 16KB, and the information related to the index is stored in the data page. Imagine if every node stores data, then suppose the index type is int. The corresponding data takes up 96 bytes, so this node takes up 104 bytes, so this page can save up to 16KB/100B = 160 nodes, so if the table has millions or even tens of millions of data, the tree height of the B tree is very terrible, when querying, there will be many more DISK I/O, so the B tree can not be used. So is there a better way? The answer from MySQL is an added version of the B+ tree.

Note: The 16KB here does not actually store node information, there is a lot of other information, and this is just a rough calculation.

3.2 B + tree

3.2.1 definition

B+ tree is a variant of B tree. The leaf nodes of B+ tree store keywords and corresponding recorded addresses, and the layers above the leaf nodes are used as indexes. A B+ tree of order m is defined as follows:

  • Each node has at most m children
  • Each node except the root has at least [m/2] children, and the root has at least two children
  • Nodes with k children must have k keywords

3.2.2 Characteristics of B+ trees

  • Non-leaf nodes do not store data, only indexes (redundant), and can store more indexes
  • The leaf node contains all index fields
  • Leaf nodes are connected by bidirectional Pointers to improve the performance of interval access

Going back to the example above, how many nodes can a page of a B+ tree store, assuming the index is of type int? We can calculate: 16KB/4B = 4000 nodes. That’s tens of times bigger.

So MySQL uses B+ trees instead of B trees in order to reduce disk access IO and improve range query performance.

4. B+ index in InnoDB

In InnoDB, tables are stored as indexes according to the order of primary keys, which are called indexed organized tables. As mentioned earlier, InnoDB uses a B+ tree index model, so data is stored in a B+ tree.

Each index in InnoDB corresponds to a B+ tree.

Suppose we have a table with a primary key column ID, a field K in the table, and an index on k. The construction sentence of this table is:


mysql> create table T(
id int primary key, 
k int not null, 
name varchar(16),
index (k))engine=InnoDB;
Copy the code

In the table, the (ID,k) values of R1~R5 are (100,1), (200,2), (300,3), (500,5) and (600,6) respectively. The schematic diagram of the two trees is as follows:

It is not difficult to see from the figure that, according to the content of the leaf node, the index type is divided into primary key index and non-primary key index.

Leaf nodes indexed by primary keys hold entire rows of data. In InnoDB, primary key indexes are also called clustered indexes.

Leaf node contents that are not primary key indexes are primary key values. In InnoDB, non-primary key indexes are also called secondary indexes.

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;
  • If the statement is select * from T where k=5, that is, the common index query mode, search the K index tree first, obtain the ID value 500, and then search the ID index tree. This process is called table back.

4.1 Index Maintenance

B+ trees need to perform necessary maintenance when inserting new values in order to maintain index order. So there are two problems, page splitting and page merging.

4.4.1 pages divided

In the example above, if you insert a new row with an ID of 700, you only need to insert a new record after the R5 record. If the newly inserted ID value is 400, it is relatively troublesome, and you need to logically move the following data to make space.

Even worse, if the data page R5 is on is already full, according to the B+ tree algorithm, it needs to apply for a new data page and move some data there. This process is called page splitting. In this case, performance naturally suffers.

In addition to performance, page splitting also affects data page utilization. Data originally placed on one page is now divided into two pages, reducing overall space utilization by about 50%.

4.1.2 pages

Page merge is the reverse of page splitting. When data is deleted, page merge may be triggered. To reduce this situation, it is recommended that the database do logical deletion rather than physical deletion.

4.1.3 Benefits of auto-increment primary keys

An AUTO_INCREMENT PRIMARY KEY is a PRIMARY KEY defined on an AUTO_INCREMENT column. NOT NULL PRIMARY KEY AUTO_INCREMENT is a PRIMARY KEY defined on an AUTO_INCREMENT column.

In other words, the auto-increment primary key insert mode fits the incremental insert scenario we mentioned earlier. Every time a new record is inserted, it is an append operation, which does not involve moving other records and does not trigger the splitting of leaf nodes.

However, the primary key of fields with business logic is not easy to ensure orderly insertion, so the cost of writing data is relatively high.

In addition to considering performance, we can also look at it from a storage perspective. If you do have a unique field in your table, such as a string id number, should you use id number as the primary key or increment field as the primary key?

Because every leaf node that is not a primary key index has a primary key value. The leaf node of each secondary index takes about 20 bytes if the id number is used as the primary key, but only 4 bytes if the integer key is used, and 8 bytes if the bigint is used.

Obviously, the smaller the primary key length, the smaller the leaf nodes of the normal index, and the smaller the space taken up by the normal index.

Therefore, auto-increment of primary keys is often a more reasonable choice for performance and storage.

5. Overwrite indexes

To avoid a back table, you can introduce an overwrite index. This means that all the required data can be found in the normal index, instead of searching the primary key index tree. Overwriting an index is an optimal case of a federated index.

5.1 Underlying data structures of federated indexes

5.2 Left-most Prefix Rule

  • An index can be as simple as one column (a) or as complex as multiple columns (A, B, C, D), known as a joint index.
  • If the index is a federated index, then the key is composed of multiple columns, and the index can only be used to check whether the key exists (equal). MySQL will continue to match to the right until it encounters a range query (>, <, between, like, left match).
  • Therefore, the order of the columns determines the number of columns that can be hit by the index.

Example:

If there are indexes (A,b,c, and d) and the query conditions are a=1 and B =2 and C >3 and d=4, a, B, and C will be matched on each node in sequence, but D will not be matched. (c is already a range query, d is certainly not sorted)

The resources

  1. MySQL > MySQL
  2. Falling in Love with An Interviewer Series – Database Index mp.weixin.qq.com/s/_9rDde9wR…
  3. InnoDB Storage Engine