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(logn),在插入和删除操作引入了旋转、变色等机制,确保平衡性,无需频繁重构树结构
红黑规则:
-
每个节点都有一个颜色属性,可以是红色或黑色。
-
红黑树的根节点必须是黑色。
-
所有的叶子节点(即树中的
null
节点)是黑色的。叶子节点不包含数据,只是辅助结构。 -
如果一个节点是红色的,则其子节点必须是黑色。这确保了没有两个红色节点相连,从而避免了树的高度过高。
-
任何路径从根节点到叶子节点或者空节点的过程中,必须经过相同数量的黑色节点。这保证了红黑树的平衡性,避免了一些路径比其他路径过长,从而影响查找效率。
但是当数据规模量巨大时,他也会暴露出来缺点:深度较大
因此红黑数无法适应大规模数据,而且每个节点只存储一个键值,导致树的层数增加,浪费存储空间,红黑树需要通过中序遍历才能完成范围查询,因此在大规模数据量的场景下,查询效率依然不高
B树
B树(B-tree)是一种自平衡的多路搜索树,它能够保持数据有序,并允许高效的插入、删除和查找操作
B树的特点包括:
- 平衡性:B树是一种平衡树,所有叶子节点的深度相同。通过这种结构,B树保证了对所有节点的访问时间是相同的,从而提高了查找效率。
- 多路性:B树的每个节点可以有多个子节点(通常是
m
个子节点)。这使得B树能够存储更多的数据,并且能更快地完成查找、插入、删除等操作。 - 节点结构:每个节点包含若干个关键字(data),并且包含指向其子节点的指针。对于每个节点中的关键字,子节点的关键字范围是有序的。
- 查找效率:B树的查找操作类似于二叉查找树,但是每个节点具有多个子节点。查找操作的时间复杂度为O(log n),其中n是树中的元素个数。
- 插入和删除操作:插入和删除操作需要保证树的平衡性,插入时可能会导致节点分裂,删除时可能会引起节点合并或借用关键字。所有这些操作都在O(log n)时间内完成。
他的单个节点可以存储多个数据和多个指针,每个节点也可以有多个分支,因此他的每一层级可以存放大量数据,同样遵循左边大右边小的存储规则,因此B树的查找效率是十分优秀的,B树通常用于数据库和文件系统中,用于存储和管理大量数据
但是MySQL中使用的数据结构并不是B树,而是B+树,相比B树,B+树更加优秀
B+树
B+树是B树的变种,它具有与B树类似的结构和特点,但在某些方面有所改进,特别是在存储和查找效率上。B+树通常用于数据库和文件系统中,作为一种高效的索引结构
- 所有数据都存储在叶子节点中:
- 在B树中,数据可以存储在内部节点和叶子节点中,而在B+树中,所有的数据(即关键字)都仅存储在叶子节点中。内部节点只存储关键字,用于引导查找过程。
- 这种设计可以减少内部节点的存储空间,提高查询效率。
- 叶子节点通过链表连接:
- B+树的叶子节点通常是通过一个链表连接起来的,这使得范围查询(例如查找某个区间内的所有数据)变得更加高效。通过遍历链表,可以一次性返回区间内的所有数据,而不需要回溯到其他节点。
- 树的高度较小:
- 由于所有数据都存储在叶子节点中,B+树的内部节点只需要存储关键字和指向子节点的指针。因此,相比于B树,B+树可以将更多的数据存储在每个节点中,从而使树的高度变得更小,查找操作的效率更高。
- 查找操作的效率更高:
- B+树的查找操作通常仅限于叶子节点,而B树在查找时可能需要在内部节点和叶子节点之间反复跳转。由于叶子节点之间有链表连接,B+树在范围查询时特别高效。
B+树相较于B树,在查找和范围查询上有显著的优势,尤其在数据库和文件系统中,因为它能够有效地减少磁盘I/O操作,并提高查询效率。因此,MySQL选择了B+树作为索引的数据结构