索引是一种帮助加快查询速度的数据结构。在MySQL中又是如何实现的？
常见的索引数据结构
有序数组
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查询 | O(logN) | 二分法 |
| 插入 | O(N) | |
| 删除 | O(logN) | 标记删除（软删除） |
- 优势：有序数组的等值查询与范围查询在性能上都很优秀；占用空间少；实现简单；天然有序
- 劣势：插入性能太差
适用环境：插入较少的情况，不再变化的数据，比如去年的销售情况
hash
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查询 | O(1) | |
| 插入 | O(1） | |
| 删除 | O(1) |
以key-value存储,可以拉链来解决冲突
- 优势：增删改查性能卓越
- 劣势：只能用于等值查询，不能范围查询，联合索引的前缀匹配失效，排序性能差
适用环境：范围查询较少
二叉树，红黑树
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查询 | O(logN) | |
| 插入 | O(logN) | |
| 删除 | O(logN) |
- 优势：增删改查性能较高；范围查询，排序性能较好
- 劣势：对于数据库来说，IO次数太多
适用环境：内存
lsm树
lsm全称日志结构合并树，它并不是一种具体的数据结构，而是一种思想，多用于大数据中。
对比普通的索引，当写数据的时候可能需要从磁盘中读取数据，再修改，有一个随机访问磁盘的过程。lsm为了提供写效率，去除了随机访问磁盘的过程，那么它是怎么做的呢?
我们知道数据存在于内存和磁盘，内存作为缓存加快读写，lsm树也是如此。它由一个内存区域和一系列的磁盘上的文件，每一个文件都有一定的格式，并且数据在文件内部是有序的。写入数据的时候只写入内存，当内存到达阈值的时候就将内存中的数据构造为一个文件，然后刷下去，这样就有多了一个文件。
当读数据的时候就比较麻烦了，需要访问每一个文件以及内存，因为他们不是整体有序的，读的效率比较低。当然为了提高读的效率会有一些优化，比如文件的格式中有[keyStart,keyEnd],布隆过滤器等。
lsm树无法避免的一个操作就是compaction，为了提高写的效率，它会将多个文件合并为一个，当然这会消耗内存和cpu的资源，极端的情况会产生读毛刺。
lsm树在大数据领域应用十分广泛，比如在hbase中，influxdb也使用了更改后的lsm树
b树
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查询 | O(logmN) | |
| 插入 | O(logmN) | |
| 删除 | O(logmN) |
- 优势：m很大，因此IO次数少；范围查询，排序性能较好
- 劣势：由于B树非叶子节点上存储数据项，导致查询可能很快也可能很慢；内存中无法缓存大量的索引
b+树
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 查询 | O(logmN) | |
| 插入 | O(logmN) | |
| 删除 | O(logmN) |
- 优势：m很大，IO次数少；稳定：每一次查询都要访问叶子节点；范围查询简单：双向链表
- 劣势：数据页分裂会造成页空洞
索引分类
是否唯一
- 唯一索引
- 非唯一索引
是否是唯一索引在查询，加锁，插入等情况的性能是不同的。
是否聚集
- 聚集索引：叶子节点上存储着数据项，比如Innodb中的主键索引，在逻辑上真实数据项按照索引组织
- 非聚集索引：叶子节点上不是数据项，比如InnoDB二级索引叶子节点上是主键
是否单列
- 单列索引
- 组合索引：多个字段组合的索引，能利用前缀匹配，索引覆盖，索引下推；但是会使用更多的空间
其他
- 全文索引：一种用于全文搜索关键字的索引，通常使用倒排索引
- 倒排索引
innodb中的索引
前提
- innodb支持b+树索引，hash索引，全文索引。
- b+树索索引的最多
- b+树索引只能根据键找到磁盘上对应的数据页而不能直接找到对应的行，需要将该数据页加载到内存中，然后查找对应的行
- 如果创建表的时候没有指定主键，如果有非空的唯一索引，那么选取第一个定义的非空唯一索引作为主键；如果不存在会自动生成一个6字节rowid；可以查询
select _rowid from xxx; - 索引页在逻辑上是有序的，也就是数据在逻辑上按照索引组织，但是索引页在物理上可以是无序的
- 当优化器选错索引是，可以使用
force index(xxx)强制使用某个索引
b+树索引
b+树索引通常在生成上的树高为2-4，那么逻辑IO只有2-4，假如机械硬盘每秒100次IO，那么一次查询最快只需要0.02-0.04秒，很快了。
辅助索引又称之为二级索引，也是采用b+树实现，当根据二级索引查询的时候，如果要查找的数据不是二级索引树上叶子节点上的数据（索引值本身，主键），那么会根据主键值进行回表：扫描主键索引树。
在组合索引中，可以使用前缀匹配：匹配前n个字符或者前m个字段，组合索引的排序方式是先排第一个字段，第一个字段相同再排其他字段。假如组合索引不是主键，在查询的时候也需要回表，但是在5.6之后引入了索引下推，如果要查询的值是主键或者是组合索引中的值，就可以不回表。
哈希索引
- 哈希算法：
k=spance_id<<20+spance_id+offset - 通过除法散列到各个槽
- 拉链法解决冲突
全文索引
使用倒排索引来实现。
在一个辅助表中存储了单词与单词在一个或多个文档的映射，使用关联数组实现：
- inverted file index ，{单词，单词所在的文档的id}
- full inverted index ，{单词，（所在的文档的id，具体的位置）}
索引管理
1 | mysql> show index from test1; |
通过show index from xxx;查看索引。
- table：表名
- Non_unique:不是唯一索引
- key_name:索引名字
- seq_in_index索引在该列中的位置
- column_name:索引列名
- collation列以什么方式存储。A:有序，NULL：无序
- cardinality：索引中唯一值数目的估值
- sub_part，索引是不是列的部分，在构造索引的时候如果选取的是一个长的字符串字段，那么数据页的利用率就不高，因此可以选择该列的一部分作为索引
- packed；如何被压缩
- null：是否允许null
- ubdex_type:索引类型
- comment：注释
索引优化
MRR（Multi-Range Read）优化
工作方式：
- 将通过辅助索引查询的数据存放到一个缓存中，也就是主键值
- 将主键排序
- 按照主键顺序访问实际的数据文件
好处：
- 使访问变得较为有顺序
- 减少缓冲池中页被替换的次数
- 批量处理对减值的查询操作
Index Condition Pushdown（ICP）优化
在根据索引查询时，会在引擎层判断是否可以使用where进行过滤，而不是将数据返回server层在过滤。用在联合索引上。
descending indexes（降序索引）
MySQL支持降序索引，在创建索引的时候添加asc 或者 desc
例子：1
2
3
4
5
6
7CREATE TABLE t (
c1 INT, c2 INT,
INDEX idx1 (c1 ASC, c2 ASC),
INDEX idx2 (c1 ASC, c2 DESC),
INDEX idx3 (c1 DESC, c2 ASC),
INDEX idx4 (c1 DESC, c2 DESC)
);
1 | ORDER BY c1 ASC, c2 ASC -- optimizer can use idx1 |
使用索引扩展（use of index extensions）
InnodB会自动的扩展二级索引：添加主键到二级索引中。
比如:1
2
3
4
5
6
7CREATE TABLE t1 (
i1 INT NOT NULL DEFAULT 0,
i2 INT NOT NULL DEFAULT 0,
d DATE DEFAULT NULL,
PRIMARY KEY (i1, i2),
INDEX k_d (d)
) ENGINE = InnoDB;
实际上：二级索引是：(d,i1,i2)
比如：1
2
3
4
5
6mysql> EXPLAIN SELECT COUNT(*) FROM t3 WHERE i1 = 3 AND d = '2000-01-01';
+----+-------------+-------+------------+------+---------------+------+---------+-------------+------+----------+-------------+
| id | select_type | table | partitions | type | possible_keys | key | key_len | ref | rows | filtered | Extra |
+----+-------------+-------+------------+------+---------------+------+---------+-------------+------+----------+-------------+
| 1 | SIMPLE | t3 | NULL | ref | PRIMARY,k_d | k_d | 8 | const,const | 1 | 100.00 | Using index |
+----+-------------+-------+------------+------+---------------+------+---------+-------------+------+----------+-------------+
可以看到，key_len 是8字节（d是4字节），而ref也是两个const，rows是1（在我的数据库中满足d = ‘2000-01-01’的rows应该是5）.
实践
优化器不使用索引的情况
- 如果对字段做函数、计算，无法使用索引树搜索，因为可能改变索引的有序性，但是即使该函数不会改变有序性也不会使用索引
- 隐式类型转化：相当于使用了函数，比如字符串与数字的比较；可以使用比较的方法来判断类型如何转换
select "10">9，返回1表示转换为数字 - 编码转换
1
mysql> select d.* from tradelog l, trade_detail d where d.tradeid=l.tradeid and l.id=2;
假如l表的编码是utf-8，而d表示utf8mb64，这条语句首先会使用l表的索引查出一条语句，然后去d表中查询，但是由于编码不同，涉及到了编码自动转换的问题，也就是需要一个转换的函数，由于utf8mb64是utf8的超集，因此d表中的索引需要一个函数转换为utf8mb64，也就违反了第一条规则。
但是如果使用的字符集相反，那么就只使用一次编码转换，依旧可以使用第二个索引
自增主键
主键最好使用递增的值，较小的值，比如自增主键。
如果使用无序的值，插入会使得数据页经常分裂，导致数据页镂空，不能有效的利用IO。在这个时候可以重建表。
联合索引
建立联合索引的时候:考虑索引的复用能力，来确定是否建立索引，索引字段的顺序
查询的时候也需要考虑能否利用前缀匹配，覆盖索引
唯一索引与非唯一索引的性能差别
查询时:
- 唯一索引,查到一个就返回;普通索引,还需要判断是否有其它的相同的索引
- 影响:微乎其微,因为MySQL每次读都是读一页,一页有很多数据;相同的索引不在此页的概率小
插入时:
- 如果数据页在内存中，唯一索引直接插入，非唯一索引页直接插入
- 如果数据页不在内存中，唯一索引需要加载磁盘上的数据页，因为不能判断是否唯一;非唯一索引直接写入change buffer的insert buffer中。
加锁时：
- 如果是间隙锁，对于唯一索引会退化为lock锁，但是非唯一索引是直接加间隙锁
给字符串加索引
- 字符串过长,考虑前缀索引
alter table t add index index1(email(6));,前缀索引会带来多次搜索的代价,因此可以使用count(distinct left(email,5)) as l5,count(distinct left(email,6)) as l6,count(distinct left(email,7)) as l7来判断最好的长度,只要超过95%就行 - 使用部分前缀索引就会导致覆盖索引失效,因为不能确定是够在该索引树上找到的就是完整的
- 如果前缀区分不明显,可是使用倒叙存储,在查询的时候采用
reverse()函数 - 也可以使用hash字段,再在表上创建一个整数字段,保存
crc32()产生的校验码,同时给这个字段加上索引;但是校验码可能会冲突,因此还需在查询的时候同时比较校验码与源字段 - 倒叙和hash不支持范围查询,倒叙有reverse()函数的消耗,hash多占存储.hash冲突毕竟小.