MySQL 索引介绍
本文章讲解 Hash、二叉树、平衡二叉树、B-Tree、B+Tree 索引的逻辑情况
查找都是索引操作，当数据量较大时，索引的大小可能有几个 G，甚至更多，为了减少索引在内存的占用，数据库索引是存储在磁盘上的，将索引以及索引对应的数据页从磁盘加载到内存中的过程是很花费时间的，进行索引查询的时候不可能把整个索引全部加载到内存，只能逐一加载
站在 MySQL 的角度上，磁盘的 I/O 操作次数对索引的使用效率至关重要，如果索引的数据结构尽量减少硬盘的 I/O 操作，对应消耗的时间也就越小
常见的加速查找的数据结构有两类：
- 树，如：平衡二叉搜索树，查询/插入/修改/删除的平均时间复杂度都是 O(log2N)
- 哈希，如：HashMap，查询/插入/修改/删除的平均时间复杂度都是 O(1)
Hash 索引
Hash 本身是一个函数，被称为散列函数。Hash 算法是通过某种确定性的算法（如：MD5、SHA1 等）将输入转变为输出。相同的输入永远可以得到相同的输出，假设输入内容有微小偏差，在输出时通常会有不同的结果
举例：要验证两个文件是否相同时，不需要把两份文件直接拿来比对，只需用 Hash 函数对两份文件进行计算，最后比较这两个 Hash 函数的结果是否相同，即可知道这两个文件是否相同
采用 Hash 进行检索效率非常高，基本上一次检索就可以找到数据，而 B+树需要自上向下依次查找，多次访问节点才能找到数据，中间需要多次 I/O 操作，从效率来说 Hash 比 B+树更快，但索引结构并没有设计成 Hash 型，原因如下：
- Hash 索引只支持等值（==、<>、IN） 查询，不支持范围查询
- Hash 索引存储数据时没有顺序的，在 ORDER BY 的情况下， Hash 索引还需要对数据重新排序
- 对于联合索引的情况，Hash 值是将联合索引键合并后一起来计算的，无法对单独的一个键或者几个索引键进行查询
- 对于等值查询来说，Hash 索引的效率更高，但如果索引列的重复值很多，效率就会降低，因为遇到 Hash 冲突时，需要遍历指针来进行比较，找到查询的关键字是非常耗时的，所以 Hash 索引通常不会用到重复值多的列上
InnoDB 本身不支持 Hash 索引，但是提供自适应 Hash 索引，如果某个数据被频繁查询，就会将这个数据页的地址存放到 Hash 表中，下次查询的时候就可以直接找到这个页面的所在位置，这样让 B+树也具备了 Hash 索引的优点
show variables like'%adaptive_hash_index';# 查看是否开启自适应 Hash# ON：已启用自适应哈希索引功能（默认值）# OFF：已关闭自适应哈希索引功能二叉搜索树
如果利用二叉树作为索引结构，那么磁盘的 IO 次数和索引树的高度是相关的
- 二叉搜索树的特点：
1.1. 一个节点只能有两个子节点，也就是一个节点度不能超过2
1.2. 左子节点 < 本节点 <= 右子节点，比我大的向右，比我小的向左 - 查找规则，搜索某个节点和插入节点的规则一样，假设搜索插入的数值为 key：
2.1. 如果 key 大于根节点，则在右子树中进行查找
2.2. 如果 key 小于根节点，则在左子树中进行查找
2.3. 如果 key 等于根节点，也就是找到了这个节点，返回根节点即可
2.4. 查找方式如下：
如果二叉树的深度非常大，则需要多次比较才能找到节点，如下图所示：
为了提高查询效率，需要减少磁盘 IO 次数，尽量降低树的高度，把原来瘦高的树结构变的矮胖，树的每层的分叉越多越好
平衡二叉树
- 平衡二又树又称为 AVL 树。它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树，在二叉搜索树的基础上增加了约束
- 常见的平衡二叉树有很多种，包括了平衡二叉搜索树、红黑树、数堆、伸展树。而平衡二叉树是最早提出来的自平衡二叉搜索树，一般提到的平衡二叉树指的就是平衡二叉搜索树
- 数据查询的时间主要依赖于磁盘 I/O 的次数，如果采用二叉树的形式，即使通过平衡二叉搜索树进行了改进，树的深度也是 O(log2n)，当 n 比较大时，深度也是比较高的，比如下图的情况：
每访问一次节点就需要进行一次磁盘 I/O 操作，对于上面的树来说需要进行5次 I/O 操作,虽然平衡二叉
树的效率高，但是树的深度也同样高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率
缺点：
- 一个节点最多分裂出两个字节点，树的高度太高，导致IO次数过多
- 节点中只保存了一个关键字，保存的内容太少
如果把二叉树改成 M = 3 时，同样的3个节点可以由三叉树来进行存储：
B-Tree
B 树简写为 B-Tree（横杠表示这两个单词连起来的意思），即：多路平衡查找树。它的高度远小于平衡二叉树的高度。结构如下图所示：
假设要查找的关键字是9，步骤如下：
- 与根节点的关键字 (17，35) 进行比较，9小于17得到指针 P1
- 按照指针 P1 找到磁盘块2，关键字为 (8，12)，因为9在8和12之间，得到指针 P2
- 按照指针 P2 找到磁盘块6，关键字为 (9，10)，找到了关键字9
如果查找的是 17，直接在根节点就可以查到结果
优点：B 树的节点既存储索引也存储数据，如果将频繁访问的数据放到根节点附近，就会大大的提高热数据查询的效率
缺点：B 树中每个节点既存储索引也存储数据，当数据比较大时候会导致每个节点存储的 key 变少了，就会导致 B 树的层数变高，增加 IO 次数
B+Tree
MySQL 默认使用 B+tree 索引，是基于 B-Tree 做出的改进
B+树和 B 树的差异在于以下几点：
● 有 k 个孩子节点就有 k 个关键字，即：孩子数量 = 关键字数，而 B 树中，孩子数量 = 关键字数 + 1
● 非叶子节点的关键字也会同时存在在子节点中，并且是在子节点中所有关键字的最大（或最小）
● 非叶子节点仅用于索引，不保存数据记录，和记录有关的信息都放在叶子节点中，而 B 树中的非叶子节点既可以保存索引，也可以保存数据记录
● 所有关键字都在叶子节点出现，叶子节点构成一个有序的双向链表
如图所示：
B 树和 B+树的区别：
- B+树的中间节点并不直接存储数据，因为 B+树每次只有访问到叶子节点才能找到对应的数据，而 B树中非叶子节点也会存储数据，会造成查询效率不稳定的情况，有时访问到非叶子节点就可以找到关键字，有时需要访问到叶子节点才能找到关键字，缺少系统性。而且在 B+树的角度上看，非叶子节点完全可以存储更多数据页的目录项记录，这样可以关联到更多的用户记录
- 其次，B+树的查询效率更高，因为通常 B+树比 B 树更矮胖（阶数更大，深度更低），查询所需要的磁盘 I/O 也会更少，同样的磁盘页大小，B+树可以存储更多的节点关键字
- 在查询范围上，B+树的效率也比 B 树高。因为所有关键字都出现在 B+树的叶子节点中，叶子节点之间会有指针，数据又是递增的，使得范围查找可以通过指针连接查找，而 B 树则需要遍历才能完成范围的查找，效率要低很多
- B 树和 B+树都可以作为索引的数据结构，在 MySQL 中采用的是 B+树，但 B 树和 B+树各有自己的应用场景，不能说 B+树完全比 B 树好
思考：
- 为了减少 I/O，索引树是否会一次性加载？
- 数据库索引是存储在磁盘上的，如果数据量很大，必然导致索引的大小也会很大，可能会有好几个 G，当使用索引查询时候，是不可能将全部几个 G 的索引都加载进内存的，只能是逐一加载每一个磁盘页，因为磁盘页对应着索引树的节点
- B+树的存储能力如何？为何说一般查找行记录，最多只需1~3次磁盘 I/O
- InnoDB 存储引擎中页的大小为 16KB，一般表的主键类型为 INT（占用4个字节）或 BIGINT（占用8个字节），指针类型也一般为4或8个字节，也就是说一个页（B+Tree 中的一个节点）中大概存储 16KB / (8B+8B) = 16384B / 16B = 1024 个键值（假设这里的 K 取值为10^3），也就是说一个深度为3的 B+树索引可以维护 10^3 * 10^3 * 10^3 = 10 亿条记录（假设一个数据页也存储10^3条行记录数据）
- 实际情况中每个节点可能不能填充满，因此在数据库中，B+Tree 的高度一般都在2~4层，MySQL 的 InnoDB 存储引擎在设计时是将根节点常驻内存的，也就是说查找某一键值的行记录时最多只需要1~3次磁盘 I/O 操作
小结
使用索引可以从海量的数据中快速定位想要查找的数据，不过索引也存在一些不足，比如占用存储空间、降低数据库写操作的性能等，如果有多个索引还会增加索引选择的时间。使用索引时，需要平衡索引的利（提升查询效率）和弊（维护索引所需的代价），在实际工作中还需要基于需求和数据本身的分布情况来确定是否使用索引，尽管索引不是万能的，但数据量大的时候不使用索引是不可想象的，毕竟索引的本质就是提升数据检索的效率