MySQL高级十一：其它索引详解

其它索引

导读

1. 树状索引结构的迭代演化：

   二叉搜索树 -> AVL树 -> B - 树 -> B + 树

一、Hash结构

1. Hash

   Hash本身是一个函数，又称为散列函数，它可以帮助我们大幅提升检索数据的效率

2. Hash算法

   是通过某种确定性的算法（比如MD5、SHA1、SHA2、SHA3等）将输入转变为输出。确保：相同的输入永远可以得到相同的输出。

3. Hash结构

   例如HashMap，查询/插入/修改/删除的平均复杂度都是O(1)，在存储时，哈希函数有可能将两个不同的关键字映射到相同的位置，这叫做 碰撞 ，在数据库中一般采用 链 接法 来解决。在链接法中，将散列到同一槽位的元素放在一个链表中

   

4. 限制性

   ① Hash索引仅能满足=、<>、IN的查询，其时间复杂度为O(1)。但是如果进行范围查询，时间复杂度就会退化为O(n)。

   ② Hash函数形成的数据是没有顺序的，在ORDER BY的情况下，使用Hash索引还需要对数据进行重新排序

   ③ 对于联合索引，Hash索引会将多个键合并后一起计算，无法单独对一个键进行查询。

   ④ 如果索引列的重复值如果很多，效率就会降低。因为这种情况下会遇到Hash冲突，需要遍历桶中的行指针进行比较。

5. 适用的存储引擎

   	MyISAM	InnoDB	Memory
   Hash索引	不支持	不支持	支持

6. 适用性

   ① 在键值性（key-value）数据库中，Redis存储的核心就是Hash表

   ② MySQL中的Memory存储引擎支持Hash存储

   ③ 在InnoDB中，虽然不支持Hash索引，但是提供自适应Hash索引。即如果某个数据经常被访问，当满足一定条件时，就会将这个数据页的地址存放Hash表中。

   

   

二、二叉搜索树

1. 最基本的树状，左边的节点小于根节点，右边的节点小于根节点

   

2. 特殊的二叉搜索树，退化为了链表

   

3. 为了提高查询效率，就需要 减少磁盘IO数 。为了减少磁盘IO的次数，就需要尽量 降低树的高度 ，需要把 原来“瘦高”的树结构变的“矮胖”，树的每层的分叉越多越好，所以引出了B - 树。

三、AVL树

1. 定义

   为了解决二叉搜索树在极端情况下退化为链表的问题，而生成的平衡二叉搜索树，Balanced Binary Tree

2. 特性

   左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是一颗平衡二叉树

3. 常见的平衡二叉树

   平衡二叉搜索树、红黑树、数堆、伸展树

4. 平衡二叉树的模型图

   

5. M叉树的模型

   

四、B - Tree

1. 定义

   英文全称：Balance Tree，也就是多路平衡查找树，简称B - Tree，其高度源小于平衡二叉树

2. 树的结构

   

3. 特性

   ① B - Tree在插入和删除节点的时候，如果导致树不平衡，就通过自动调整节点的位置来保持树的自平衡

   ② 关键字集合分布在整棵树中，即叶子节点和非叶子节点都存放数据。故搜索有可能在非叶子节点结束。

   ③ 其搜索性能等价与关键字全集内做了一次二分查找

五、B + Tree

1. 简介

   B + Tree也是一种多路搜索树，基于B - Tree做出的改进，更适合在操作系统中进行文件索引

2. B+树与B-树的差异

   ① 有k个孩子的节点就有k个关键字。但在B-树种，孩子数量 = 关键字 + 1。

   ② 非叶子节点仅用于索引，不保存数据记录，跟记录有关的信息都放在叶子节点中。B-树中，非叶子节点既保存索引，也保存数据记录

   ③ 所有关键字都在叶子节点中，并构成一个有序链表。B - 树中的关键字在整颗树中，所以无法构成一个有序链表，搜索过程呈现M状。

3. 特色

   因B+树的中间节点并不直接存储数据，所以致使B+树

   ① B+树查询效率更稳定

   ② B+树查询效率更高，因为B+树的中间节点不存储数据，就可以存储更多的目录项，从而使得B+树比B树更

   ​ 矮胖，从而查询所需的磁盘I/O会更少。

4. 优势

   因为特色1和2的原因，所以B+树更适用于在操作系统中的文件索引

六、Hash索引于B+树索引的区别

1. 主要是因为数据的有序/无序

   	Hash索引	B+树索引
   1	不能进行范围查询 因为其索引指向的数据是无序的	可以进行范围查询 因为其叶子节点是有序链表
   2	不支持联合索引的最左侧原则	可以进行联合索引
   3	不支持ORDER BY排序	支持ORDER BY排序
   4	不可以使用模糊查询

小结

1. 基于上述对比和各索引的优势，MySQL最终选择B+树索引。

2. 使用索引可以帮助我们从海量的数据中快速定位想要查找的数据，不过索引也存在一些不足，比如占用存储空间，降低数据库写操作的性能等，如果有多个索引还会增加许哦因选择的时间。当我们使用索引时，需要平衡索引的利（提升查询效率）和弊（维护索引的代价）

   在实际工作中，我们还需要 基于需求和数据本身的分布情况来确定是否使用索引，尽管索引不是万能的，但是数据量巨大时，不适用索引是不可想象的，毕竟索引的本质就是帮助我们提升数据检索的效率。