第五章 创建高性能的索引
索引,key,index。
mysql中,key
相当于index
。
索引的存储=>存储引擎层。
5.1.1 索引的类型
B-Tree索引
实际上大多使用的是B+树。
相关区别:https://www.cnblogs.com/oldhorse/archive/2009/11/16/1604009.html
B树:二叉树
B-树:多叉树,数据存所有的各个节点上;
B+树:数据存叶节点上,叶节点连在一起。
B*树:比B+树多一个非叶节点之间的指针。(类似跳表)
虽然不同存储引擎的具体索引实现不同,但Mysql中对于这一类索引使用的关键字是B-Tree
索引。
1 | NDB引擎: T-Tree结构 |
B-Tree索引
(B+Tree)的适用查询:
1 | 1. 全键值: Key中所有列是某个值; |
哈希索引
哈希索引基于哈希表实现:
每一个Key计算一个哈希值,哈希表里的value存数据行的指针。Memory
引擎对于相同哈希值的行用拉链存储。(非唯一哈希索引)
支持哈希索引的引擎: 只有Memory
引擎。
Memory
引擎: 默认哈希索引,也支持B-Tree索引。
哈希索引的适用查询:
1 | 1. 全键值。 |
哈希索引的局限性:
- 只存了哈希值,因此无法进行范围查询;
- 无法用于排序;
- 整个Key做哈希,因此无法部分匹配查询;
- 不支持前缀匹配;
- 要求哈希函数冲突少。
哈希索引的适用场景:
- 数据仓库的查找表。(精确匹配O(1)复杂度,星形,多表连接)
个人理解: 哈希索引既然是Memory引擎里用的,可能实现上就是在内存里load表数据,做了一张HashMap.(TODO)
自适应哈希索引Innodb
引擎的自适应哈希索引
:
当注意到某些索引值被使用得非常频繁时,会在内存中基于B-Tree索引再创建一个哈希索引。
(可以选择开启)
创建自定义哈希索引
假如有一个列url特别长,使用B-Tree索引的话存储内容就很大。如果查询时大多是精确匹配某个url,就可以考虑使用哈希索引。
方法:
- 新增一列url_crc,专门存储url的哈希值;
- 用触发器维护这一列。(增改)
哈希函数选择:
- 不使用MD5或SHA1,开销太大,结果太长;
- 使用CRC32或自定义。
难点: 平衡长度和冲突。
空间数据索引(R-Tree)(不推荐)
多维度索引数据(不只是前缀索引)。
需要使用Mysql的GIS相关函数MBRContains()
。
推荐使用PostgreSql的PostGIS
,Mysql还没做好。
全文索引
其他索引类型
第三方存储引擎中的索引类型:
TokuDB: 分形树索引。
ScaleDB: Patricia tries
等等。
5.2 索引的优点
- 减少扫描数据量;
- 避免排序和临时表;
- 将随机IO转化为顺序IO.
索引与查询匹配程度的评价:三星系统:
- 一星: 将查询相关记录放在了一起;(顺序IO,范围查询能利用到索引)
- 二星: 数据顺序与查找顺序一致;(避免排序,让排序也能利用到索引)
- 三星: 索引列包含查询的所有列。(避免二次访问磁盘)
上述评价的对象是(索引,某种查询). 因此并没有一个索引能够完美适应所有查询.只能说尽量适应当前场景下的高频查询.
索引适用场景:
- 小表: 直接扫全表即可;
- 中表: 索引;
- 大表: 分区。索引开销太大。
5.3 高性能的索引策略
索引策略分为两个方面:
- 建立索引的策略;
- 使用索引的策略。
5.3.1 独立列(使用索引的策略)
独立列: 索引列不能是表达式的一部分,也不能是函数的参数。
此外,如果数据类型不匹配,相当于隐式调用了类型转换函数,也是无法使用到索引的。
1 | 错误示例:(表达式) |
可以使用explain
语句检查查询是否能够利用索引。(type
不是ALL
)
5.3.2 前缀索引和索引选择性(建立索引策略)
索引的选择性= count(distinct key)/count(1)
因此Unique key的选择性是1.
可用: 选择性达到0.031以上。
当提升前缀的长度已经无法显著提高选择性,就可以停下来考虑这个长度了。
前缀索引的优点:
- 性能好;
- 空间小。
前缀索引的缺点:
- Order By和Group By无法使用;
- 覆盖扫描无法使用。
后缀索引:
可以存储反转以后的列来达到这个目的。
5.3.3 多列索引
index merge(索引合并)
利用两个单列索引来优化总查询。
explain计划里的索引type是index_merge
.
三个变种:
- OR=转化=>分治以后Union;
- And=转化=>分治以后取交集;
- 上述两种情况的组合。
OR
1 | select * from xxx where actorid=1 or filmid=2 |
索引合并并不一定比扫全表快,可以考虑用参数optimizer_switch
来关闭,或者IGNORE index
。
另一种思路就是直接建立多列索引,而不是单列索引。
5.3.4 索引顺序
本节针对B-Tree索引。
索引的顺序设置得好的话,可以受益的查询:
- order by与group by
- where条件部分匹配,范围匹配
- distinct
- 经验法则:
选择性高的列放前面=>优化Where
(不一定能优化order by和group by)
5.3.5 聚簇索引
形容的是Innodb存储B-tree索引的数据存储方式。
聚簇索引: 数据行存储在叶子节点。
聚簇: 数据行与相邻的键值紧凑存储。
InnoDB的主键列是聚簇索引;其他key列则不是(叶子节点存的不是数据行,而是主键值)。
Innodb没有主键时:
- 找Not Null的Unique key,建立聚簇索引;
- 没有的话,隐式定义一个主键。
聚簇索引优点:
- 符合查询的话,磁盘IO次数少;
- 顺序IO多;
- 覆盖索引扫描可以使用页节点中的主键值。
缺点:
- 数据不在磁盘(例如在内存),顺序IO就没优势了;
- 插入速度依赖于插入顺序;
- 更新聚簇索引列代价高(大量移动);
- 扫全表稍微慢(页分裂导致数据存储不连续);
- 页分裂导致存储空间大于实际数据大小;
- 二级索引需要两次索引查找(第一次只找到主键)。(可以使用自适应哈希索引,优化重复的查询)
Innodb和Myisam的数据分布对比
MyIsam: 主键索引和非主键索引都是非聚簇索引,存储上没有差异,叶子节点都指向物理地址。
Innodb: 主键索引是聚簇索引,叶子节点指向物理地址;非主键索引是二级索引,非聚簇索引,叶子节点指向主键值(需要二次查找)。
Innodb二级索引:
存储主键值,所以主键里的页分裂或移动的时候,不需要更新二级索引。
Innodb中按主键顺序插入行
使用自增id可以让主键顺序,保证插入效率,也保证聚簇索引的存储效率。
不适用场景:
- id随机;
- 不连续id,id分布范围过大。
(避免使用uuid作为innodb的主键)
顺序主键的缺点:
- 并发插入时间隙锁成为热点;
- 自增锁成为热点,可以通过更改Innodb_autoinc _lock_mode尽量避免这一点,但又会引进自增id存在空洞的问题.
Innodb_autoinc _lock_mode有三个取值:
1 | 0: 传统模式. 每个sesson都会竞争自增锁;(默认) |
自增id空洞产生的原因:
- 事务回滚,导致原先分配的id浪费了;
- 使用连续模式时有并发插入;
- 使用交叉模式.
详见https://www.jianshu.com/p/cca59b515e20.
5.3.6 覆盖索引
覆盖索引: 索引已经覆盖到了需要查询的所有数据。(叶子节点)
(这种情况下Select *性能会低于Select xxx)
覆盖索引的优点:
- 减少IO次数;
- 减少IO数量,提高缓存效率;
- 对于Innodb,如果二级索引覆盖了数据,就可以避免二次查询(二次查询主键索引)。
由于覆盖索引需要存储列的值,因此哈希索引、空间索引、全文索引都不能成为覆盖索引。
只有B-Tree索引才能成为覆盖索引。
explain时,如果Extra
列的值为Using index
,说明利用了覆盖索引。
回顾一下三星评价系统:
1星: 常用查询的范围查询能利用到索引(顺序IO);
2星: 常用查询的Order BY能利用到索引;
3星: 常用查询的输出只包含索引. (避免二次查找,减少磁盘IO, 覆盖索引)
因此如果一个覆盖索引,同时又能满足1星和2星,那就是3星级的索引了.
覆盖索引相关优化:
- 索引为: (actor,title)上述查询explain以后,
1
2
3select * from products
where actor='SEAN CARREY'
AND title like '%APOLO%'Extra
列为Using Where
,说明没有用到覆盖索引.
原因是,select *
包含的是所有列,而索引只有两列,不符合覆盖索引的定义.
用到的索引是actor前缀索引,title无法应用到,因为用的Like模糊查询.
查询流程大致为:
(1) 使用actor前缀索引,取出表中符合条件的主键地址;// 第1次磁盘IO
(2) 使用(1)中的主键地址,回表(读磁盘)取出相应的数据行. // 第2次磁盘IO
- 索引为: (actor,title,pro_id)上述查询explain以后,
1
2
3
4
5
6
7
8select *
FROM product
JOIN (
select prod_id
FROM product
WHERE actor='SEAN CARREY' AND title like '%APOLO%'
)AS t1
ON t1.prod_id=t2.prod_idExtra
列为Using where;Using index
.说明用到了覆盖索引.
原因是,子查询中输出的列是prod_id,包含在索引中,因此省去了此处的二次查询.
随后进行了延迟关联,找出product表中的其他列.
查询流程大致为:
(1)使用actor前缀索引,取出表中符合条件的索引与主键地址;//第1次磁盘IO
(2)使用(1)中的进行join,取出表中其他数据列.//第2次磁盘IO
由于都要使用两次磁盘IO,
1和2查询的效率取决于where条件中匹配返回的行数,假设这个product表有100W行:
(1) 返回行数很多:
actor过滤后剩下3W行,title过滤后剩下2W行;
1和2查询效率相同:
大部分时间在发送和读取数据上;
(2) 返回行数很少:
actor过滤后剩下3W行,title过滤后剩下40行;
2的查询效率高很多:
2读取3W个id,40个整行;1读取3w个整行.
(3) 总数据量少,返回行数也少:
actor过滤后剩下50行,title过滤后剩下40行;
1和2查询效率相近:
2读取50个id,40个整行;1读取50个整行.
上述查询的执行框架:
- 使用索引actor从存储引擎获取数据行;
- 将数据行读入服务器层,用title进行过滤.
因此上述优化针对的是减少存储引擎读取到服务器层的数据行.
上述优化只针对Mysql5.6版本之前. 5.6之后,有Index condition pushdown (索引条件推送), 把查询条件推送到存储引擎, 减少读取的数据量.
– TO BE CONTINUE…