浅谈MySQL索引为什么是B+树_Mysql

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)，在插入和删除操作引入了旋转、变色等机制，确保平衡性，无需频繁重构树结构

红黑规则：

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

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

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

b树的特点包括：

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