浅析MysQL B-Tree 索引

B-Tree 索引

不同的存储引擎也可能使用不同的存储结构，i如，NDB集群存储引擎内部实现使用了T-Tree结构存储这种索引，即使其名字是BTREE；InnoDB使用的是B+Tree。

B-Tree通常一位这所有的值都是按顺序存储的，并且每一个叶子页道根的距离相同。下图大致反应了InnoDB索引是如何工作的。

为什么mysql索引要使用B+树，而不是B树，红黑树

看完上面的文章就可以理解为何B-Tree索引能够快速访问数据了。因为存储引擎不再需要进行全表扫描获取需要的数据，叶子节点包含了所有元素信息，每一个叶子节点指针都指向下一个节点，所以很适合查找范围数据。

索引对多个值进行排列的依据是CREATE TABLE 语句中定义索引时的顺序。

那么，索引排序的规则就是按照 last_name ,first_name ,dob 的顺序来的。

可以使用 B-Tree 索引的查询类型
B-Tree索引适用于全键值、键值范围或键前缀查找。
键前缀查找只是用于根据最左前缀查找。

举个粒子：

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 )
);

这个表的索引如下：

type结果

type结果值从好到坏依次是：

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

一般来说，得保证查询至少达到range级别，最好能达到ref，否则就可能会出现性能问题。

possible_keys：sql所用到的索引

key：显示MySQL实际决定使用的键（索引）。如果没有选择索引，键是NULL

（1）全值匹配
全值匹配指的是和索引中的所有列进行匹配。

例如上面的People表的索引（last_name,first_name,dob）可以用于查找last_name='Cuba Allen',first_name='Chuang',dob='1996-01-01'的人。这就是使用了索引中的所有列进行匹配，即全值匹配。

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  <-----可以看到这个key就是我们定义的索引
  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）匹配最左前缀
可以只使用索引的第一个列进行匹配。

例如可以用于查找last_name='aaa'的人，即用于查找姓为Zeng的人，这里只使用了索引的最左列进行匹配，即匹配最左前缀。

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  <----使用了索引
  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）匹配列前缀
可以只匹配某一列的值的开头部分。

例如可以用于查找last_name LIKE ‘a％'的人，即用于查找所有以Z开头的姓的人，这里只使用了索引最左列的前缀进行匹配，即匹配列前缀。

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   <---使用了索引
  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）匹配范围值
可以只适用索引的第一列查找符合某个范围内的数据。

例如可以用于查找last_name BETWEEN ‘aaa' AND ‘aaabbbccc'的人，即用于查找姓在aaa和aaabbbccc之间的人，这里只使用了索引最左列的前缀进行范围匹配，即匹配范围值。

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  <---使用了索引
  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）精确匹配某一列并范围匹配另外一列
可以使第一列全匹配，第二列范围匹配。

例如可以用于查找last_name='aaa' AND first_name LIKE 'b％'的人，即用于查找姓是Zeng，名字以C开头的人，这里使用了索引的最左列精确匹配，第二列进行范围匹配。

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  <---使用了索引
  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）只访问索引的查询
查询只需访问索引，而无须访问数据行。

例如select last_name, first_name where last_name='aaa'; 这里只查询索引所包含的last_name和first_name列，则无须读取数据行。

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

B-Tree 的限制

（1）只能按照索引的最左列开始查找。
例如People表中的索引无法用于查找first_name为'bbb'的人，也无法查找某个特定生日的人，因为这两个列都不是最左数据列。

（2）只能按照索引最左列的最左前缀进行匹配。
例如People表中的索引无法查找last_name LIKE ‘％b'的人，虽然last_name就是此索引的最左列，但MySQL索引无法查找以‘b'结尾的last_name的记录。

（3）只能按照索引定义的顺序从左到右进行匹配，不能跳过索引中的列。
例如People表中的索引无法用于查找last_name='a' AND bod='1996-01-01'的人，因为MySQL无法跳过索引中的某一列而使用索引中最左列和排在末尾的列进行组合。如果不指定索引中中间的列，则MySQL只能使用索引的最左列，即第一列。

（4）如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。
例如有这样一个查询：where last_name='a' AND first_name LIKE 'b％' AND dob='1996-01-01'; 这个查询只能使用索引的前两列，因为这里LIKE是一个范围条件，则first_name后面的索引列都将失效。（优化点：尽量不要在索引列中使用LIKE等范围条件，改用多个等于条件来替代，保证后面的索引列能生效。）

来源：https://segmentfault.com/a/1190000038243722?utm_source=tuicool&utm_medium=referral