B+树索引的使用

前提知识点

1. 每个索引都对应一棵 B+ 树， B+ 树分为好多层，最下边一层是叶子节点，其余的是内节点。所有用户记录都存储在 B+ 树的叶子节点，所有目录项记录都存储在内节点。
2. InnoDB 存储引擎会自动为主键（如果没有它会自动帮我们添加）建立 聚簇索引，聚簇索引的叶子节点包含完整的用户录。
3. 我们可以为自己感兴趣的列建立 二级索引，二级索引 的叶子节点包含的用户记录由 索引列 + 主键组成所以如果想通过二级索引来查找完整的用户记录的话需要通过回表 操作也就是在通过二级索引找到主键值之后再到聚簇索引中查找完整的用户记录。
4. B+ 树中每层节点都是按照索引列值从小到大的顺序排序而组成了双向链表，而且每个页内的记录（不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单链表。如果是联合索引的话，则页面和记录先按照联合索引 前边的列排序，如果该列值相同，再按照 联合索引 后边的列排序。
5. 通过索引查找记录是从 B+ 树的根节点开始，一层一层向下搜索。

create table `single_table` (
`id` int not null auto_increment,
`key1` varchar(100),
`key2` int,
`key3` varchar(100),
`key_part1` varchar(100), 
`key_part2` varchar(100), 
`key_part3` varchar(100), 
`common_fields` varchar(100),
primary key (id),
key idx_key1(key1),
unique key uk_key2(key2),
key idx_key3(key3),
key idx_key_part(`key_part1`,`key_part2`,`key_part3`)
)engine=innoDB charset=utf8;

7.1 B+树索引的示意图的简化

B+树其实是一个“矮矮的大胖子”。
聚簇索引特点：记录是按照主键值从小到大的顺序排序的。

简化后的聚簇索引示意图

二级索引的记录是按照key1列的值从小到大的顺序排序的，如果key1的值相同，着按照id列的值进行排序。

二级索引简化后的B+树示意图

7.2.索引的代价

索引是个好东西，但是不能肆意创建，它在空间和时间上都会“拖后腿”

1.空间上的代价

每建立一个索引，都要为其建立一颗B+树，每一棵B+树的每一个节点（内节点和叶子结点）都是一个数据页，一个数据页默认会占用16KB的存储空间，而一棵很大的B+树由很多数据页组成，这将占用很大的一片一片存储空间。

2.时间上的代价

B+ 树每层节点都是按照索引列的值从小到大的顺序排序而组成了双向链表。
不论是叶子节点中的记录，还是内节点中的记录（也就是不论是用户记录还是目录项记录）都是按照索引列的值从小到大的顺序而形成了一个单向链表。而增、删、改操作可能会对节点和记录的排序造成破坏，所以存储引擎需要额外的时间进行一些记录移位，页面分裂、页面回收啥的操作来维护好节点和记录的排序。如果我们建了许多索引，每个索引对应的 B+ 树都要进行相关的维护操作。

7.3应用B+树的索引

1.扫描区间和边界值

全表扫描意味着从聚簇索引的第一个叶子结点的第一条记录开始，沿着记录所在的单向链表向后扫描
可以使用等于或者区间值来减少扫描的记录数量
把形成扫描区间的搜索条件成为这个扫描区间的边界条件

select * from `single_table` where `key2` in (1438,6328) and or  (`key2` >=38 and `key2` <= 79)

使用uk_key2索引执行这个查询，则需要从下面3个扫描区间中获取二级索引记录

[1438,1438]：对应的边界值条件就是in (1438) -- 单点扫描区间
[6328,6328]：对应的边界值条件就是in (6328) -- 单点扫描区间
[38,79]：对应的边界值条件就是>= 38 and <= 79 -- 范围扫描区间

并不是所有的搜索条件都可以成为边界值，关键在于使用的索引

select * from `single_table` where `key1`< 'a' and `key3` > z and `common_field` = 'abc'

扫描区间在数轴上的显示

like

select * from `single_table` where `key2` > 100 and `key2` > 200
select * from `single_table` where `key2` > 100 or `key2` >200

语句一：扫描区间（200，+∞）
语句二：扫描区间（100，+∞）
2.有的搜索条件不能生成合适的扫描区间的情况

select * from `single_table` where `key2` > 100 and `common_field` = 'abc';
select * from `single_table` where `key2` > 100 or `common_field` = 'abc';

语句一：扫描区间（100，+∞）
语句二：扫描区间（-∞，+∞）
3.从复杂的搜索条件中找出扫描区间

select * from `single_table` where
(`key1` > 'xyz' and `key2` = 748) or
(`key1` < 'abc' and `key1` > 'lmn') or
(`key1` like '%suf' and `key1` > 'zzz'  and (`key2` < 8000 or common_field = 'abc'));

假设使用idx_key1索引

(`key1` > 'xyz' and true) or
(`key1` < 'abc' and `key1` > 'lmn') or
(true and `key1` > 'zzz'  and (true or true))

(`key1` > 'xyz' ) or(`key1` < 'abc' and `key1` > 'lmn') or(`key1` > 'zzz' )

(key1 > 'xyz' ) or (`key1` > 'zzz')

最终区间：（'xyz',+∞）
假设使用idx_key2索引

(true and `key2` = 748) or (true or true) or (true and true and (`key2` < 8000 or true))

key2 = 748 or true

true

最终扫描区间：（-∞，+∞）
4.使用联合索引值ing查询时对应的扫描区间

select * from `single_table` where `key_part1` = 'a'

扫描区间：['a','a']

定位符合条件的记录过程

select * from `single_table` where `key_part1` = 'a' and `key_part2` = 'b' and `key_part3` = 'c'

扫描区间：[('a','b','c'),('a','b','c')]

2.索引用于排序

使用联合索引的注意事项
借助索引的排序可能省去内存或者磁盘中排序的步骤
使用联合索引排序时，order by 子句后面的列的顺序必须遵循列索引的顺序给出，联合索引的左边连续的列为常量时，也可以使用联合索引对右边的列进行排序

select * from `single_table` where `key_part1` = 'a' and `key_part2` = 'b' order by `key_part3` limit 10

不可能使用索引排序的情况
1.asc,desc混用
2.排序列包含非同一个索引的列
3.排序列是某个联合索引列，但是这些排序列子联合索引中并不连续
4.用来形成扫描区的索引列与排序列不同
5.排序列不是以单独列名的形式出现order by子句中

3.索引用于分组

select `key_part1`,`key_part2`,`key_part3`,count(*) from `single_table` group by `key_part1`,`key_part2`,`key_part3`

可根据联合索引进行分组，而不需要建立临时表

7.4回表的代价

需要回表的记录越多，使用二级索引的性能就越低，甚至让某些查询宁愿使用全表扫描也不使用 二级索引

select * from `single_table` where key1>'a' and `key1` < 'c'

扫描区间（'a','c'）
读取扫描区间的二级索引数据时，所付出的代价还是较小的，不过在扫描区间（'a','c'）区间中二级索引所对应的id时毫无规律的，我们没读取一条二级索引记录。就需要根据该二级索引对应的id到聚簇索引中执行回表，由于要读取很多id值并不是连续的聚簇索引记录，而且这些聚簇索引记录分布在不同的数据页中，这些数据页也是毫无规律。因此会造成大量的随机I/O

7.5更好地创建和使用索引

1.只为用于搜索/排序/分组的列创建索引，只用于查询列没必要创建索引
2.考虑索引列中不重复的个数，不重复值的个数占全部记录条数的比例如果太低，说明该列存在很多重复值，那么在通过二级索引+回表的方式执行查询时，就有可能执行太多次回表操作
3.索引列的类型尽量小，数据类型小，索引占用的存储空间就越少，在一个数据阅内就可以存储更多的记录，磁盘I/O带来的性能损耗也就越小（一次页面的I/O可以将更多的记录加载到内存中）读写效率也就越高
4.为列前缀建立索引，字符串过长，在索引中占用的存储空间越大
5.覆盖索引：索引中已经包含所有需要读取的列的查询的方式成为覆盖索引，避免回表。最好仅把业务中需要的列放在查询列表中。
6.让索引列以列名的形式在搜索条件中单独出现
7.新插入主键时主键大小对效率的影响。避免新插入数据造成页分裂所带来的性能损耗。
8.冗余和重复索引应该避免