索引

对任何数据结构来说，在 Read Overhead（读）、Update Overhead（写） 和 Memory or Storage Overhead（存储） 中，同时优化两项时，需要以另一项劣化作为代价

为什么使用索引

1. 大大减少了服务器需要扫描的数据量
2. 帮助服务器避免排序和临时表
3. 将随机io变成顺序io

索引用处

1. 快速查找匹配WHERE子句的行
2. 从consideration中消除行,如果可以在多个索引之间进行选择，mysql通常会使用找到最少行的索引
3. 如果表具有多列索引，则优化器可以使用索引的任何最左前缀来查找行
4. 当有表连接的时候，从其他表检索行数据
5. 查找特定索引列的min或max值
6. 如果排序或分组时在可用索引的最左前缀上完成的，则对表进行排序和分组
7. 在某些情况下，可以优化查询以检索值而无需查询数据行

索引使用条件

• 小表全表扫描效率优于索引
• 索引适合中大型表
• 特大型表，建立和维护索引的代价将会随之增长

评价

索引好坏的评价维度

• 访问类型：是否支持范围访问、特定值访问
• 访问时间
• 插入时间
• 删除时间
• 空间开销

一些索引数据结构

• hash（散列索引）
  • 可以直接根据key访问
  • **但是无法进行范围查询**
• avl（顺序索引）
  • 平衡二叉树，左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值（平衡因子 ） 不超过1
  • 支持范围查询
  • **插入操作可能需要旋转，效率低**
• b+树（顺序索引）

散列索引

要求全部的索引要能放入内存

• 静态散列
• 动态散列：散列函数、桶大小可以动态改变，性能不随文件增长降低。空间开销小。并且增加了一个中间层，带来微小的性能损失。

位图索引

性别_男= 10010101性别_女= 01101010区_朝阳= 00000100

当要获取朝阳的男的时候，将两个向量相与，结果为1的位置的数据，就是搜索命中的结果

位图操作的高效实现

位图与B+树

采用传统的 B+ 树建立索引，如果数据区分度很低，则B+树效率也不高

顺序索引

• 稠密索引: 每个属性都有一个索引项
• 稀疏索引: 只为某些属性建立索引

多级索引

• 通过将一级索引表放置在内存中加快搜索速度

索引的更新

插入新记录

对于稠密索引：如果该索引值不存在于索引中，则在合适的位置插入索引值，如果存在于索引中，则找到索引值对应的记录链表，在链表尾部追加新记录

对于稀疏索引：在合适的索引值范围内添加新记录

删除记录

对于稠密索引：如果该记录时该索引值的唯一记录，删除即可。否则执行链表的节点删除操作

对于稀疏索引：如果包含了索引值，则删除索引值对应的记录，并调整索引范围

辅助索引

在索引与实际记录之间的一个中间层，也就是非聚簇索引，索引的不是物理位置，而是根据某些列的值建立的一个独立的数据结构

B树

2-3 树是一种特殊的 B- 树

B+树

B-tree减少了定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统

B+树中叶子节点中包含了key和value，非叶子节点中只是包含了key，不包含value

所有叶子节点位于同一层，之间会通过双向指针串联在一起，构成一个双向链表

B+ 树可以让整个树状结构变得更加矮胖，而磁盘的预读特性每次都可以加载一整个节点中全部的键，到内存进行二分查找。同时叶子节点都被串联起来了，适合范围查询，非叶子结点没有存放数据，适合放到内存当中

如果出现了两条或者多条记录在索引属性上拥有相同的值，解决方法：

• 创建包含原始搜索码和其他额外属性的符合搜索码
• 在B+树节点上使用列表来存储

MySQL 中，一个页就是 B+ 树的一个节点，一个页的大小最大为 16K。因为非叶子节点保存的是主键值 + 指针，假设主键值类型是 __int64（占 8 字节），指针占 6 字节，一共 14 字节，那么一个页 16K（16384 字节）如果存满则大概可以保存下 1170 个“主键值 + 指针”对（16384/14=1170），假如每一条记录的大小为 1k，那么一个节点就能容纳 16 条记录，所以一个三层的 B+ 树能容纳 $1170 * 1170 * 16 = 21902400$

文件结构

操作

更新操作比较复杂，但是需要较少的 IO 操作

批量加载

如果一次性插入大量数据，在插入前对数据排序再插入到B+树中，可以有效提升性能

同时，如果B+树是空的，还可以使用自底向上的方式来进行构建

查找

首先在根节点进行二分查找，找到一个key的指针，接下来递归地不断向其非叶子节点查找，到了叶子节点，再进行二分查找，找出key所对应的data

修改

查找出要修改节点的位置，由于每个中间节点能容纳的元素是有限的，所以修改之后会进行分裂、合并、旋转

vs红黑树

• 红黑树的出度为2，B树的出度要大很多，所以B树的查找次数更少
• B+ Tree能更好地利用磁盘的预读特性 但操作也会更加复杂

LSM树

log-structured merge tree

Memtable

内存中的数据结构，存储的是近期更新的记录值，可以用各种有序高效的数据结构来实现。为了保证内存中的数据在崩溃后能恢复，会采取 WAL 机制，先写日志再写内存，同时定期生成检查点快照，避免 WAL 日志无限增长。

Immutable Table

在写入磁盘的过程中，系统很可能仍然在对外工作，所以创建副本，可以很好的地帮助避免读写冲突竞争

SSTable

它要求key是有序的，并且每个段中每个key只能出现一次，查找key时，可以在稀疏索引中通过排序查找里快速找到

为了实现SSTables，需要在内存中维护一个有序的数据结构，每次写入时都会写到内存表，再由系统周期性刷到磁盘，为避免崩溃导致内存的数据还没刷到磁盘丢失，再维护一个日志文件，每进行一个操作就写到日志，以供恢复时使用

需要查找时，就对段逐个倒叙查找，直到找到

压缩数据

在 SSTable 的主流实现里，我们会把不同的阶段被合并的 segment 放到不同的层中，并限制每一层数量，当某层 segment 超过一定数量，我们就会把它们删除，合并出一个更大的 segment 放入下一层。

删除数据

对数据标记了一个特殊的状态为记为删除，把这个特殊的状态称为 tombstone

MYSQL索引

技术名词

• 回表：使用索引就能完成查询 无需扫描表数据
• 最左匹配：在检索数据时从联合索引的最左边开始匹配，也代表字符串最左N个字符可以走索引
• 索引下推：在“仅能利用最左前缀索的场景”下，在遍历索引时，使用不在最左前缀索引中的其他联合索引字段，过滤会减少遍历索引查出的主键条数，减少回表

分类

• 根据叶子节点是否存储数据来划分，可以分成聚簇索引和非聚簇索引
• 如果某个索引包含某个查询的所有列，那么这个索引就是覆盖索引
• 如果索引的值必须是唯一的，不能重复，那么这个索引就是唯一索引
• 如果索引的某个列，只包含该列值的前一部分，那么这个索引就是前缀索引。比如说在一个类型是 varchar(128) 的列上，选择前 64 个字符作为索引
• 如果某个索引由多个列组成，那么这个索引就是组合索引，也叫做联合索引
• 全文索引是指用于支持文本模糊查询的索引
• 哈希索引是指使用哈希算法的索引，但是 MySQL 的 InnoDB 引擎并不支持这种索引

B+ Tree索引

• 是大多数 MySQL 存储引擎的默认索引类型
• 除了用于查找，还可以用于排序和分组
• 适用于全键值、键值范围和键前缀查找

哈希索引

• 无法用于排序与分组
• 只支持精确查找，无法用于部分查找和范围查找
• 数据列只能回表查询，无法直接根据索引读取

只有Memory引擎显式支持哈希索引。对于索引比较长的字符序列，哈希索引很好用

InnoDB当某些索引值被使用的非常频繁时，会在B树索引的基础上创建一个哈希索引来提升效率，这个过程是内部且自动的。

为了在InnoDB上模拟出哈希索引，可以考虑使用一个字段存储哈希值，每次查找时对这个哈希值做一个等值比较：

SELECT * FROM tb_url WHERE hash_code = CRC32('http://baidu.com') AND url = 'http://baidu.com';

全文索引

• MyISAM 存储引擎支持（innodb 5.6后支持）
• 用于查找文本中的关键词
• 查找条件使用 MATCH AGAINST
• 使用倒排索引

空间数据索引

空间数据索引（R-Tree），可以用于地理数据存储

索引匹配方式

全值匹配

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

explain select * from staffs where name = 'July' and age = '23' and pos = 'dev'

但要注意，进行查询时，索引列不能是表达式的一部分，也不能是函数的参数

SELECT a FROM B WHERE a+3 = 6; -- 无法用到索引

像字符串跟数值比较的隐式类型转换、字段运算、字段是函数的参数、字符集不同等，本质上都是对字段做了转换操作，可能会破坏索引值的有序性，因此优化器就决定放弃走索引树的搜索，但还是会遍历索引

匹配最左前缀

多个列作为条件进行查询时，使用组合索引比使用多个单列索引性能更好，MySQL会进行一项称为索引合并的策略，一定程度上可以使用多个单列索引来定位指定的行

explain select * from staffs where name = 'July' and age = '23';explain select * from staffs where name = 'July';-- 精确匹配某一列并范围匹配另外一列，可以查询第一列的全部和第二列的部分explain select * from staffs where name = 'July' and age > 25;-- 2. 最左匹配，如果有一个(name,age,pos) 的索引，当一个索引不止一个列时，只有当最左索引（索引的第一个列）出现时，才会走索引查询explain select * from staffs where age = 25 -- 不走索引

当包含多个列作为索引，需要注意的是正确的顺序依赖于该索引的查询，同时需要考虑如何更好的满足排序和分组的需要

但不考虑排序和分组的情况下，让选择性最强的索引列放在前面

匹配列前缀

可以匹配某一列的值的开头部分

explain select * from staffs where name like 'J%'; -- 可以用索引explain select * from staffs where name like '%y'; -- 用不到索引

可以选择开始的部分字符串来进行索引，索引的列的不重复值数量/总数量=索引的选择性 选择性越高 查询效率越好

前缀索引占用的空间会比较少，但同时会增加扫描次数，为了达到索引空间与查询性能的平衡，需要统计数据整体前缀的区分度，选取一个折中的前缀索引长度

BLOB、TEXT 和 VARCHAR 类型的列，必须使用前缀索引

前缀索引无法进行ORDER BY 或者GEOUP BY，也无法覆盖扫描，需要再回表查询

有时候又需要后缀索引，为了达成这个目的，一种hack的方式是把字符串反转后进行存储

匹配范围值

可以查找某一个范围的数据

explain select * from staffs where name > 'Mary';

范围条件是：<、<=、>、>=、between 范围列可以用到索引，但是范围列后面的列无法用到索引，索引最多用于一个范围列

覆盖索引

explain select name,age,pos from staffs where name = 'July' and age = 25 and pos = 'dev'; -- Extra:Using index 代表可以使用覆盖索引

如果一个索引包含所有需要查询的字段的值，称之为覆盖索引，当需要的数据被索引覆盖时，就不必回表查询。只使用索引可以减少数据读取量，同时由于索引是顺序存储的，相比直接读取数据，拥有较好的IO性能。MySQL中只能使用B树索引做覆盖索引

聚簇索引与非聚簇索引

• 聚簇索引：不是单独的索引类型，而是一种数据存储方式，指的是数据行跟相邻的键值紧凑的存储在一起
• 非聚簇索引：数据文件跟索引文件分开存放

在InnoDB中，默认会选择主键来做聚簇索引，若没有主键，会生成一个隐藏的主键，主键最好使用自增的数值类型，这样在插入效率及空间占用都会最优

MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址，在索引检索的时候，首先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其 data 域的值，然后以 data 域的值为地址读取相应的数据记录。

而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录，。而其余的索引都作为辅助索引，辅助索引的data域存储相应记录主键的值而不是地址，这也是和MyISAM不同的地方。在根据主索引搜索时，直接找到key所在的节点即可取出数据；在根据辅助索引查找时，则需要先取出主键的值，再走一遍主索引。

使用索引排序

EXPLAIN的type为index时 代表使用索引扫描做排序

只有当ORDER BY子句的列都是索引且排序方向一致时，才会使用索引排序

压缩索引

MyISAM会使用前缀压缩的方式将降低索引空间占用，从而使更多的索引可以放入内存。但代价是牺牲了CPU的运算时间。

冗余索引

大多数情况下应尽量扩展已有的索引而非创建新索引，索引越多，更新的时候越慢。

但有时候为了兼容多个查询情况，为创建冗余索引来提升性能

其他关于索引的优化

• union all,in,or都能够使用索引，但是推荐使用in
• 更新十分频繁，数据区分度不高的字段上不宜建立索引 更新会变更B+树，更新频繁的字段建议索引会大大降低数据库性能 区分不大的属性，建立索引是没有意义的，不能有效的过滤数据
• 创建索引的列，不允许为null，可能会得到不符合预期的结果
• 单表索引建议控制在5个以内
• 单索引字段数不允许超过5个（组合索引）

索引监控

show status like 'Handler_read%';

• Handler_read_first：读取索引第一个条目的次数
• Handler_read_key：通过index获取数据的次数
• Handler_read_last：读取索引最后一个条目的次数
• Handler_read_next：通过索引读取下一条数据的次数
• Handler_read_prev：通过索引读取上一条数据的次数
• Handler_read_rnd：从固定位置读取数据的次数
• Handler_read_rnd_next：从数据节点读取下一条数据的次数

维护索引和表

CHECK TABLE 命令可以找出大多数表和索引的错误，使用REPAIR TABLE来修复损坏的表

MySQL 使用基本成本模型的优化器，优化器会计算不同执行计划的执行成本，而执行成本则会使用表、索引等的统计信息计算得到，有时候这些统计信息会不准，使用ANALYZE TABLE 可以重新生成表的统计信息

使用OPTIMIZE TABLE来整理碎片，对于不支持的存储引擎，执行

ALTER TABLE table_name ENGINE=old_engine