B树和B+树

大标 2022年3月9日18:44:45
评论
60
摘要

B树(balance tree)和B+树,可以认为是N叉多路平衡排序查找树。  这里的N是相对于二叉树中的二来说的,B树和B+树的典型应用场景是数据库引擎的索引结构。但是从理论上讲,二叉树查找速度和比较次数都是最小的,为什么不用二叉树呢?  因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(

B树(balance tree)和B+树,可以认为是N叉多路平衡排序查找树。

  这里的N是相对于二叉树中的二来说的,B树和B+树的典型应用场景是数据库引擎的索引结构。但是从理论上讲,二叉树查找速度和比较次数都是最小的,为什么不用二叉树呢?

  因为我们要考虑磁盘IO的影响,它相对于内存来说是很慢的。数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,它的每个节点最多包含N个孩子,N称为b树的阶,N的大小取决于磁盘页的大小。

  

一个N阶的B树具有如下几个特征(括号内我给出了通俗的翻译):

  1. 定义任意非叶子结点最多只有N个儿子,且N>2(翻译 :一个节点最多分N个叉,最少2个叉);
  2. 除根结点以外的非叶子结点的儿子数为[N/2, N],向上取整 (翻译 :进一步限定了非根节点的分叉数目的最小值为N/2,为了防止形成二叉树);
  3. 非叶子结点的关键字个数=儿子数-1 (翻译 :限定子节点中的数据量,数量为分叉数-1);
  4. 所有叶子结点位于同一层(翻译:废话);
  5. k个关键字把节点拆成k+1段,分别指向k+1个儿子,满足查找树的大小关系 (翻译:同一级节点元素有序排列且左子<父<右子)。

简化总结:

  1.   N阶B树根节点最少2个儿子节点;
  2.   非子节点儿子节点数目最少为N/2,最多为N;
  3.   儿子节点的key数量最多为N-1;
  4.   同一级节点元素有序排列且左子<父<右子

  

 如图是一个3阶段B树,顺便说明一下数字5的查询过程:

  

 

 

  第一次磁盘IO,把9所在节点读到内存,把目标数5和9比较,小,找小于9对应的左节点; 

      

 

 

  第二次磁盘IO,还是读节点到内存,在内存中把5依次和2、6比较,定位到2、6中间区域对应的节点;

  第三次侧排IO,读取key3、5所在的节点,并成功查询到5

  b树的插入删除元素操作: 
  比如我们要在下图中插入元素4: 
      
1,首先自顶向下查询找到4应该在的位置,即3、5之间; 
2,但是3阶b树的节点最多只能有2个元素,所以把3、4、5里面的中间元素4上移(中间元素上移是插入操作的关键); 
3,上一层节点加入4之后也超载了,继续中间元素上移的操作,现在根节点变成了4、9; 
4,还要满足查找树的性质,所以对元素进行调整以满足大小关系,始终维持多路平衡也是b树的优势,最后变成这样: 

再比如我们要删除元素11: 
1,自顶向下查询到11,删掉它; 
2,然后不满足b树的条件了,因为元素12所在的节点只有一个孩子了,所以我们要“左旋”,元素12下来,元素13上去: 
 
这时如果再删除15呢?很简单,当元素个数太少以至于不能再旋转时,12直接上去就行了。

 

 B+树

  b+树,是b树的一种变体,查询性能更好。m阶的b+树的特征:

  1. 有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点。
  2. 所有的叶子结点中包含了全部关键字的信息,及指向含这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  3. 所有的非叶子结点可以看成是索引部分,结点中仅含其子树中的最大(或最小)关键字。
  4. 通常在b+树上有两个头指针,一个指向根结点,一个指向关键字最小的叶子结点。
  5. 同一个数字会在不同节点中重复出现,根节点的最大元素就是b+树的最大元素。

 

b+树相比于b树的查询优势:

  1. b+树的中间节点不保存数据,所以磁盘页能容纳更多节点元素,更“矮胖”;
  2. b+树查询必须查找到叶子节点,b树只要匹配到即可不用管元素位置,因此b+树查找更稳定(并不慢);
  3. 对于范围查找来说,b+树只需遍历叶子节点链表即可,b树却需要重复地中序遍历,如下两图:

     

     

 

 

参考连接
  https://www.cnblogs.com/xueqiuqiu/articles/8779029.html

  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
大标
  • 本文由 发表于 2022年3月9日18:44:45
  • 转载请务必保留本文链接:https://www.tanhuibiao.com/script/qita/1292.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: