时间:2021-05-02
前言
在mysql中,无论是innodb还是myisam,都使用了b+树作索引结构(这里不考虑hash等其他索引)。本文将从最普通的二叉查找树开始,逐步说明各种树解决的问题以及面临的新问题,从而说明mysql为什么选择b+树作为索引结构。
二叉查找树(bst,binary search tree),也叫二叉排序树,在二叉树的基础上需要满足:任意节点的左子树上所有节点值不大于根节点的值,任意节点的右子树上所有节点值不小于根节点的值。如下是一颗bst:
当需要快速查找时,将数据存储在bst是一种常见的选择,因为此时查询时间取决于树高,平均时间复杂度是o(lgn)。然而,bst可能长歪而变得不平衡,如下图所示,此时bst退化为链表,时间复杂度退化为o(n)。
为了解决这个问题,引入了平衡二叉树。
avl树是严格的平衡二叉树,所有节点的左右子树高度差不能超过1;avl树查找、插入和删除在平均和最坏情况下都是o(lgn)。
avl实现平衡的关键在于旋转操作:插入和删除可能破坏二叉树的平衡,此时需要通过一次或多次树旋转来重新平衡这个树。当插入数据时,最多只需要1次旋转(单旋转或双旋转);但是当删除数据时,会导致树失衡,avl需要维护从被删除节点到根节点这条路径上所有节点的平衡,旋转的量级为o(lgn)。
由于旋转的耗时,avl树在删除数据时效率很低;在删除操作较多时,维护平衡所需的代价可能高于其带来的好处,因此avl实际使用并不广泛。
与avl树相比,红黑树并不追求严格的平衡,而是大致的平衡:只是确保从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。从实现来看,红黑树最大的特点是每个节点都属于两种颜色(红色或黑色)之一,且节点颜色的划分需要满足特定的规则(具体规则略)。红黑树示例如下:
与avl树相比,红黑树的查询效率会有所下降,这是因为树的平衡性变差,高度更高。但红黑树的删除效率大大提高了,因为红黑树同时引入了颜色,当插入或删除数据时,只需要进行o(1)次数的旋转以及变色就能保证基本的平衡,不需要像avl树进行o(lgn)次数的旋转。总的来说,红黑树的统计性能高于avl。
因此,在实际应用中,avl树的使用相对较少,而红黑树的使用非常广泛。例如,java中的treemap使用红黑树存储排序键值对;java8中的hashmap使用链表+红黑树解决哈希冲突问题(当冲突节点较少时,使用链表,当冲突节点较多时,使用红黑树)。
对于数据在内存中的情况(如上述的treemap和hashmap),红黑树的表现是非常优异的。但是对于数据在磁盘等辅助存储设备中的情况(如mysql等数据库),红黑树并不擅长,因为红黑树长得还是太高了。当数据在磁盘中时,磁盘io会成为最大的性能瓶颈,设计的目标应该是尽量减少io次数;而树的高度越高,增删改查所需要的io次数也越多,会严重影响性能。
b树也称b-树(其中不是减号),是为磁盘等辅存设备设计的多路平衡查找树,与二叉树相比,树的每个非叶节点可以有多个子树。因此,当总节点数量相同时,b树的高度远远小于avl树和红黑树(b树是一颗“矮胖子”),磁盘io次数大大减少。
定义b树最重要的概念是阶数(order),对于一颗m阶b树,需要满足以下条件:
可以看出,b树的定义,主要是对非叶结点的子节点数量和记录数量的限制。
下图是一个3阶b树的例子:
b树的优势除了树高小,还有对访问局部性原理的利用。所谓局部性原理,是指当一个数据被使用时,其附近的数据有较大概率在短时间内被使用。b树将键相近的数据存储在同一个节点,当访问其中某个数据时,数据库会将该整个节点读到缓存中;当它临近的数据紧接着被访问时,可以直接在缓存中读取,无需进行磁盘io;换句话说,b树的缓存命中率更高。
b树在数据库中有一些应用,如mongodb的索引使用了b树结构。但是在很多数据库应用中,使用了是b树的变种b+树。
b+树也是多路平衡查找树,其与b树的区别主要在于:
由此,b+树与b树相比,有以下优势:
b+树也存在劣势:由于键会重复出现,因此会占用更多的空间。但是与带来的性能优势相比,空间劣势往往可以接受,因此b+树的在数据库中的使用比b树更加广泛。
前面说到,b树/b+树与红黑树等二叉树相比,最大的优势在于树高更小。实际上,对于innodb的b+索引来说,树的高度一般在2-4层。下面来进行一些具体的估算。
树的高度是由阶数决定的,阶数越大树越矮;而阶数的大小又取决于每个节点可以存储多少条记录。innodb中每个节点使用一个页(page),页的大小为16kb,其中元数据只占大约128字节左右(包括文件管理头信息、页面头信息等等),大多数空间都用来存储数据。
对于一颗3层b+树,第一层(根节点)有1个页面,可以存储1000条记录;第二层有1000个页面,可以存储1000 * 1000条记录;第三层(叶节点)有1000 * 1000个页面,每个页面可以存储100条记录,因此可以存储1000 * 1000 * 100条记录,即1亿条。而对于二叉树,存储1亿条记录则需要26层左右。
最后,总结一下各种树解决的问题以及面临的新问题:
以上就是mysql用b+树作为索引结构有什么好处的详细内容,更多关于mysql b+树索引结构的资料请关注服务器之家其它相关文章!
原文链接:https://juejin.cn/post/6916392833460994062
声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。
前言由于MySQL的索引中最重要的数据结构就是B+树,所以前面我们先大概讲讲B+树的原理B+Tree原理1.数据结构BTree指的是BalanceTree,也就
B-树是一种常见的数据结构。和他一起的还有B+树。在这里,需要澄清一下概念。B树,B-树,B+树有什么区别?他们有什么关系呢?其实,从数据结构来讲只有2种,也就
搞懂这个问题之前,我们首先来看一下mysql表的存储结构,再分别对比二叉树、多叉树、b树和b+树的区别就都懂了。mysql的存储结构表存储结构单位:表>段>区>
Q1:数据库有哪些索引?优缺点是什么?1.B树索引:大多数数据库采用的索引(innoDB采用的是b+树)。能够加快访问数据的速度,尤其是范围数据的查找非常快。缺
以下是基于我结合B+树的数据结构和对实验结果的推测作出的判断,如有错误,恳请指正!今天实验了一下MySQL的count()操作优化,以下讨论基于mysql5.7