Mysql索引（二）

索引底层数据结构

从数据结构的角度来看，MySQL常见索引有B+Tree索引、HASH索引、Full-Text索引。InnoDB是在 MySQL 5.5 之后成为默认的MySQL 存储引擎，B+Tree 索引类型也是MySQL存储引擎采用最多的索引类型。

Hash索引

Hash索引是将一列或者多列数据值，进行hash运算并将结果映射到数组的某个位置上。当Hash值冲突时, 会追加一个链表存储数据。整个结构与Java中的HashMap相似。哈希表

是键值对的集合，通过键(key)即可快速取出对应的值(value)，因此哈希表可以快速检索数据（接近 O(1)）。

🤔 为何能够通过key快速取出 value 呢？原因在于哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到key对应的index，找到了index也就找到了对应的value。
但是哈希算法有个Hash冲突问题，也就是说多个不同的key最后得到的index相同。通常情况下，我们常用的解决办法是链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如JDK1.8之前HashMap就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
为了减少Hash冲突的发生，一个好的哈希函数应该均匀地将数据分布在整个哈希值集合中。

InnoDB不直接支持常规的哈希索引，但是InnoDB中有一种特殊的自适应哈希索引（Adaptive Hash Index），自适应哈希索引并不是传统意义上的哈希索引，而是结合了B+Tree

和哈希索引的特点，以便更好地适应实际应用中的数据访问模式和性能需求。自适应哈希索引的每个哈希桶实际上是一个小型的B+Tree结构。这个 B+Tree 结构可以存储多个键值

对，而不仅仅是一个键。这有助于减少哈希冲突链的长度，提高了索引的效率。

既然哈希表这么快，为什么MySQL没有使用其作为索引的数据结构呢？主要是因为Hash索引不支持顺序和范围查询。假如我们要对表中的数据进行排序或者进行范围查询，那Hash索引可就不行了。并且每次IO只能取一个。

二叉查找树(BST)

二叉查找树（Binary Search Tree）是一种基于二叉树的数据结构，在一般情况下，查询效率比链表结构要高。它具有以下特点：

• 左子树所有节点的值均小于根节点的值
• 右子树所有节点的值均大于根节点的值
• 左右子树也分别为二叉查找树

当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过1的时候，查询的时间复杂度为O(log2(N))，具有比较高的效率；当二叉查找树不平衡时，例如在最

坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为O(N)。

数据量大的情况下，会导致树的高度变高，如果每个节点对应磁盘的一个块来存储一条数据，IO次数大幅增加，显然用此结构来存储数据是不可取的。也就是说，二叉查找树的性

能非常依赖于它的平衡程度，这就导致其不适合作为 MySQL 底层索引的数据结构。

平衡二叉树(AVL)

AVL树是自平衡二叉查找树，特点是保证任何节点的左右子树高度之差不超过1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。

AVL树采用了旋转操作来保持平衡。主要有四种旋转操作：LL旋转、RR旋转、LR旋转和RL旋转。其中LL旋转和RR旋转分别用于处理左左和右右失衡，而LR旋转和RL旋转则用于处理左右和右左失衡。

由于AVL树需要频繁地进行旋转操作来保持平衡，因此会有较大的计算开销进而降低了数据库写操作的性能。并且 在使用AVL树时，每个树节点仅存储一个数据，而每次进行磁盘IO时只能读取一个节点的数据，如果需要查询的数据分布在多个节点上，那么就需要进行多次磁盘IO。 磁盘IO是一项耗时的操作，在设计数据库索引时，我们需要优先考虑如何最大限度地减少磁盘IO操作的次数。

如果数据都存储在内存中，采用AVL树来存储，还是可以的，查询效率非常高。不过我们的数据是存在磁盘中，采用这种结构，每个节点对应一个磁盘块，数据量大的时候，也会和二叉树一样，会导致树的高度变高，这样逻辑上很近的节点实际可能非常远，无法很好的利用磁盘预读（局部性原理），会增加IO次数，所以用这种结构存储数据也是不可取的。

红黑树

红黑树是一种自平衡二叉查找树，通过在插入和删除节点时进行颜色变换和旋转操作，使得树始终保持平衡状态，它具有以下特点：

• 每个节点非红即黑
• 根节点总是黑色的
• 每个叶子节点都是黑色的空节点（NIL 节点）
• 如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
• 从任意节点到它的叶子节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）

和AVL树不同的是，红黑树并不追求严格的平衡，而是大致的平衡，也可以称为弱平衡。正因如此，红黑树的查询效率稍有下降，因为红黑树的平衡性相对较弱，可能会导致树的高度较高，这可能会导致一些数据需要进行多次磁盘IO操作才能查询到，这也是MySQL没有选择红黑树的主要原因。也正因如此，红黑树的插入和删除操作效率大大提高了，因为红黑树在插入和删除节点时只需进行 O(1) 次数的旋转和变色操作，即可保持基本平衡状态，而不需要像AVL树一样进行O(logn)次数的旋转操作。

红黑树的应用还是比较广泛的，TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。对于数据在内存中的这种情况来说，红黑树的表现是非常优异的。

B-Tree

B-Tree这里的B表示balance，是一种自平衡的树，能够保持数据有序，B-Tree允许每个节点有更多的子节点。B-Tree不利于范围查找，范围查找也是我们经常用到的，所以B-Tree也不太适合在磁盘中存储需要检索的数据。

B+Tree

MySQL索引的实现采用的是B+Tree，B+Tree是B-Tree的变体，也是一棵多路搜索树。B+Tree相较于B-Tree最主要的特点是：数据只出现在叶子节点；所有叶子节点增加了一个链指针。

B+Tree中所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。B+Tree的叶子节点上有指针相连，因此在做数据遍历的时候，只需要对叶子节点进行遍历即可，这个特性使得B+Tree非常适合做范围查询。

🤔 那么为什么InnoDB选择B+tree作为索引的数据结构呢 ？

MySQL选择使用B+tree作为索引结构，主要是因为B+tree提供了许多适合数据库索引的优点：

1. 高效的查找和范围查询性能：B+tree的结构使得查找操作非常高效。所有的叶节点都按键值的顺序存储并且相互链接，这使得对于范围查询特别高效。
2. 节省磁盘空间：B+tree中只有叶节点包含数据指针或实际的数据值，而内部节点只存储键值。这样的设计减少了内部节点所需的空间，使得更多的键值可以存储在一个节点中，从而减少了磁盘I/O次数。
3. 优化磁盘I/O操作：数据库系统常常运行在存储数据的磁盘驱动器上。B+tree的结构减少了节点分裂的频率，并且由于叶节点是顺序访问的，所以它们特别适合磁盘的顺序读取特性。
4. 更好的缓存利用性：由于内部节点不包含实际数据，而只包含键值，这意味着更多的键值可以被缓存在内存中，从而减少访问磁盘的次数。
5. 支持顺序和随机访问：B+tree通过其叶节点的链表结构支持高效的顺序访问，同时也支持随机数据访问。
6. 写操作的性能：B+tree减少了因插入或删除操作而导致的树重新平衡的频率。

B+Tree vs Hash

Hash在做等值查询的时候效率很高，搜索时间复杂度为 O(1)。但是Hash表不适合做范围查询，它更适合做等值的查询，这也是B+Tree索引比Hash索引有着更广泛的适用场景的原因。

B+Tree vs 二叉树

对于有N个叶子节点的B+Tree，其搜索复杂度为 O(logdN)，其中d表示节点允许的最大子节点个数为d个。

在实际的应用当中，d值是大于100的，这样就保证了即使数据达到千万级别时，B+Tree的高度依然维持在3 ~ 4层左右，也就是说一次数据查询操作只需要做3~4次的磁盘I/O操作就能查询到目标数据。

而二叉树的每个父节点的儿子节点个数只能是2个，意味着其搜索复杂度为O(logN)，这已经比B+Tree高出不少，因此二叉树检索到目标数据所经历的磁盘I/O次数要更多。并且如果二叉树受插入顺序影响特殊化为一个链表，相当于全表扫描。平衡二叉树相比于二叉查找树来说，查找效率更稳定，总体的查找速度也更快。但是平衡二叉树可是每个节点只存储一个键值和数据的，并且每次新增数据，平衡二叉树都会进行大量的平衡判断。

B+Tree & B-Tree

BTree也称B-Tree全称为多路平衡查找树 ，B+Tree是BTree的一种变体。BTree和B+Tree中的B是Balanced （平衡）的意思。

目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构的。

B+Tree的磁盘读写代价更低：B+Tree的内部节点并没有指向关键字具体信息的指针，因此其内部节点相对BTree更小，如果把所有同一内部节点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多，一次性读入内存的需要查找的关键字也就越多，相对IO读写次数就降低了。

B+Tree的查询效率更加稳定：由于非终节点并不是最终指向文件内容的节点，而只是叶子节点中关键字的索引。所以任何关键字的查找必须走一条从根节点到叶子节点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。

由于B+Tree的数据都存储在叶子节点中，分支节点均为索引方便扫库，只需要扫一遍叶子节点即可，但是BTree因为其分支节点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+Tree更加适合在区间查询的情况，所以通常B+Tree树用于数据库索引。

B-Tree & B+Tree的异同：

• B-Tree的所有节点既存放键(key) 也存放数据(data)，而B+Tree只有叶子节点存放key和data，其他内节点只存放 key。
• B-Tree的叶子节点都是独立的，B+Tree的叶子节点有一条引用链指向与它相邻的叶子节点。
• B-Tree的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而B+Tree的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
• 在B-Tree中进行范围查询时，首先找到要查找的下限，然后对B-Tree进行中序遍历，直到找到查找的上限；而B+Tree的范围查询，只需要对链表进行遍历即可。
• B-Tree因为非叶子节点也保存具体数据，所以在查找某个关键字的时候找到即可返回。而B+Tree所有的数据都在叶子节点，每次查找都得到叶子节点。所以在同样高度的B-Tree和B+Tree中，B-Tree查找某个关键字的效率更高。
• B+Tree只在叶子节点存储数据，而B-Tree的非叶子节点也要存储数据，所以B+Tree的单个节点的数据量更小，在相同的磁盘I/O次数下，就能查询更多的节点。
• B+Tree叶子节点采用的是双向链表连接，适合MySQL中常见的基于范围的顺序查找，而B-Tree无法做到这一点。

综上，B+Tree与B-Tree相比，具备更少的IO次数、更稳定的查询效率和更适于范围查询这些优势。