索引概述
索引即key
在存储引擎层实现，不同引擎工作方式不同
索引优化--最好的查询优化手段，可提效几个数量级
两步查找数据：
磁盘查找索引节点（页），将其调入内存；
内存内业内查找数据
一. 索引类型
B-Tree
Hash
R-Tree空间数据索引
全文索引
1. B-tree索引
- 支持引擎：InnoDB，MyISAM，Memory
- 所有叶子值顺序存储，且到root高度一样
- InnoDB，MyISAM B-tree工作方式异同：
InnoDB按原格式存储数据，MYISAM用前缀压缩技术
InnoDB用主键key索引数据行，MyISAM用物理位置索引数据行
- 加速：存储引擎从root节点扫描，代替全表扫描
- 叶节点指针-->被索引数据（data record）
1)B-Tree适用场景
1 全值匹配查询
所有列都匹配
2 最左前缀匹配
组合索引第一列
3 列前缀匹配
某列值开头
4 范围值匹配
5 一列精确一列范围匹配
6 覆盖索引查询
只访问索引即可取data，无须访问数据行
7 Order by排序
？
2) B-Tree不适用场景
- 非最左列
- 跳列
A C
- 某列进行范围查询，其右边所有列无法再用索引
2. Hash索引
- 访问哈希索引的数据很快
f(key)=slot
1) 支持引擎
Memory，NDB集群
2) 适用场景
索引全列匹配
3) 不适用场景
- 不能从索引直接取data
哈希索引=哈希值+行指针，不存储字段值
- 不能用于排序
哈希值有序，但索引数据无序
- 不支持部分索引列匹配
- 不支持范围查询
仅支持等值匹配 =,<=>,IN()
<=> NULL安全等于----操作数可为NULL
4) InnoDB自适应Hash索引
某些索引值被引用很频繁，InnoDB自动在内存B-Tree索引上创建一个Hash索引
用户无法控制和配置，但可关闭
5) 自定义hash索引
存储引擎不支持时，模拟创建hash
如何创建？
B-tree上创建伪hash索引
- 仍在Btree上查找，但用hash索引值代替原Key（伪hash）
- 须在where指定hash函数，不要用MD5(),SHA1()
select id from url
where url="www.mysql.com"
and
url_crc=CRC32("www.mysql.com")
其中urc_crc列为索引列
6) 处理Hash冲突
使用hash索引查询时，须在where指定常量
select id from url
where
url_crc=CRC32("www.mysql.com")
and
url="www.mysql.com"
select word,crc from words
where
crc=CRC32("gnu")
and
word="gnu"
@birthday problem
In probability theory, the birthday problem or birthday paradox concerns the
probability that,
in a set of {\displaystyle n} n randomly chosen people, some pair of them will have the same birthday.
By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367 (since there are only 366 possible birthdays, including February 29). However, 99.9% probability is reached with just 70 people, and 50% probability with 23 people.
3. 空间数据索引 R-Tree
支持引擎：MyISAM
用作地理数据存储，如美团，滴滴定位服务
任意维度组合查询
须使用GIS函数维护数据，MySQL做的不好
4. 全文索引
- 查找文本关键字，非比较索引键值
- 类似搜索引擎
- 相同列创建全文索引和B-Tree索引，不冲突
5. 其他索引
第三方引擎TokuDB
二. 索引好处
1. 好处
1) 减少扫描数据量
2) 避免排序和临时表
3) 随机IO转为顺序IO
2. 索引三星评价
评价索引是否适合某查询
第一星
索引将相关data行放到一起
第二星
索引的data行按查询所需顺序排序
第三星
索引含 查询全部列
三 .高性能索引策略
1. 独立的列
独立
索引列非表达式子式，或函数参数
两个错误：
1)索引列为表达式
select id from actor
where id + 1 = 5
2)
select ...
where
TO_DAYS(Current_DATE) - TO_DAYS(date_col) <= 10；
2. 前缀索引和索引选择性
1) 前缀索引
很长字符串，可索引开始的部分字符串
适用场景
BLOB，TEXT，很长的VARCHAR列
2) 优缺点
优点
节约索引空间
缺点
无法使用之做order by，Group by
无法使用做覆盖索引
3) 索引选择性
=不重复索引值/数据表记录总数
- 不重复索引值<-->基数<-->cardinality
- 记录总数<-->#T
- 取值范围 [1/#T ,1]
- 越高越好
选择性越高，过滤掉的行越多
4) 如何找到 前缀索引长度
思想
足够长（接近完整列），又不能太长（节约空间）
方法1 试验法
先算完整列频次，然后一个一个前缀试验
计算完整列频次
试验前3前缀
方法2 计算完整列选择性
使前缀选择性接近完整列选择性
5） 如何创建前缀索引
ALTER TABLE sakila
ADD KEY(city(7));
KEY(city(7))
3. 多列索引
1） 常见错误
每个列都创建单独索引，导致索引合并
create table t(
c1 int，
c2 int，
KEY（c1），
KEY（c2)
);
2） 索引合并表示索引建的不好，待优化
- 多个索引相交（AND）不如组合索引好
- 多个索引联合（OR）耗费CPU和内存资源
- 优化器不计算（耗费CPU和内存资源）到查询成本中
4. 选择合适的索引列顺序
仅适用于BTree索引（按顺序存储数据）
Btree索引按从左到右顺序，依次扫描
索引可按升、降序扫描，满足Order by，Group by，Distinct
如何选择合适的索引列顺序
经验法则
无order by和Group by时，选择性最高的列放在前面
select * from payment
where staff_id=2 and customer_id=584;
key（staff_id,customer_id)还是key(customer_id,staff_id)?
5. 聚簇索引（clustered index）
InnoDB支持，MyISAM为非聚簇
聚簇
数据行，键值存储在一起
一个表只能有一个聚簇索引
聚簇特点
- InnoDB通过主键聚集数据
主键未定义，用唯一非空索引聚集
无唯一非空索引，则隐式定义主键
- 只聚集同一页面记录
聚簇优点
- 相关数据保存在一起，如电子邮件（用户ID和全部邮件）
- 数据访问更快（索引和数据都在BTree中）
- 覆盖索引查询直接取页节点键值
聚簇缺点
数据全放内存时无优势（访问顺序不再重要）
插入速度依赖于插入顺序
InnoDB按主键顺序插入最快（否则插入后用optimize table优化表）
更新聚簇索引列代价很高
强制将每个更新行移动到新位置
页分裂问题
插入新行或，主键更新导致需移动行时
全表扫描慢
二级索引需两次索引查找
二级索引（secondary index，辅助索引）
叶节点保存行主键值，非指向data行的物理记录的指针
二级索引查找行步骤
- 叶子节点找到主键值
- 在聚簇索引找数据行
1 . InnoDB和MyISAM数据分布对比
InnoDB数据分布
InnoDB就是表，不用再像Myisam用单独列存储
聚簇索引叶子节点包含：
主键值
事物ID
回滚指针（用于事物和MVCC）
其他剩余列
聚簇和非聚簇表对比
2. InnoDB表按主键顺序插入行
无数据聚集，使用AUTO INCREMENT作为主键--保证按顺序写入
避免使用UUID（universal unique identifier）聚簇索引--导致插入变得随机
6. 覆盖索引
索引直接包含所需查询数据行，不需要回记录表（数据表）
只能用BTree做覆盖索引
支持InnoDB,myisam
Explain显示 Extra：Using index
覆盖索引优点
- 索引条目小于数据行，减少了数据访问量
- 范围查询IO少（索引列值顺序存储）
- 对InnoDB表（聚簇索引）特别有用
二级主键能覆盖查询可避免对主键索引的二次查询
MyISAM覆盖索引可能会导致系统问题
MyISAM引擎内存只缓存索引，数据由OS缓存
ICP索引条件推送（index condition pushdown）
MySQL5.6开始支持
条件过滤推到存储引擎层完成，减少IO访问
7. 用索引扫描做排序
MySQL生成有序结果的两种方式
- 排序
- 按顺序扫描索引
Exlain Type：Using index
为何索引扫描比全表扫描慢？
如果索引不能覆盖查询全部列，则每扫一条索引记录必须回表（随机IO）
同一索引，既满足排序，又满足查找是最好的
何时能用索引进行排序？
- 索引列序和order by顺序一致时
- 且所有列排序方向一样
不能使用索引进行排序的场景
- order by出现不同排序方向
- order by引用非索引列
- where和order by中的列无法组合为最左前缀
- where第一列是范围条件
- where出现IN(多个相等条件视为范围）
8. 压缩（前缀压缩）索引
MyISAM使用
减少索引大小（1/10磁盘空间）让更多索引进入内存
默认只压缩字符串，也可设置整数
只能从头开始扫描，无法二分
随机扫描导致适用于IO密集型（OLTP），不适用CPU密集型（OLAP）？
index1：perform
index2：performance-->7,ance
9. 冗余和重复索引
应删除重复索引
１) 重复索引
相同列创建多个索引
三个重复索引--unique，primary限制均通过索引实现
2) 冗余索引
应该删除冗余索引
两种冗余
已有key（A，B）,再建key(A)
ID为主键，扩展索引为(A,ID)
建议
尽量扩展现有索引，而不是创建新索引，那样会导致冗余索引
10.删除未使用的索引
percona Toolkit--
pt-index-usage工具
11. 索引和锁
InnoDB存储引擎层完成条件过滤时（ICP--MySQL 5.6及以后），索引可减少访问行数，从而减少加锁数量
否则全表扫描并锁住所有行
覆盖索引失效：
- InnoDB二级索引上用共享（读）锁，访问主键索引需要排他（写）锁
-
select for update比lock in share mode或非锁定查询慢
四. 索引和表维护
维护表三目的
找到并修复损坏的表
维护准确的索引统计信息
减少碎片
1. 找到并修复表
1） MyISAM表
check table--检查表
repair table--修复损坏的表
2） InnoDB表使用no-op ALTER
Alter TABLE innodb_tb ENGINE=INNODB;
2. 维护索引统计信息
优化器有时用索引统计信息估算扫描行数
ANALYZE TABLE更新统计信息避免错误
memory引擎不存储统计信息
MyISAM引擎存储统计信息在磁盘
Show Index from table查看索引基数（cardinality,索引列不同取值个数）
触发索引统计信息更新的三种情形
SHOW TABLE STATUS
SHOW INDEX
打开某些INFORMATION_SCHEMA表
3.减少索引和数据碎片
1）BTree索引会碎片化，降低查询效率
BTree随机访问是必须的，因为从root节点随机磁盘访问才能定位到叶子节点
2）三种数据碎片
行碎片
数据行存储在多个地方多个碎片中
行间碎片
逻辑上顺序的页或行，在磁盘上非顺序存储
剩余空间碎片
数据页中有大量不用的空余空间
MyISAM三种碎片都有，InnoDB无小碎片
3）如何消除碎片？
- OPTIMIZE TABLE
- ALTER TABLE tb ENGINE=<engine>;
- 删除所有索引-->重建表 -->重建索引
五. 总结
索引三原则
1.单行访问很慢
最好一个数据块读取多行
2. 按顺序访问范围行很快
- 顺序IO无需多次磁盘寻道，比随机IO快很多
- 服务器按顺序读取数据，则不需要额外排序
3. 索引覆盖查询很快
避免了大量单行访问
2017-4-10 sz
