Official account: Java Xiaokaxiu, website: Javaxks.com

Author: that_is_cool, link: blog.csdn.net/that_is_cool/article/details/81069945

Learning Java for more than a year, but never on the database to do a complete summary, whim set up such a web title, I hope not anticliactic bar, ha ha.

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 plus tree

B and B + tree is a data structure model of frequency is very high, in a few blog before, the writer has the balance of binary search tree and binary tree for explanation and code analysis, but those who are in the program to use more trees, in the database, the data quantity is relatively large, multipath search trees obviously more suitable for database application scenarios, We will introduce these two kinds of multi-path search trees. After all, as a programmer, how can you do without some B-tree in mind?

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

1. 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.

2. A b-tree of order M requires that all non-leaf child nodes except the root node must have [M /2,m] child trees;

3. The root node must have only two subtrees, of course, if there is only one root node;

4. B tree is a binary search tree, which is similar to a binary search tree. The earlier the subtree, the smaller the subtree.

5. A node of B tree requires that the number of subtrees be equal to the number of keywords + 1.

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

A fifth-order 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

1, B + tree puts all search results in the leaf node, which means that search B + tree, must go to the leaf node to return results;

2. The number of keywords in each node of the B + tree is the same as the number of Pointers in the subtree;

3. Each keyword of the non-leaf node of the B + tree corresponds to a pointer, and the keyword is the maximum or minimum value of the subtree;

Take a look at the model:

A third order B + tree

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.

The main index of InnoDB, where the leaves hold rows of data

Innodb secondary index, where leaves hold primary keys

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.

MyIsam Primary key index of the storage engine

MyIsam storage engine secondary index, store is also physical address

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

When a, B, and C are present, it continues to match the field on the right

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

When removing b, it is found that the composite index only matches up to A and does not match c