b树与b+树的区别是什么?各自有什么优点?

KLQ 2020-05-26 15:41:52 java常见问答 8845

关于b树和b+树你了解多少呢?你知道b树和b+树两者之间的区别吗?b树的优点是什么?b+树的优点又是什么?下面一起来详细的了解一下。

一、b树与b+树的区别

最开始,我们要讲的就是b树与b+树的区别,注意,b树与b+树的区别这个问题也是在各大面试场景当中经常会出现的面试题。

1、B+树当中查找,不管查找是不是成功的,每一次的查找,都是一条从根节点到叶节点的路径

2、B树当中,叶节点包含的关键字和其他节点包含的关键字是不重复的。

B+树的索引项只包含对应子树的最大关键字和指向该子树的指针,不含有这个关键字对应记录的存储地址

3、B树当中,每个节点(非根节点)关键字个数的范围为[m/2(向上取整)-1,m-1](根节点为[1,m-1]),并且具有n个关键字的节点包含(n+1)棵子树

B+树当中,每个节点(非根节点)关键字个数的范围为[m/2(向上取整),m](根节点为[1,m]),具有n个关键字的节点包含(n)棵子树

4、B树每个节点都存储数据,所有节点组成这棵树。

B+树只有叶子节点存储数据(B+数中有两个头指针:一个指向根节点,另一个指向关键字最小的叶节点),叶子节点包含了这棵树的所有数据,所有的叶子结点使用链表相连,便于区间查找和遍历,所有非叶节点起到索引作用

那么b树和b+树分别都有什么样的优点呢?

二、b树的优点

B树的每一个节点都包含key和value。

所以,经常访问的元素可能离根节点更近,所以访问也是更加的迅速

三、b+树的优点

1、b+树的中间节点不保存数据,可以容纳更多的节点元素

2、所有的叶子结点使用链表相连,有助于区间查找和遍历

B树的话,就需要进行每一层的递归遍历

相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好

除此之外,b树和b+树两者的共同优点又是怎样的呢?

四、b树和b+树的共同优点

考虑到了IO的影响,它对于内存来说是非常的慢的。

数据库索引是存储在磁盘上的,在数据量大的时候,就不可以将整个索引全部加载到内存,只可以说一项一项的加载每一个磁盘页(对应索引树的节点)。

所以的话,要减少IO次数,对于树来讲的话,IO次数就是树的高度,而“矮胖”就是b树的特征之一,m的大小取决于磁盘页的大小。

关于b树与b+树之间的区别以及b树与b+树的优点你们都弄清楚了吗?你还想了解更多关于b树与b+树的相关知识吗?请继续来奇Q工具网的常见问题栏目了解吧。

推荐阅读:

将二叉搜索树转换成双向链表(实现及思路)

红黑树删除节点最坏时间复杂度怎么删?红黑树结构教程