b树和b+树的区别
基本知识
2-3树
2-3-4树
B树存储引擎
(小知识点)
Innodb使用的是B+树,他存在有一个主键索引和辅助索引两种索引,主键索引是在生成主键时就有的索引,他的叶子节点中存放的就是数据行,所以又称之为聚集索引。
而另一类索引,辅助索引,就是我们人为新建的索引,他的叶子节点中存放的是主键,当我们通过辅助索引查找到主键之后,再通过查找的主键去查找主键索引,
(数据结构)
相比哈希存储引擎,B树存储引擎不仅支持随机读取,还支持范围扫描。关系数据库中通过索引访问数据,在Mysql InnoDB中,有一个称为聚集索引的特殊索引,行的数据存于其中,组织成B+树(B树的一种)数据结构。
如图所示,MySQL InnoDB按照页面(Page)来组织数据,每个页面对应B+树的一个节点。其中,叶子节点保存每行的完整数据,非叶子节点保存索引信息。数据在每个节点中有序存储,数据库查询时需要从根节点开始二分查找直到叶子节点,每次读取一个节点,如果对应的页面不在内存中,需要从磁盘中读取并缓存起来。B+树的根节点是常驻内存的,因此,B+树一次检索最多需要h-1次磁盘IO,复杂度为O(h)=O(logdN)(N为元素个数,d为每个节点的出度,h为B+树高度)。修改操作首先需要记录提交日志,接着修改内存中的B+树。如果内存中的被修改过的页面超过一定的比率,后台线程会将这些页面刷到磁盘中持久化。
B-树
简介
B树也是一种用于查找的平衡树,但是它不是二叉树。
B树的定义:B树(B-tree)是一种树状数据结构,能够用来存储排序后的数据。这种数据结构能够让查找数据、循序存取、插入数据及删除的动作,都在对数时间内完成。B树,概括来说是一个一般化的二叉查找树,可以拥有多于2个子节点。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。这种数据结构常被应用在数据库和文件系统的实作上。
1 一颗m阶树中每个节点至多有m棵子树(即至多含有m-1个关键字);
2 若根节点不是叶子节点,则至少有2棵子树;
3 除根节点之外的所有非终端节点至少有[ m/2 ] ( 向上取整 )棵子树,即([ m/2 ]-1个关键字)
4 每个节点中的信息结构为(A0,K1,A1,K2......Kn,An),其中n表示关键字个数,Ki为关键字,Ai为指针;且Ai-1所指子树中所有结点的关键字均小于Ki,An所指子树中所有结点的关键字均大于Kn;
5 所有的叶子节点都出现在同一层次上,且不带任何信息,也是为了保持算法的一致性。
查找
插入
没有破坏结构
结构破坏
删除
终端
1 直接删除
2 兄弟够借
3兄弟不够借
非终端
(1)
(2)
(3)
B+树
B+树是B-树的变体,也是一种多路搜索树:
1.其定义基本与B-树同,除了:
2.非叶子结点的子树指针与关键字个数相同;
3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树(B-树是开区间);
4.为所有叶子结点增加一个链指针;
5.所有关键字都在叶子结点出现;
B树和二叉查找树的性能对比?
B树包括B+树的设计思想都是尽可能的降低树的高度,以此降低磁盘IO的次数,因为一个索引节点就表示一个磁盘页,页的换入换出次数越多,表示磁盘IO次数越多,越低效。
B树算法减少定位数据所在的节点时所经历的磁盘IO次数,从而加快存取速度。
假设一个节点可以容纳100个值,那么3层的B树可以容纳100万个数据。(根节点100值,第二层可以存储99个节点(k-1),也就是99*100 个值,第三层可以存储
(99*100-1)*100)结果是近似100万个数据。而如果使用二叉查找树,则需要将近20层,也就是进行20次磁盘IO,性能差距如此之大。
如mongoDB数据库使用,单次查询平均快于Mysql(但侧面来看Mysql至少平均查询耗时差不多)。
为什么数据库索引不用红黑树而用B+树?
红黑树当插入删除元素的时候会进行频繁的变色与旋转(左旋,右旋),来保证红黑树的性质,浪费时间。
但是当数据量较小,数据完全可以放入内存中,不需要进行磁盘IO,这时候,红黑树时间复杂度比B+树低。
比如TreeSet TreeMap 和HashMap (jdk1.8)就是使用红黑树作为底层数据结构。
B+树和B树相比,主要的不同点
所有指向文件的关键字及其指针都在叶子节点中,不像B树,有的指向文件的关键字是在内部节点中。换句话说,B+树中,内部节点仅仅起到索引的作用,在搜索过程中,如果查询和内部节点的关键字一致,那么搜索过程不停止,而是继续向下搜索这个分支。
优势
根据B+树的结构,我们可以发现B+树相比于B树,在文件系统,数据库系统当中,更有优势,原因如下:
B+树的磁盘读写代价更低
B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。
B+树的查询效率更加稳定
由于内部结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。
B+树更有利于对数据库的扫描
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题,而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库中频繁使用的range query,B+树有着更高的性能。
从一道索引数据结构面试题看B树、B+树
题目1: Mysql数据库用过吧?l里面的索引是基于什么数据结构。
答:主要是基于Hash表和B+树
题目2: 很好请你说一下B+树的实现细节是什么样的?B-树和B+树有什么区别?联合索引在B+树中如何存储?
答: 首先,数据库使用树型结构来增加查询效率,并保持有序。那么,为什么不使用二叉树来实现数据结构呢,二叉树算法时间复杂度是lg(N),查询速度和比较次数都是较小的。
实际上,查询索引操作最耗资源的不在内存中,而是磁盘IO。索引是存在磁盘上的,当数据量比较大的时候,索引的大小可能达到几个G。那么,我们利用索引进行查询的时候,不可能把索引直接加载到内存中,只能一次读取一个磁盘页,一个磁盘页对应着一个节点,一次读取操作需要一次磁盘io。
在二叉树查询时,最坏的情况下查找的次数是树的高度,即io次数为树的高度。B-树就是比二叉树“矮胖”的树。
B树的特征如下:
1. 根节点至少有两个子女
2. 每个中间节点包含k-1个元素和k个孩子,其中 m/2 <= k <= m
3. 每个叶子节点包含k-1个元素,其中 m/2 <= k <= m
4. 所有叶子节点位于同一层
5. 节点中的元素从小到大排列,正好是孩子节点的值域。(就是孩子节点的元素都比父节点中元素的最小值大,比父节点元素的最大值小)
B-树查询的次数并不比二叉树的次数小,但是相比起磁盘io速度,内存中比较的耗时就不足为提了。所以只要树的高度足够低,io次数少,就可以提升查找性能。而每个节点中有多个元素,都只在内存中操作。
而B+树是基于B-树的,增加了如下规则:
1. 有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
2. 所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
3. 所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。
所以,B+树对比B-树有如下好处:
io次数少:B+树中间节点只存索引,不存在实际的数据,所以可以存储更多的数据。索引树更加的矮胖,io次数更少。
性能稳定:B+树数据只存在于叶子节点,查询性能稳定
范围查询简单:b+树不需要中序遍历,遍历链表即可。
参考链接
https://blog.csdn.net/tongdanping/article/details/79878302
深入理解MySQL索引原理和实现——为什么索引可以加速查询?
https://blog.csdn.net/u012954706/article/details/81241049
mysql索引的新手入门详解
MySQL实战45讲 ---深入浅出索引
https://blog.csdn.net/zhangshk_/article/details/83013482
B树,B+树,红黑树 数据库常见面试题