1.Hash表

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

为何能够通过 key 快速取出 value 呢？ 原因在于 哈希算法（也叫散列算法）。通过哈希算法，我们可以快速找到 key 对应的 index，找到了 index 也就找到了对应的 value
image.png|425

哈希算法有个 Hash 冲突 问题，也就是说多个不同的 key 最后得到的 index 相同。通常情况下，我们常用的解决办法是 链地址法。链地址法就是将哈希冲突数据存放在链表中。就比如 JDK1.8 之前 HashMap 就是通过链地址法来解决哈希冲突的。不过，JDK1.8 以后HashMap为了减少链表过长的时候搜索时间过长引入了红黑树。
image.png|425

为了减少 Hash 冲突的发生，一个好的哈希函数应该“均匀地”将数据分布在整个可能的哈希值集合中。

MySQL 的 InnoDB 存储引擎不直接支持常规的哈希索引，但是，InnoDB 存储引擎中存在一种特殊的“自适应哈希索引”（Adaptive Hash Index），自适应哈希索引并不是传统意义上的纯哈希索引，而是结合了 B+Tree 和哈希索引的特点，以便更好地适应实际应用中的数据访问模式和性能需求。自适应哈希索引的每个哈希桶实际上是一个小型的 B+Tree 结构。这个 B+Tree 结构可以存储多个键值对，而不仅仅是一个键。这有助于减少哈希冲突链的长度，提高了索引的效率

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

缺点：Hash表不支持顺序和范围查找

2.二叉查找树(BST)

二叉查找树（Binary Search Tree）是一种基于二叉树的数据结构，它具有以下特点：

  1. 左子树所有节点的值均小于根节点的值。
  2. 右子树所有节点的值均大于根节点的值。
  3. 左右子树也分别为二叉查找树。

当二叉查找树是平衡的时候，也就是树的每个节点的左右子树深度相差不超过 1 的时候，查询的时间复杂度为 O(log2(N))，具有比较高的效率。然而，当二叉查找树不平衡时，例如在最坏情况下（有序插入节点），树会退化成线性链表（也被称为斜树），导致查询效率急剧下降，时间复杂退化为 O（N）

image.png|207

也就是说，二叉查找树的性能非常依赖于它的平衡程度，这就导致其不适合作为 MySQL 底层索引的数据结构。

为了解决这个问题，并提高查询效率，人们发明了多种在二叉查找树基础上的改进型数据结构，如平衡二叉树、B-Tree、B+Tree 等。

缺点：二叉搜索树依赖于平衡程度，可能退化为链表，时间复杂度为O(n)

3.AVL 树

AVL 树是计算机科学中最早被发明的自平衡二叉查找树，它的名称来自于发明者 G.M. Adelson-Velsky 和 E.M. Landis 的名字缩写。AVL 树的特点是保证任何节点的左右子树高度之差不超过 1，因此也被称为高度平衡二叉树，它的查找、插入和删除在平均和最坏情况下的时间复杂度都是 O(logn)。

image.png|375

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

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

实际应用中，AVL 树使用的并不多

缺点：频繁的旋转操作会有较大的计算开销；AVL树每个节点仅存储一个节点的数据，查询多个数据时会进行多次IO操作

4.红黑树

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

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

image.png|425

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

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

缺点：红黑树查询效率稍有下降；树的高度可能较高，需要多次IO才能查询到；

5.B 树& B+树

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

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

B 树& B+树两者有何异同呢？

  • B 树的所有节点**既存放键(key) 也存放数据(data)**，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
  • B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
  • B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。
  • 在 B 树中进行范围查询时，首先找到要查找的下限，然后对 B 树进行中序遍历，直到找到查找的上限；而 B+树的范围查询，只需要对链表进行遍历即可。

在 MySQL 中，MyISAM 引擎和 InnoDB 引擎都是使用 B+Tree 作为索引结构，但是，两者的实现方式不太一样。

6.B+树的优缺点

B+树是一种广泛使用的数据结构，特别是在数据库系统和文件系统中作为索引结构。以下是 B+树的主要优点和缺点：

B+树的优点：

  1. 高效检索：
  • B+树的所有叶子节点都位于同一层，这保证了每次检索的时间复杂度都是 O(log n)，其中 n 是树中节点的数量。
  • 每个节点存储更多的键值对，这减少了树的高度，提高了检索效率。
  1. 支持范围查询：
  • B+树的所有叶子节点通过指针链接在一起，这样可以很容易地遍历所有叶子节点来进行范围查询或者排序输出。
  1. 良好的磁盘 I/O 性能：
  • B+树设计时考虑到了磁盘 I/O 的性能，每个节点存储大量的数据，减少了磁盘访问次数。
  • 磁盘 I/O 通常比内存访问慢得多，因此减少磁盘访问次数对于提高性能至关重要。
  1. 易于维护：
  • B+树在插入和删除操作上保持良好的平衡，使得树的结构更加稳定，从而降低了维护成本。
  1. 支持并发操作：
  • 由于 B+树的内部节点不包含数据，只包含指向叶子节点的指针，这使得锁定机制更容易实现，从而支持高并发操作。

B+树的缺点：

  1. 额外的空间开销：
  • B+树的每个节点都有指向下一个节点的指针，这增加了额外的空间消耗。
  • 叶子节点之间的链接指针可能会占用较多的空间，尤其是在大型数据集上。
  1. 内存使用效率较低：
  • 与 B 树相比，B+树的内部节点不存储数据，这意味着更多的空间用于存储索引而不是实际的数据，这可能在某些场景下导致内存使用效率降低。
  1. 不适合随机访问：
  • 虽然 B+树适合顺序访问，但在进行随机数据访问时效率不如哈希表等数据结构。
  1. 插入和删除操作可能导致节点分裂和合并：
  • 插入或删除操作可能导致节点的分裂或合并，这虽然不会影响性能，但增加了操作的复杂性。

总的来说，B+树非常适合用于需要频繁进行范围查询和排序输出的场合，尤其是在磁盘存储中。在内存数据库或不需要进行大量范围查询的应用场景中，B 树或其他数据结构可能会更为合适。