索引查找算法BTREE
BTREE查找算法演变B-TREE ：普通 BTREE，平衡多路查找树（B-Tree）B+TREE ：叶子节点双向指针B++TREE（B*TREE）：枝节点的双向指针
普通B-TREE
增强版B+TREE（B*TREE）
总结：从上图看出，在B+Tree上有两个头指针，一个指向根节点，另一个指向关键字最小的叶子节点，而且所有叶子节点（即数据节点）之间是一种链式环结构。B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构，InnoDB存储引擎就是用B+Tree实现其索引结构。从上图中的B-Tree结构图中可以看到每个节点中不仅包含数据的key值，还有data值。而每一个页的存储空间是有限的，如果data数据较大时将会导致每个节点（即一个页）能存储的key的数量很小，当存储的数据量很大时同样会导致B-Tree的深度较大，增大查询时的磁盘I/O次数，进而影响查询效率。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。而BTree，这个是以B+Tree为基础，在非叶子结点（枝节点）上增加了链表指针，BTree的空间利用率更高。
MySQL中如何使用BTREE
1 聚簇索引
聚簇索引也叫集群索引，聚集索引。它不是一种单独的索引类型，而是一种数据存储方式。Innodb的聚簇索引实际上在同一个结构中保存了B*Tree索引和数据行。当表有聚簇索引时，数据行实际上存储在索引的叶子节点中。聚簇的意思是表示数据行和相邻的键值紧凑地存储在一起。一个表只能有一个聚簇索引。也就是按照每张表的主键构成一棵B+树，叶子节点中存放整张表的行记录数据，也将聚集索引的叶子节点成为数据页，每个数据页之间通过一个双向链表来进行链接。数据页存放的是每行的所有记录，非数据页存放的是键值和指向数据页的偏移量。它可以在叶子节点直接找到数据，且对于主键的排序查找和范围查找速度非常快，因为聚集索引是逻辑上连续的。比如查询后10条数据，由于B+树索引是双向链表，可以很快找到随后一个数据页，然后取出最后的10条数据。
①前提条件
1.如果表中设置了主键（例如ID列），自动根据ID列生成索引树。 2.如果没有设置主键，自动选择第一个唯一键的列作为聚簇索引 3.如果没有唯一键，自动生成隐藏的聚簇索引。 4.在建表时，推荐创建主键为数字自增列。
②功能
1.录入数据时，按照聚簇索引组织存储数据，在磁盘上有序存储数据行。 2.加速查询(基于ID作为条件的判断查询)。
③聚簇索引的B*Tree构建过程
a. 叶子节点：存储数据行时就是有序的，直接将数据行的page作为叶子节点（相邻的叶子结点，有双向指针） b. 枝节点 ：提取叶子节点ID的范围+指针，构建枝节点（相邻枝节点，有双向指针） c. 根节点 ：提取枝节点的ID的范围+指针，构建根节
2 辅助索引
辅助索引需要人为创建辅助索引，将经常作为查询条件的列创建辅助索引，起到加速查询的效果。也称非聚集索引，按照每张表创建的索引列创建一棵B+树，叶子节点并不包含行记录的全部数据。叶子节点包含键值 和 书签，书签用来告诉InnoDB存储引擎在哪可以找到与索引对应的行数据，每张表可以有多个辅助索引。如果某个查询是通过辅助索引查找数据的，则查找过程为：先遍历辅助索引并找到叶节点找到指针获取主键索引的主键，然后通过主键索引找到对应的页从而找到一个完整的行记录。注：没执行一次查询就是一次IO，比如 辅助索引树高度为3，聚集索引树高度为2，则通过辅助索引查询数据时就要进行3+2次逻辑IO最终得到一个数据页。
辅助索引的B*Tree 构建过程
a. 叶子节点：提取主键（ID）+辅助索引列，按照辅助索引列进行从小到大排序后，生成叶子节点。（多个辅助索引列，以最左边的列为标准。相邻的叶子结点，有双向指针。） b. 枝节点 ：提取叶子节点辅助索引列的范围+指针，构建枝节点（相邻枝节点，有双向指针） c. 根节点 ：提取枝节点的辅助索引列的范围+指针，构建根节点
辅助索引查询过程：
# 按照辅助索引列，作为查询条件时。 1. 查找辅助索引树，得到ID值 2. 拿着ID值回表（聚簇索引）查询
①单列索引
只拿一个非主键列来创建索引，如下：
# 单列辅助索引 select * from test.t100w where k2='780P' # 优化方式： alter table 表名 add index 索引名(列名); mysql> alter table t100w add index idx_k2(k2);
②联合索引
# 使用多个非主键列创建辅助索引 mysql> alter table t100w add index idx_k1_num(k1,num);
③前缀索引
列值长度越长，数据量大的话，会影响到索引高度，需要使用前缀索引，也就是截取列值的前缀生成新的索引以提高效率。
# 判断前缀长度多少合适：截取字符串之后得到的总记录数越接近截取之前的越好，说明前缀的唯一性高！ select count(distinct(left(name,5))) from city ; select count(distinct name) from city ; # 创建前缀索引 mysql> alter table city add index idx_n(name(5)); # 删除索引 mysql> alter table city drop index idx_n;
关于索引的相关问题
1 回表问题
# 关于辅助索引回表是什么？回表会带来什么问题？怎么减少回表？ a. 回表：按照辅助索引列作为查询条件时，先查找辅助索引树，再到聚簇索引树查找数据行的过程。 b. 影响：IO量多、IO次数多、随机IO会增多 c. 减少回表： 1. 辅助索引能够完全覆盖查询结果，可以使用联合索引。 2. 尽量让查询条件精细化，尽量使用唯一值多的列作为查询条件 3. 优化器：MRR（Multi-Range-Read）， 锦上添花的功能。 mysql> select @@optimizer_switch; mysql> set global optimizer_switch='mrr=on'; 功能： （1）辅助索引查找后得到ID值，进行自动排序 （2）一次性回表，很有可能受到B+TREE中的双向指针的优化查找。
2 索引树高度的影响因素
a. 高度越低越好 b. 数据行越多，高度越高。 1. 分区表。一个实例里管理。基本不再使用了！ 2. 按照数据特点，进行归档表。 3. 分布式架构。针对海量数据、高并发业务主流方案。 4. 在设计方面，满足三大范式。 c. 主键规划：长度过长。 1. 主键，尽量使用自增数字列。 d. 列值长度越长，数据量大的话，会影响到高度。 1. 使用前缀索引 比如列值长100字符，那么只取前10个字符，构建索引树。 e. 数据类型的选择。 选择合适的、简短的数据类性。 例如： 1. 存储人的年龄 ，使用 tinyint 和 char(3)哪个好一些 2. 存储人名，char(20)和varchar(20)的选择哪一个好。 a. 站在数据插入性能角度思考，应该选：char b. 从节省空间角度思考,应该选：varchar c. 从索引树高度的角度思考，应该选：varchar 结论：建议使用varchar类型存储变长列值
创建索引
查询表索引
mysql> desc city; +-------------+----------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+----------+------+-----+---------+----------------+ | ID | int(11) | NO | PRI | NULL | auto_increment | | Name | char(35) | NO | MUL | | | | CountryCode | char(3) | NO | UK | | | | District | char(20) | NO | | | | | Population | int(11) | NO | | 0 | | +-------------+----------+------+-----+---------+----------------+ 5 rows in set (0.00 sec) PK --> 主键（聚簇索引） MUL --> 辅助索引 UK --> 唯一索引 mysql> show index from city; +-------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment | +-------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ | city | 0 | PRIMARY | 1 | ID | A | 4188 | NULL | NULL | | BTREE | | | | city | 1 | CountryCode | 1 | CountryCode | A | 232 | NULL | NULL | | BTREE | | | | city | 1 | idx_name | 1 | Name | A | 3554 | 5 | NULL | | BTREE | | | +-------+------------+-------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+ # Cardinality值越大，索引优先级越高。
创建索引
# 单列辅助索引 select * from test.t100w where k2='780P'; # 该表没有索引，大量数据查询耗时极大，需要优化！ 优化方式： 语法：alter table 表名 add index 索引名(列名); alter table t100w add index idx_k2(k2); # 联合索引创建 mysql> alter table t100w add index idx_k1_num(k1,num); # 前缀索引创建 # 判断前缀长度多少合适： select count(distinct(left(name,5))) from city ; select count(distinct name) from city ; # 创建前缀索引 mysql> alter table city add index idx_n(name(5)); # 删除索引 alter table city drop index idx_n;
执行计划获取和分析
1 执行计划工具
# 获取语句的执行计划工具 explain des # 使用方法 ： mysql> desc select * from city where countrycode='CHN'; mysql> explain select * from city where countrycode='CHN'; +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ | 1 | SIMPLE | city | NULL | ref | CountryCode | CountryCode | 3 | const | 363 | 100.00 | NULL | +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+
2 执行计划信息
table ：此次查询访问的表 type ：索引查询的类型（ALL、index、range、ref、eq_ref、const(system)、NULL） possible_keys ：可能会应用的索引 key : 最终选择的索引 key_len ：索引覆盖长度，主要是用来判断联合索引应用长度。 rows ：需要扫描的行数 Extra ：额外信息
3 Type信息详解
代价从高到低！
- ALL
# 没有使用到索引 a. 查询条件没建立索引 # district并没有被创建成辅助索引 mysql> desc select * from city where district='shandong'; +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+ | 1 | SIMPLE | city | NULL | ALL | NULL | NULL | NULL | NULL | 4188 | 10.00 | Using where | +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+ 1 row in set, 1 warning (0.00 sec) b. 有索引不走 # 这三种查询不走索引 mysql> desc select * from city where countrycode!='CHN'; mysql> desc select * from city where countrycode not in ('CHN','USA'); mysql> desc select * from city where countrycode like '%CH%';
index
# 全索引扫描 mysql> desc city; +-------------+----------+------+-----+---------+----------------+ | Field | Type | Null | Key | Default | Extra | +-------------+----------+------+-----+---------+----------------+ | ID | int(11) | NO | PRI | NULL | auto_increment | | Name | char(35) | NO | MUL | | | | CountryCode | char(3) | NO | MUL | | | | District | char(20) | NO | | | | | Population | int(11) | NO | | 0 | | +-------------+----------+------+-----+---------+----------------+ 5 rows in set (0.00 sec) mysql> desc select countrycode from city; +----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+ | 1 | SIMPLE | city | NULL | index | NULL | CountryCode | 3 | NULL | 4188 | 100.00 | Using index | +----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-------------+ 1 row in set, 1 warning (0.00 sec) # 由于country是辅助索引，这里查询会遍历扫描索引，效率也是一种问题。
range
从这里开始，我们可以接受这些类型的索引查询，但是无法容忍上述两种!
# 索引范围扫描 # 会受到：B+TREE额外优化，叶子节点双向指针 # >、<、>=、<=、in、or、between and、like mysql> desc select * from city where id<10; mysql> desc select * from city where countrycode like 'CH%'; +----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------+ | 1 | SIMPLE | city | NULL | range | CountryCode | CountryCode | 3 | NULL | 397 | 100.00 | Using index condition | +----+-------------+-------+------------+-------+---------------+-------------+---------+------+------+----------+-----------------------+ 1 row in set, 1 warning (0.00 sec) # 这种情况下，主键索引性能还可以，如果查询条件是辅助索引，就会牵扯到回表次数问题而导致性能较低。 # 以下两种查询，大几率受不到叶子节点双向指针优化。 # 他会遍历两个值之间的数据，而这种遍历是没有必要的！ mysql> desc select * from city where countrycode in ('CHN','USA'); mysql> desc select * from city where countrycode='CHN' or countrycode='USA'; # 建议：如果查询列重复值少的话，我们建议改写为 union all (2-3个，如果超过50%，那就没什么卵用了！) desc select * from city where countrycode='CHN' union all select * from city where countrycode='USA'; +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ | 1 | PRIMARY | city | NULL | ref | CountryCode | CountryCode | 3 | const | 363 | 100.00 | NULL | | 2 | UNION | city | NULL | ref | CountryCode | CountryCode | 3 | const | 274 | 100.00 | NULL | +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ 2 rows in set, 1 warning (0.00 sec)
ref
# 辅助索引等值查询 desc select * from city where countrycode='CHN'; +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ | 1 | SIMPLE | city | NULL | ref | CountryCode | CountryCode | 3 | const | 363 | 100.00 | NULL | +----+-------------+-------+------------+------+---------------+-------------+---------+-------+------+----------+-------+ 1 row in set, 1 warning (0.00 sec) # 等值查询的代价比range就要低很多了。
eq_ref
# 多表连接查询中，非驱动表的连接条件是主键或唯一键时。 mysql> desc select city.name,country.name from city left join country on city.countrycode=country.code where city.population<100; # 在非驱动表country中code是主键，在多表连接中如果显示未eq_ref，那就是最佳的优化实践，也是性能最好的一种场景。这也是多表连接中非驱动表的优化方向。驱动表后续会介绍。 +----+-------------+---------+------------+--------+---------------+---------+---------+------------------------+------+----------+-------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+---------+------------+--------+---------------+---------+---------+------------------------+------+----------+-------------+ | 1 | SIMPLE | city | NULL | ALL | NULL | NULL | NULL | NULL | 4188 | 33.33 | Using where | | 1 | SIMPLE | country | NULL | eq_ref | PRIMARY | PRIMARY | 3 | world.city.CountryCode | 1 | 100.00 | NULL | +----+-------------+---------+------------+--------+---------------+---------+---------+------------------------+------+----------+-------------+ 2 rows in set, 1 warning (0.00 sec) # 这个时候我们把population条件创建为一个辅助索引，驱动表走的索引就是range。这也是最好的一种优化了，没有别的方式比这个性能更好了，知足吧！ mysql> alter table city add index idx_p(population); mysql> desc select city.name,country.name from city left join country on city.countrycode=country.code where city.population<100; +----+-------------+---------+------------+--------+---------------+---------+---------+------------------------+------+----------+-----------------------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+---------+------------+--------+---------------+---------+---------+------------------------+------+----------+-----------------------+ | 1 | SIMPLE | city | NULL | range | idx_p | idx_p | 4 | NULL | 1 | 100.00 | Using index condition | | 1 | SIMPLE | country | NULL | eq_ref | PRIMARY | PRIMARY | 3 | world.city.CountryCode | 1 | 100.00 | NULL | +----+-------------+---------+------------+--------+---------------+---------+---------+------------------------+------+----------+-----------------------+ 2 rows in set, 1 warning (0.00 sec)
const(system)
# 主键或唯一键等值查询 # 性能最好，只需回表一次，这是一种奢望！ mysql> desc select * from city where id=1; +----+-------------+-------+------------+-------+---------------+---------+---------+-------+------+----------+-------+ | id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra | +----+-------------+-------+------------+-------+---------------+---------+---------+-------+------+----------+-------+ | 1 | SIMPLE | city | NULL | const | PRIMARY | PRIMARY | 4 | const | 1 | 100.00 | NULL | +----+-------------+-------+------------+-------+---------------+---------+---------+-------+------+----------+-------+ 1 row in set, 1 warning (0.00 sec)
NULL
# 查不到数据的时候性能最好！那我要你有何用！！！不用管了！！！ mysql> desc select * from city where id=1000000000000000;
总结
通常最常见的执行计划类型是：range、ref、eq_ref。 如果出现index或者all的情况，那就可能涉及到改写sql查询语句，或者得找业务沟通查询条件了。
