• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

B树与B+树区别辨析

开发技术 开发技术 2周前 (01-11) 9次浏览

我们都知道,innodb中的索引结构使用的是B+树。B+树是一种B树的变形树,而B树又是来源于平衡二叉树。相较于平衡二叉树,B树更适合磁盘场景下文件索引系统。那为什么B树更适合磁盘场景,B+树又在B树基础上做了什么优化?抱着这些问题,本博客将深入分析B树和B+树来龙去脉,其中会涉及到二叉排序树和平衡二叉树等数据结构。

二叉排序树、平衡二叉树、B树和B+树都是基于二分法的思路来优化查找的。

二叉排序树

要谈B树,首先要理解平衡二叉树。而平衡二叉树又是从二叉排序树优化而来。让我们追根溯源先看看二叉排序树。这个数据结构非常容易理解,满足如下性质即为一棵二叉排序

  • 若左子树不为空,则左子树上所有结点值均小于它的根结点值;
  • 若右子树不为空,则右子树上所有结点值均大于等于它的根结点值;
  • 左右子树也分别是二叉排序树。

中序遍历一棵二叉排序树能得到一个递增的有序序列

问题:二叉排序树的查找性能受限于它的结构,如果结构合理,复杂度能达到二分法的复杂度,O(log2N);而在极端情况下,往二叉排序树中插入结点,会得到一个单链表,这样时间复杂度就是O(N)了。树的高度越小,查找速度越快。

平衡二叉树

为了使二叉排序树高度尽可能小,平衡二叉树诞生了,也成为AVL树。这种数据结构,是具备如下特征的二叉排序树:

  • 左子树和右子树深度之差绝对值不超过1;
  • 左子树和右子树也是平衡二叉树。

平衡二叉树通过“旋转”操作来保证左右子树深度之差小于等于1,从而保证树的高度尽可能小。

问题:虽说平衡二叉树可以保证一定的查找效率。即便这样,平衡二叉树方法也只适用于存储在内存中的较小的文件,如果是查找存放在外存中很大的文件,每访问一个结点就需要进行磁盘IO,由于节点众多,开销依然很大。

B树

既然结点太多了,那将多个结点合成一个节点如何,是否可以减少IO次数。这样也相当于将二叉树变成多叉树。B树也是基于这个思路来实现的,即一个结点包含多个关键字(表示要查找的目标数值)和多个指向子树的指针。
对于一个m阶的B树,拥有如下特性:

  • 树中每个结点至多有m棵子树;
  • 若根结点不是叶子结点,则至少有两棵子树;
  • 除了根结点以外的所有非终端结点,至少有m/2棵子树;
  • 所有叶子结点都出现在同一层次上(这体现出平衡的特点),并且不带信息,成为失败结点;
  • 所有非终端结点最多有m-1个关键字。

在实际的文件系统场景中,B树的结点规模一般以一个磁盘页为单位,所以m值取决于磁盘页大小

结点结构如下所示

B树与B+树区别辨析

第一个元素n记录当前结点的关键字数量。K1 – Kn 表示各个关键字,P0 – Pn 表示指向子树根结点的指针。重要性质:Pi所指向子树中所有结点关键字均大于Ki,并且小于Ki+1。B树便是依据此性质来完成查找。

因此,B树查找的过程与平衡二叉树类似,无需赘述。但是插入和删除不太一样。

插入

以插入为例,假设要向一个m阶B树插入某个关键字,B树会先查找该关键字在最底层的位置,向对应的位置插入。同时保证结点数量不超过m-1,如果超过数量限制,则会进行结点“分裂”,以中间关键字为界将结点一分为二,并将中间关键字向上插入到双亲结点上,若双亲结点已满,用同样的方法继续分解,直到分解到根节点,此时B树高度加1。

删除

对于删除而言,同理,如果结点的关键字删除后数量小于(m/2)-1则要进行“合并”结点的操作。除了删除关键字,还需要删除关键字邻近的指针。例如删除Ki时,也需要删除Pi。这里就有两种情况,若删除的结点Pi是最低层,直接删除Ki和Pi即可,因为指针指向null;如果不是,不能直接删,因为Pi指向一棵子树,这时需要将Pi指向的子树里最小的关键字与待删除关键字互换,互换之后目标关键字一定是转移到了最低一层,将其和相邻指针删除即可。

B+树

B树已经是很优秀的数据结构了,为什么还需要B+树呢?先来看看二者的区别。B+树是B树的变形树,它们的差异如下:

  • 有n棵子树的结点中含有n个关键字;
  • 所有叶子结点中包含全部关键字信息,以及指向含有这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接;
  • 所有非终端结点可以看成是索引部分,结点中仅含有其子树中的最大或最小关键字(innodb中是最小关键字)

B+树的随机查找、插入和删除过程基本与B树类似

与B树相比的优势

1.查询的IO次数更少

其实上文在B树中提到的关键字,不仅仅只是数值,也包含具体的数据。读取结点,也会把各个关键字对应的具体数据读取出来。而在B+树中对于非终端节点而言,每一个关键字只是一个索引,不包含其它数据(只有终端结点才会引用具体数据)。因此,在单个结点大小一致的前提下(取磁盘页的大小),B+树中每个非终端结点结点可以存储更多元素,因此树的分支会更多,更加矮胖,查询的IO次数也更少。

2.查询性能稳定

B树查询不同结点性能可能不一样,因为目标元素可能位于根节点,也可能在叶子结点上。但是B+树中有效结点一定在最低层,所以每次查找必须查到叶子结点,性能稳定。

3.便于范围查询

范围查询,B树需要进行多次二分查找。而B+树只需要一次二分查找找到下限,之后再顺着链表找到上限即可。叶子结点通过链表互相连接这一事实,决定了B+树在范围查询上的优势。

综上所述,在MySQL索引结构中使用B+树性能要更优于B树。


喜欢 (0)