Brief Analysis of MySQL B-Tree Index

B-Tree Index

Different storage engines may also use different storage structures. For example, the NDB cluster storage engine internally uses a T-Tree structure to store this index, even though its name is BTREE; InnoDB uses a B+Tree.

B-Tree usually stores all values ​​in order, and each leaf page has the same distance to the root. The following diagram roughly reflects how InnoDB indexes work.

Why does MySQL use B+ tree instead of B tree or red-black tree for index?

After reading the above article, you can understand why B-Tree index can quickly access data. Because the storage engine no longer needs to perform a full table scan to obtain the required data, the leaf node contains all element information, and each leaf node pointer points to the next node, so it is very suitable for searching range data.

The index arranges multiple values ​​according to the order in which they are defined in the CREATE TABLE statement.

Then, the index sorting rule is in the order of last_name, first_name, dob.

Types of queries that can use B-Tree indexes
B-Tree indexes are suitable for full key value, key value range, or key prefix lookup.
Key prefix search is only used to search based on the leftmost prefix.

Take a particle:

CREATE TABLE People (
  last_name VARCHAR ( 50 ) NOT NULL,
  first_name VARCHAR ( 50 ) NOT NULL,
  dob date NOT NULL,
  gender enum ( 'm', 'f' ) NOT NULL,
KEY ( last_name, first_name, dob ) 
);

The index of this table is as follows:

type result

The type result values ​​from best to worst are:

system > const > eq_ref > ref > fulltext > ref_or_null > index_merge > unique_subquery > index_subquery > range > index > ALL

Generally speaking, you must ensure that the query reaches at least the range level, preferably the ref level, otherwise performance issues may occur.

possible_keys: index used by sql

key: Shows the key (index) that MySQL actually decided to use. If no index is selected, the key is NULL

(1) Full value matching Full value matching refers to matching all columns in the index.

For example, the index (last_name, first_name, dob) of the People table above can be used to find people whose last_name = 'Cuba Allen', first_name = 'Chuang', dob = '1996-01-01'. This means that all columns in the index are used for matching, that is, full value matching.

mysql> EXPLAIN select * from People where last_name = 'aaa' and first_name = 'bbb' and dob='2020-11-20' \G;
*************************** 1. row ***************************
     id: 1
 select_type: SIMPLE
    table: People
 partitions: NULL
    type: ref
possible_keys: last_name
     key: last_name <-----You can see that this key is the index we defined key_len: 307
     ref: const,const,const
    rows: 1
  filtered: 100.00
    Extra: NULL
1 row in set, 1 warning (0.00 sec)

ERROR: 
No query specified

(2) To match the leftmost prefix, you can use only the first column of the index.

For example, it can be used to find people whose last_name='aaa', that is, to find people whose last name is Zeng. Here, only the leftmost column of the index is used for matching, that is, matching the leftmost prefix.

mysql> EXPLAIN select * from People where last_name = 'aaa' \G;
*************************** 1. row ***************************
     id: 1
 select_type: SIMPLE
    table: People
 partitions: NULL
    type: ref
possible_keys: last_name
     key: last_name <----Index used key_len: 152
     ref: const
    rows: 3
  filtered: 100.00
    Extra: NULL
1 row in set, 1 warning (0.00 sec)

ERROR: 
No query specified

(3) Matching a column prefix can only match the beginning part of the value of a column.

For example, it can be used to find people whose last_name LIKE 'a%', that is, to find all people whose last names begin with Z. Here, only the prefix of the leftmost column of the index is used for matching, that is, matching the column prefix.

mysql> EXPLAIN select * from People where last_name = 'a%' \G;
*************************** 1. row ***************************
     id: 1
 select_type: SIMPLE
    table: People
 partitions: NULL
    type: ref
possible_keys: last_name
     key: last_name <---index used key_len: 152
     ref: const
    rows: 1
  filtered: 100.00
    Extra: NULL
1 row in set, 1 warning (0.00 sec)

ERROR: 
No query specified

(4) To match a range value, you can use only the first column of the index to search for data that falls within a certain range.

For example, it can be used to find people whose last_name is between 'aaa' and 'aaabbbccc'. Here, only the prefix of the leftmost column of the index is used for range matching, that is, matching the range value.

mysql> EXPLAIN select * from People where last_name BETWEEN 'aaa' and 'aaabbbccc'\G;
*************************** 1. row ***************************
     id: 1
 select_type: SIMPLE
    table: People
 partitions: NULL
    type: range
possible_keys: last_name
     key: last_name <---index used key_len: 152
     ref: NULL
    rows: 3
  filtered: 100.00
    Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

ERROR: 
No query specified

(5) Exactly matching a column and range matching another column can result in a full match of the first column and a range match of the second column.

For example, it can be used to find people with last_name='aaa' AND first_name LIKE 'b%', that is, to find people whose last name is Zeng and whose first name starts with C. Here, the leftmost column of the index is used for exact matching, and the second column is used for range matching.

mysql> EXPLAIN select * from People where last_name = 'aaa' and first_name like 'b%'\G;
*************************** 1. row ***************************
     id: 1
 select_type: SIMPLE
    table: People
 partitions: NULL
    type: range
possible_keys: last_name
     key: last_name <---index used key_len: 304
     ref: NULL
    rows: 1
  filtered: 100.00
    Extra: Using index condition
1 row in set, 1 warning (0.00 sec)

ERROR: 
No query specified

(6) Queries that only access indexes: Queries only need to access indexes without accessing data rows.

For example, select last_name, first_name where last_name='aaa'; here only the last_name and first_name columns included in the index are queried, so there is no need to read the data rows.

mysql> explain select last_name,first_name,dob from People where last_name = 'aaa'
*************************** 1. row ***************************
      id: 1
 select_type: SIMPLE
    table: People
  partitions: NULL
     type: ref
possible_keys: last_name
     key: last_name
   key_len: 152
     ref: const
     rows: 1
   filtered: 100.00
    Extra: Using index
1 row in set, 1 warning (0.00 sec)

ERROR: 
No query specified

Limitations of B-Trees

(1) You can only search by starting from the leftmost column of the index.
For example, the index in the People table cannot be used to find people whose first_name is 'bbb', nor can it be used to find people with a specific birthday, because neither of these columns is the leftmost column.

(2) Only the leftmost prefix of the leftmost column of the index can be matched.
For example, the index in the People table cannot find people whose last_name LIKE '%b'. Although last_name is the leftmost column of this index, the MySQL index cannot find records with last_name ending with 'b'.

(3) Matching can only be performed from left to right in the order defined by the index, and columns in the index cannot be skipped.
For example, the index in the People table cannot be used to find people with last_name='a' AND bod='1996-01-01', because MySQL cannot skip a column in the index and use the leftmost column and the last column in the index for combination. If you do not specify the middle column in the index, MySQL can only use the leftmost column of the index, that is, the first column.

(4) If a query contains a range query on a column, all columns to the right of it cannot use index optimization to find them.
For example, there is a query like this: where last_name='a' AND first_name LIKE 'b%' AND dob='1996-01-01'; This query can only use the first two columns of the index, because LIKE is a range condition here, and the index columns after first_name will be invalid. (Optimization point: Try not to use range conditions such as LIKE in the index column. Use multiple equal conditions instead to ensure that the subsequent index columns can take effect.)

The above is a brief analysis of the details of MysQL B-Tree index. For more information about MysQL B-Tree index, please pay attention to other related articles on 123WORDPRESS.COM!