MySQL索引为什么是B+树

MySQL索引为什么是B+树

---

索引是帮助MySQL高效获取数据的数据结构，在数据之外，数据库还维护着满足特定查找算法的数据结构B+树，这些数据结果以某种特定的方式引用数据，这样就可以在这些数据结构上实现高级查找算法，提升数据的查找速度，这种数据结构就是索引

如果此时有一个user表，在它还未建立索引的时候，如果想要查找age为35岁的用户：

select * from user where age = 35

那么此时在user表中会逐个查找每一行，直到查找到最后一行，然后返回age为35的行

id	name	username	age
1001	张三	zhangsan	20
1002	李四	lisi	18
1003	王九	wangjiu	35
1004	赵六	zhaoliu	22
1005	王八	wangba	17

这样的查找无疑是非常耗时的，当数据量非常庞大时，全部检索整张表会消耗大量的时间和性能，因此需要为数据建立合适的索引来提高查询的效率

那为什么MySQL采用的是B+数呢？而不是二叉树、红黑数呢？

二叉树

二叉树在查找时，使用的是二分查找算法，查询效率得到了提高，并且二叉树简单易实现，当数据量较小时，普通二叉树的性能已经能满足要求，开销更小

但是二叉树有一个非常致命的缺点：高度不稳定

普通二叉树在数据分布不均时可能变成链表状，最坏情况下高度为 O(n)，影响查找性能：

---

红黑树

红黑树是一种自平衡二叉搜索树，保证任何路径的最大深度不超过最小深度的两倍，自平衡的特性完美解决了二叉树中高度不稳定的特点，查找、插入和删除操作的时间复杂度始终保持在 O(log⁡n)，在插入和删除操作引入了旋转、变色等机制，确保平衡性，无需频繁重构树结构

红黑规则：

• 每个节点都有一个颜色属性，可以是红色或黑色。

• 红黑树的根节点必须是黑色。

• 所有的叶子节点（即树中的 null 节点）是黑色的。叶子节点不包含数据，只是辅助结构。

• 如果一个节点是红色的，则其子节点必须是黑色。这确保了没有两个红色节点相连，从而避免了树的高度过高。

• 任何路径从根节点到叶子节点或者空节点的过程中，必须经过相同数量的黑色节点。这保证了红黑树的平衡性，避免了一些路径比其他路径过长，从而影响查找效率。

但是当数据规模量巨大时，他也会暴露出来缺点：深度较大

因此红黑数无法适应大规模数据，而且每个节点只存储一个键值，导致树的层数增加，浪费存储空间，红黑树需要通过中序遍历才能完成范围查询，因此在大规模数据量的场景下，查询效率依然不高

---

B树

B树（B-tree）是一种自平衡的多路搜索树，它能够保持数据有序，并允许高效的插入、删除和查找操作

B树的特点包括：

1. 平衡性：B树是一种平衡树，所有叶子节点的深度相同。通过这种结构，B树保证了对所有节点的访问时间是相同的，从而提高了查找效率。
2. 多路性：B树的每个节点可以有多个子节点（通常是 m 个子节点）。这使得B树能够存储更多的数据，并且能更快地完成查找、插入、删除等操作。
3. 节点结构：每个节点包含若干个关键字（data），并且包含指向其子节点的指针。对于每个节点中的关键字，子节点的关键字范围是有序的。
4. 查找效率：B树的查找操作类似于二叉查找树，但是每个节点具有多个子节点。查找操作的时间复杂度为O(log n)，其中n是树中的元素个数。
5. 插入和删除操作：插入和删除操作需要保证树的平衡性，插入时可能会导致节点分裂，删除时可能会引起节点合并或借用关键字。所有这些操作都在O(log n)时间内完成。

他的单个节点可以存储多个数据和多个指针，每个节点也可以有多个分支，因此他的每一层级可以存放大量数据，同样遵循左边大右边小的存储规则，因此B树的查找效率是十分优秀的，B树通常用于数据库和文件系统中，用于存储和管理大量数据

但是MySQL中使用的数据结构并不是B树，而是B+树，相比B树，B+树更加优秀

---

B+树

B+树是B树的变种，它具有与B树类似的结构和特点，但在某些方面有所改进，特别是在存储和查找效率上。B+树通常用于数据库和文件系统中，作为一种高效的索引结构

1. 所有数据都存储在叶子节点中：
   • 在B树中，数据可以存储在内部节点和叶子节点中，而在B+树中，所有的数据（即关键字）都仅存储在叶子节点中。内部节点只存储关键字，用于引导查找过程。
   • 这种设计可以减少内部节点的存储空间，提高查询效率。
2. 叶子节点通过链表连接：
   • B+树的叶子节点通常是通过一个链表连接起来的，这使得范围查询（例如查找某个区间内的所有数据）变得更加高效。通过遍历链表，可以一次性返回区间内的所有数据，而不需要回溯到其他节点。
3. 树的高度较小：
   • 由于所有数据都存储在叶子节点中，B+树的内部节点只需要存储关键字和指向子节点的指针。因此，相比于B树，B+树可以将更多的数据存储在每个节点中，从而使树的高度变得更小，查找操作的效率更高。
4. 查找操作的效率更高：
   • B+树的查找操作通常仅限于叶子节点，而B树在查找时可能需要在内部节点和叶子节点之间反复跳转。由于叶子节点之间有链表连接，B+树在范围查询时特别高效。

B+树相较于B树，在查找和范围查询上有显著的优势，尤其在数据库和文件系统中，因为它能够有效地减少磁盘I/O操作，并提高查询效率。因此，MySQL选择了B+树作为索引的数据结构