An index is actually a data structure. In a database, the ratio of reads and writes is 10:1, so if every lookup is a full table lookup, it will be very inefficient. Therefore, this article will explain the MySql index step by step according to the title.

##B tree and B+ tree B tree and B+ tree is a data structure in the frequency of the very high model, in the author’s previous blog, there are binary search tree and binary balance tree have been explained and code analysis, but those are used more trees in the program, in the database, the data is relatively large, Multipath search tree is obviously more suitable for database application scenarios, next we will introduce these two kinds of multipath search tree, after all, as a programmer, the heart does not point B tree how can line?

B tree: A B tree is a B-tree, which has the following properties:

B trees are different from binary trees in that one node can store multiple keywords and Pointers to multiple subtrees, which is also the characteristic of B+ trees. A b-tree of order m requires that all non-leaf child nodes except the root node must have [M /2,m] child trees. The root node must have only two subtrees, of course, if the root node has only one node; B tree is a binary search tree, much like a binary search tree, in that the earlier the subtree, the smaller, and within the same node, keywords are sorted by size; A node of B tree requires that the number of subtrees is equal to the number of keywords +1;Copy the code

Well, without further ado, let’s look at the model of a B tree:



Since B trees place all search keys in the nodes, the search is very much like a binary search, for example, E:

First, the left subtree is found through the root node, and then the left subtree is traversed sequentially, and E is found between F and J, so the leaf node is searched. After the keyword is traversed sequentially, E can be returned. If E is not found, it means that it is not found.

B + tree

B+ tree = index + tree = index + tree = index + tree = index + tree = index + tree

B+ tree puts all the search results in the leaf node, which means that if you search B+ tree, you have to go to the leaf node to return the results. The number of keywords in each node of B+ tree is the same as the number of Pointers in the subtree. Each key of the non-leaf node of the B+ tree corresponds to a pointer, and the key is the maximum or minimum value of the subtree. Take a look at the model:

Its search is also crude, much like that of a B-tree, except that it finds objects in leaves, like rabbits:

The first step is smaller than the horse, it will find his subtree, the second step is smaller than the dragon, it will find his subtree, and finally hit the target in the keyword in the leaf node.

So how does MySql leverage this data structure?

There are two common storage engines in MySql

MySql of course has more than two search engines, but the B+ tree index is used by the next two storage engines, Innodb and Myisam.

Innodb storage engine

Innodb uses B+ tree, which has two kinds of indexes: primary key index and secondary index. Primary key index is the index when generating primary key. Its leaf node stores data rows, so it is also called clustered index.

The other kind of index, the secondary index, is artificially created by us. Its leaf node stores the primary key. When we find the primary key through the secondary index, we find the primary key through the primary key.

MyIsam storage engine

MyIsam will no longer be able to use clustered indexes. Although it uses a B+ tree, its primary key index is no different from the secondary index, which stores the physical address of the data row in the leaf.

The difference between

1. Innodb supports transactions and the default is Autocommit, so every SQL statement is wrapped as a transaction. If multiple transactions are executed, it is better to add begin and COMMIT. MyIsam does not support transactions and therefore cannot be rolled back;

Innodb also supports row locking. MyIsam locks all tables for write operations, so MyIsam’s write operation performance will be poor.

3. Therefore, it is better to use MyIsam and Innodb for more tables.

Extension – compound index

We all know we can create an index on a column, but what is a compound index?

Create:

create table test(
a int,
b int,
c int,
KEY a(a,b,c)
);
Copy the code

With the above code we can create a composite index for a, B, and C. The overhead of maintaining a composite index is lower than that of maintaining three indexes.

However, a composite index must meet a left-most matching principle, that is, it will search a, B, and C in sequence. If the left field is not used as a judgment condition, it will not execute the following index:

EXPLAIN DELETE from test
where  a=1 and c= 3 and b =2 
Copy the code

EXPLAIN DELETE from test
where  a=1 and c= 3 
Copy the code