MySQL的索引深入剖析数据结构与算法qq42145271的博客-

一. 索引是什么？？？

1.官方解释

数据库索引，是数据库管理系统（DBMS）中一个排序的数据结构，以协助快速查询、更新数据库表中数据。
首先它是排序的，然后是个数据结构，其次可以加速我们查询数据。

我们的数据表是以文件的形式存放在磁盘上面的，每一行数据都有它的磁盘地址。
如果没有索引的话，要从几百万行数据里面检索一条数据，只能依次遍历这张表的全部数据，直到找到这条数据。
但是有了索引之后，只需要在索引里面去检索这条数据就行了，因为它是一种特殊的专门用来快速检索的数据结构，我们找到数据存放的磁盘地址以后，就可以拿到数据了。
就像字典的目录，我们需要去查找某个字，肯定不可能从第一页开始翻。那么这本书有专门的目录，它可能只有几页的内容，它是按页码来组织的，可以根据拼音第一个字母或者偏旁部首来查找，找到拼音或者偏旁部首，确定内容对应的页码，就能很快地找到我们想要的内容。

所以索引是一种排序的数据结构。

2. 创建索引

唯一的索引 (Unique Index)

在表格上面创建某个一个唯一的索引。唯一的索引意味着两个行不能拥有相同的索引值。

CREATE UNIQUE INDEX 索引名称 ON 表名称 (列名称)
“列名称” 规定你需要索引的列。

普通的索引
在表上创建一个简单的索引。当我们省略关键词 UNIQUE 时，就可以使用重复的值。

CREATE INDEX 索引名称 ON 表名称 (列名称)
“列名称” 规定你需要索引的列。
我们可以在建表的时候创建索引，也可以在表建完之后创建索引。

使用连接工具也可以添加索引，可以选择索引类型，索引方法

在 InnoDB 里面，索引类型有三种，普通索引、唯一索引（主键索引是特殊的唯一索引）、全文索引。
普通（Normal）：也叫非唯一索引，是最普通的索引，没有任何的限制。
唯一（Unique）：唯一索引要求键值不能重复。另外需要注意的是，主键索引是一种特殊的唯一索引，它还多了一个限制条件，要求键值不能为空。主键索引用 primay key创建。
全文（Fulltext）：针对比较大的数据，比如我们存放的是消息内容，有几 KB 的数据的这种情况，如果要解决 like 查询效率低的问题，可以创建全文索引。只有文本类型的字段才可以创建全文索引，比如 char、varchar、text。

我们说索引是一种数据结构，那么它到底应该选择一种什么数据结构，才能实现数据的高效检索呢？？？

二、索引的数据结构历史演进

1. 二分查找

二分查找也叫折半查找，每一次，我们都把候选数据缩小了一半。如果数据已经排过序的话，这种方式效率比较高。所以第一个，我们可以考虑用有序数组作为索引的数据结构。
有序数组的等值查询和比较查询效率非常高，但是更新数据的时候会出现一个问题，可能要挪动大量的数据（改变 index），所以只适合存储静态的数据。为了支持频繁的修改，比如插入数据，我们需要采用链表。链表的话，如果是单链表，它的查找效率还是不够高。

所以，有没有可以使用二分查找的链表呢？

为了解决这个问题，BST（Binary Search Tree）也就是我们所说的二叉查找树诞生了

2. 二叉树（BST Binary Search Tree）

二叉查找树的特点是什么？

左子树所有的节点都小于父节点，右子树所有的节点都大于父节点。投影到平面以后，就是一个有序的线性表。

二叉树既能够实现快速查找，又能够实现快速插入。
但是二叉查找树有一个问题：
就是它的查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成O(n)

如果我们插入的数据刚好是有序的1、2、11、13、14、16、17，顺序添加它会变成链表，这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的

是因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。
所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？
这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树（AVL 是发明这个数据结构的人的名字）

3. 平衡二叉树（AVL Tree）

AVL Trees (Balanced binary search trees)

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。
这个时候我们再按顺序插入一定是这样，不会变成一棵“斜树”

当它的左右子节点的高度差超过 1 的时候会进行一个左旋或者右旋的操作
所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？
在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

它应该存储三块的内容：
第一个是索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。
第二个是数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。
第三个，因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断

1. 使用AVL作为索引数据结构存在的问题

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len from information_schema.TABLES where table_schema='gupao' and table_name='user_innodb'; 

当我们用树的结构来存储索引的时候，访问一个节点就要跟磁盘之间发生一次 IO。
InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。那么，一个树的节点就是 16K 的大小。

如果我们一个节点只存一个键值+数据+引用，例如整形的字段，可能只用了十几个或者几十个字节，它远远达不到 16K 的容量，所以访问一个树节点，进行一次 IO 的时候，浪费了大量的空间

所以如果每个节点存储的数据太少，从索引中找到我们需要的数据，就要访问更多的节点，意味着跟磁盘交互次数就会过多。如果是机械硬盘，每次从磁盘读取数据需要 10ms 左右的寻址时间，交互次数越多，消耗的时间就越多

1. 二叉树的树高度太深了，如果数据量比较大，IO次数太多，从磁盘io读取耗费性能
2. 磁盘读取最小单位是4KB，如果是二叉树，因为它的每个节点存储的是关键字，数据区和子节点的引用，会造成io空间资源浪费，没有利用好操作系统和磁盘的交互

所以我们的解决方案是什么呢？
第一个就是让每个节点存储更多的数据。
第二个，节点上的关键字的数量越多，我们的指针数也越多，也就是意味着可以有更多的分叉（我们把它叫做“路数”）。因为分叉数越多，树的深度就会减少（根节点是 0）。
这样，我们的树是不是从原来的高瘦高瘦的样子，变成了矮胖矮胖的样子？
这个时候，我们的树就不再是二叉了，而是多叉，或者叫做多路。

4. 多路平衡查找树（ B Tree） （ 分裂、 合并）

跟 AVL 树一样，B 树在枝节点和叶子节点存储键值、数据地址、节点引用。
它有一个特点：分叉数（路数）永远比关键字数多 1。比如我们画的这棵树，每个节点存储两个关键字，那么就会有三个指针指向三个子节点。

B Tree 的查找规则是什么样的呢？比如我们要在这张表里面查找 15。
因为 15 小于 17，走左边。因为 15 大于 12，走右边。在磁盘块 7 里面就找到了 15，只用了 3 次 IO

这个是不是比 AVL 树效率更高呢？
那 B Tree 又是怎么实现一个节点存储多个关键字，还保持平衡的呢？跟 AVL 树有什么区别？

比如 Max Degree（路数）是 3 的时候，我们插入数据 1、2、3，在插入 3 的时候，本来应该在第一个磁盘块，但是如果一个节点有三个关键字的时候，意味着有 4 个指针，子节点会变成 4 路，所以这个时候必须进行分裂。把中间的数据 2 提上去，把 1 和 3 变成 2 的子节点

如果删除节点，会有相反的合并的操作。
注意这里是分裂和合并，跟 AVL 树的左旋和右旋是不一样的

从这个里面我们也能看到，在更新索引的时候会有大量的索引的结构的调整，所以解释了为什么我们不要在频繁更新的列上建索引，或者为什么不要更新主键。节点的分裂和合并，其实就是 InnoDB 页的分裂和合并

5. B+树（ 加强版多路平衡查找树）

B Tree 的效率已经很高了，为什么 MySQL 还要对 B Tree 进行改良，最终使用了B+Tree 呢？
总体上来说，这个 B 树的改良版本解决的问题比 B Tree 更全面。
我们来看一下 InnoDB 里面的 B+树的存储结构：

MySQL 中的 B+Tree 有几个特点：
1、它的关键字的数量是跟路数相等的；
2、B+Tree 的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据。
搜索到关键字不会直接返回，会到最后一层的叶子节点。比如我们搜索 id=28，虽然在第一层直接命中了，但是全部的数据在叶子节点上面，所以我还要继续往下搜索，一直到叶子节点。
举个例子：假设一条记录是 1K，一个叶子节点（一页）可以存储 16 条记录。非叶
子节点可以存储多少个指针？
假设索引字段是 bigint 类型，长度为 8 字节。指针大小在 InnoDB 源码中设置为6 字节，这样一共 14 字节。
非叶子节点（一页）可以存16384/14=1170个这样的单元（键值+指针），代表有1170个指针，树深度为2的时候，有1170 x 1170个叶子节点，可以存储的数据1170117016=21902400。

在查找数据时一次页的查找代表一次 IO，也就是说，一张 2000 万左右的表，查询数据最多需要访问 3 次磁盘。所以在 InnoDB 中 B+ 树深度一般为 1-3 层，它就能满足千万级的数据存储
3、B+Tree 的每个叶子节点增加了一个指向相邻叶子节点的指针，它的最后一个数据会指向下一个叶子节点的第一个数据，形成了一个有序链表的结构。
4、它是根据左闭右开的区间 [ )来检索数据

我们来看一下 B+Tree 的数据搜寻过程：
1）比如我们要查找 28，在根节点就找到了键值，但是因为它不是页子节点，所以会继续往下搜寻，28 是[28,66)的左闭右开的区间的临界值，所以会走中间的子节点，然后继续搜索，它又是[28,34)的左闭右开的区间的临界值，所以会走左边的子节点，最后在叶子节点上找到了需要的数据。

2）第二个，如果是范围查询，比如要查询从 22 到 60 的数据，当找到 22 之后，只需要顺着节点和指针顺序遍历就可以一次性访问到所有的数据节点，这样就极大地提高了区间查询效率（不需要返回上层父节点重复遍历查找）

总结一下，InnoDB 中的 B+Tree 的特点：

1)它是 B Tree 的变种，B Tree 能解决的问题，它都能解决。B Tree 解决的两大问题是什么？（每个节点存储更多关键字；路数更多）
2)扫库、扫表能力更强（如果我们要对表进行全表扫描，只需要遍历叶子节点就可以了，不需要遍历整棵 B+Tree 拿到所有的数据）
3) B+Tree 的磁盘读写能力相对于 B Tree 来说更强（根节点和枝节点不保存数据区，所以一个节点可以保存更多的关键字，一次磁盘加载的关键字更多）
4)排序能力更强（因为叶子节点上有下一个数据区的指针，数据形成了链表）
5)效率更加稳定（B+Tree 永远是在叶子节点拿到数据，所以 IO 次数是稳定的）

6. 为什么不用红黑树？

红黑树也是 BST 树，但是不是严格平衡的。
必须满足 5 个约束：
1、节点分为红色或者黑色。
2、根节点必须是黑色的。
3、叶子节点都是黑色的 NULL 节点。
4、红色节点的两个子节点都是黑色（不允许两个相邻的红色节点）。
5、从任意节点出发，到其每个叶子节点的路径中包含相同数量的黑色节点。
插入：60、56、68、45、64、58、72、43、49

基于以上规则，可以推导出：
从根节点到叶子节点的最长路径（红黑相间的路径）不大于最短路径（全部是黑色节点）的 2 倍。
为什么不用红黑树？1、只有两路；2、不够平衡。
红黑树一般只放在内存里面用。例如 Java 的 TreeMap，HashMap

7. B+和Hash索引

在 Navicat 的工具中，创建索引，索引方式有两种，Hash 和 B Tree。
HASH：以 KV 的形式检索数据，也就是说，它会根据索引字段生成哈希码和指针，指针指向数据

哈希索引有什么特点呢？

第一个，它的时间复杂度是 O(1)，查询速度比较快。因为哈希索引里面的数据不是按顺序存储的，所以不能用于排序。
第二个，我们在查询数据的时候要根据键值计算哈希码，所以它只能支持等值查询（= IN），不支持范围查询（> < >= <= between and）。
另外一个就是如果字段重复值很多的时候，会出现大量的哈希冲突（采用拉链法解决），效率会降低

InnoDB 可以在客户端创建一个索引，使用哈希索引吗？
MySQL官网有句话：InnoDB utilizes hash indexes internally for its Adaptive Hash Index feature
翻译过来就是：InnoDB 内部使用哈希索引来实现自适应哈希索引特性。
这句话的意思是 **InnoDB 只支持显式创建 B+Tree 索引，对于一些热点数据页，InnoDB 会自动建立自适应 Hash 索引，也就是在 B+Tree 索引基础上建立 Hash 索引，**这个过程对于客户端是不可控制的，隐式的。
我们在 Navicat 工具里面选择索引方法是哈希，但是它创建的还是 B+Tree 索引，这个不是我们可以手动控制的。

三、B+树的落地实现

我们知道，MySQL 是一个支持插件式存储引擎的数据库。在 MySQL 里
面，每个表在创建的时候都可以指定它所使用的存储引擎。
这里我们主要关注一下最常用的两个存储引擎，MyISAM 和 InnoDB 的索引的实现
首先，MySQL 的数据都是文件的形式存放在磁盘中的，我们可以找到这个数据目录的地址。在 MySQL 中有这么一个参数

每个数据库有一个目录，我们新建了一个叫做 User的数据库，那么这里就有一个User的文件夹。
每张 InnoDB 的表有两个文件（.frm 和.ibd），MyISAM 的表有三个文件（.frm、.MYD、.MYI）
有一个是相同的文件，.frm。 .frm 是 MySQL 里面表结构定义的文件，不管你建表的时候选用任何一个存储引擎都会生成

我们主要看一下其他两个文件是怎么实现 MySQL 不同的存储引擎的索引的

1. MyISAM

在 MyISAM 里面，另外有两个文件：
一个是.MYD 文件，D 代表 Data，是 MyISAM 的数据文件，存放数据记录
一个是.MYI 文件，I 代表 Index，是 MyISAM 的索引文件，存放索引，比如我们在id 字段上面创建了一个主键索引，那么主键索引就是在这个索引文件里面
也就是说，在 MyISAM 里面，索引和数据是两个独立的文件。
那我们怎么根据索引找到数据呢？

MyISAM 的 B+Tree 里面，叶子节点存储的是数据文件对应的磁盘地址。所以从索引文件.MYI 中找到键值后，会到数据文件.MYD 中获取相应的数据记录。

这里是主键索引，如果是辅助索引，有什么不一样呢？
在 MyISAM 里面，辅助索引也在这个.MYI 文件里面。
辅助索引跟主键索引存储和检索数据的方式是没有任何区别的，一样是在索引文件里面找到磁盘地址，然后到数据文件里面获取数据

2. InnoDB

InnoDB 只有一个文件（.ibd 文件），那索引放在哪里呢？
在 InnoDB 里面，它是以主键为索引来组织数据的存储的，所以索引文件和数据文件是同一个文件，都在.ibd 文件里面。
在 InnoDB 的主键索引的叶子节点上，它直接存储了我们的数据。

3. 什么叫做聚集索引（聚簇索引）？

就是索引键值的逻辑顺序跟表数据行的物理存储顺序是一致的。（比如字典的目录是按拼音排序的，内容也是按拼音排序的，按拼音排序的这种目录就叫聚集索引）。
在 InnoDB 里面，它组织数据的方式叫做叫做（聚集）索引组织表（clustered indexorganize table），所以主键索引是聚集索引，非主键都是非聚集索引。
如果 InnoDB 里面主键是这样存储的，那主键之外的索引，比如我们在 name 字段上面建的普通索引，又是怎么存储和检索数据的呢？
辅助索引存储索引和主键的值，然后根据主键的值去主键索引获取数据
InnoDB 中，主键索引和辅助索引是有一个主次之分的。
辅助索引存储的是辅助索引和主键值。如果使用辅助索引查询，会根据主键值在主键索引中查询，最终取得数据。

4. 为什么在辅助索引里面存储的是主键值而不是主键的磁盘地址呢？

如果主键的数据类型比较大，是不是比存地址更消耗空间呢？
我们前面说到 B Tree 是怎么实现一个节点存储多个关键字，还保持平衡的呢？
是因为有分叉和合并的操作，这个时候键值的地址会发生变化，所以在辅助索引里面不能存储地址

5. 另一个问题，如果一张表没有主键怎么办？

1、如果我们定义了主键(PRIMARY KEY)，那么 InnoDB 会选择主键作为聚集索引。
2、如果没有显式定义主键，则 InnoDB 会选择第一个不包含有 NULL 值的唯一索引作为主键索引。
3、如果也没有这样的唯一索引，则 InnoDB 会选择内置 6 字节长的 ROWID 作为隐藏的聚集索引，它会随着行记录的写入而主键递增。

select _rowid name from t; 

四、索引的使用原则

我们容易有以一个误区，就是在经常使用的查询条件上都建立索引，索引越多越好，其实不是的

1. 列的离散度

count(distinct(column_name)) : count(*)，列的全部不同值和所有数据行的比例。数据行数相同的情况下，分子越大，列的离散度就越高

简单来说，如果列的重复值越多，离散度就越低，重复值越少，离散度就越高。

了解了离散度的概念之后，我们再来思考一个问题，我们在 名称字段上面建立索引和在 性别上面建立索引有什么区别？？？
当我们用在 gender 上建立的索引去检索数据的时候，由于重复值太多，需要扫描的行数就更多
如果在 B+Tree 里面的重复值太多，MySQL 的优化器发现走索引跟使用全表扫描差不了多少的时候，就算建了索引，也不一定会走索引

2. 最左匹配原则

我们说的都是针对单列创建的索引，但有的时候我们的多条件查询的时候，也会建立联合索引。单列索引可以看成是特殊的联合索引
联合索引在 B+Tree 中是复合的数据结构，它是按照从左到右的顺序来建立搜索树的
比如字段A，B，C，创建组合索引只有a_b_c，a_b，a，其他的方式比如b，b_a则索引不会生效。
最左前缀原则就是要先看第一列，第一列满足情况的条件下再看第二列，以此类推。
就好比闯关游戏，必须先通过前面关卡，才能进入后面关卡。
索引是B+树，所以查询快，如果直接查询第二列或者第三列，它是非排序的。
多列索引一般是按照第一列排序，然后在第一列基础上对第二列排序，然后第三列，如果直接访问第二列是无序的，后面也就用不到索引了，也就是索引失效。
所以，我们在建立联合索引的时候，一定要把最常用的列放在最左边

3. 覆盖索引

回表：

非主键索引，我们先通过索引找到主键索引的键值，再通过主键值查出索引里面没有的数据，它比基于主键索引的查询多扫描了一棵索引树，这个过程就叫回表

在辅助索引里面，不管是单列索引还是联合索引，如果 select 的数据列只用从索引中就能够取得，不必从数据区中读取，这时候使用的索引就叫做覆盖索引，这样就避免了回表。
因为覆盖索引减少了 IO 次数，减少了数据的访问量，可以大大地提升查询
效率。

五、索引的创建于使用

1. 索引的创建

1、在用于 where 判断 order 排序和 join 的（on）字段上创建索引
2、索引的个数不要过多。——浪费空间，更新变慢。
3、区分度低的字段，例如性别，不要建索引。——离散度太低，导致扫描行数过多。
4、频繁更新的值，不要作为主键或者索引。——页分裂
5、组合索引把散列性高（区分度高）的值放在前面。
6、创建复合索引，而不是修改单列索引。
7、过长的字段，怎么建立索引？
8、为什么不建议用无序的值（例如身份证、UUID ）作为索引？

2. 哪些情况索引失效

1、索引列上使用函数（replaceSUBSTRCONCATsum count avg）、表达式、计算（+ – * /）
2、字符串不加引号，出现隐式转换。更准确的说是类型不一致会导致失效，比如字段email是字符串类型的，使用WHERE email=99999 则会导致失败，应该改为WHERE email=‘99999’。
3、like 条件中前面带%
4、在查询条件中使用IS NULL或者IS NOT NULL会导致索引失效。因为null不能用作索引，索引是不会索引null值的
5、负向查询，NOT LIKE 不能，!= （<>）和 NOT IN 在某些情况下可以
6、总是使用索引的第一个列：
如果索引是建立在多个列上, 只有在它的第一个列(leading column)被where子句引用时,优化器才会选择使用该索引. 这也是一条简单而重要的规则，当仅引用索引的第二个列时,优化器使用了全表扫描而忽略了索引，就是最左前缀原则

注意一个 SQL 语句是否使用索引，跟数据库版本、数据量、数据选择度都有关系。
其实，用不用索引，最终都是优化器说了算
优化器是基于什么的优化器？
基于 cost 开销（Cost Base Optimizer），它不是基于规则（Rule-Based Optimizer），
也不是基于语义。怎么样开销小就怎么来。
官网参考：
https://docs.oracle.com/cd/B10501_01/server.920/a96533/rbo.htm#38960
https://dev.mysql.com/doc/refman/5.7/en/cost-model.html

如果其中有错误的地方，欢迎指出。如果对你有所帮助，欢迎评论关注。
小白一个，还在继续学习中。。。。。