看图轻松理解数据结构与算法系列(B树)

作者:超人汪小建(seaboat)

出处:https://blog.csdn.net/wangyangzhizhou/column/info/25184/2


B树

B树即平衡查找树,一般理解为平衡多路查找树,也称为B-树、B_树。是一种自平衡树状数据结构,能对存储的数据进行O(log n)的时间复杂度进行查找、插入和删除。B树一般较多用在存储系统上,比如数据库或文件系统。

B树特点

  • B树可以定义一个m值作为预定范围,即m路(阶)B树。
  • 每个节点最多有m个孩子。
  • 每个节点至少有ceil(m/2)个孩子,除了根节点和叶子节点外。
  • 对于根节点,子树个数范围为[2,m],节点内值的个数范围为[1,m-1]。
  • 对于非根节点,节点内的值个数范围为[ceil(m/2)-1,m-1]。
  • 根节点(非叶子节点)至少有两个孩子。
  • 一个有k个孩子的非叶子节点包含k-1个值。
  • 所有叶子节点在同一层。
  • 节点内的值按照从小到大排列。
  • 父节点的若干值作为分离值分成多个子树,左子树小于对应分离值,对应分离值小于右子树。

以下是一个四阶B树,

image

插入

假设现在构建一棵四阶B树,开始插入“A”,直接作为根节点,

image

插入“B”,大于“A”,放右边,

image

插入“C”,按顺序排到最后,

image

继续插入“D”,直接添加的结果如下图,此时超过了节点可以存放容量,对于四阶B树每个节点最多存放3个值,此时需要执行分裂操作,

image

分裂操作为,先选取待分裂节点的中值,这里为“B”,然后将中值“B”放到父节点中,因为这里还没有父节点,那么直接创建一个新的父节点存放“B”,而原来小于“B”的那些值作为左子树,原来大于“B”的那些值作为右子树。

image

继续插入“E”,”E”大于“B”,往右子节点,

image

分别于“C”和“D”比较,大于它们,放到最右边,

image

插入“F”,“F”大于“B”,往右子树,

image

“F”分别与“C””D”“E”比较,大于它们,放到最右边,此时触发分裂操作,

image

选取待分裂节点的中值“D”,然后将中值“D”放到父节点中,父节点中的“B”小于“D”,于是放到“B”右边,而原来小于“D”的那些值作为左子树,原来大于“D”的那些值作为右子树。

image

继续插入“M”,结果为,

image

插入“L’,大于“B”“D”,往右子树,

image

“L”大于“E”“F”小于“M”,于是放到第三个位置,此时触发分裂操作,

image

选取待分裂节点的中值“F”,然后将中值“F”放到父节点中,父节点中的“B”“D”都小于“F”,于是放到最右边,而原来小于“F”的那些值作为左子树,原来大于“F”的那些值作为右子树。

image

插入“K”,结果为,

image

插入“J”,大于“B”“D”“F”,往右子树,

image

“J”小于“K”“L”“M”,于是放到第一个位置,此时触发分裂操作,

image

选取待分裂节点的中值“K”,然后将中值“K”放到父节点中,父节点中的“B”“D”“F”都小于“K”,于是放到最右边,而原来小于“K”的那些值作为左子树,原来大于“K”的那些值作为右子树。此时父节点也触发分裂操作,

image

选取待分裂节点的中值“D”,然后将中值“D”放到父节点中,由于还没有父节点,那么直接创建一个新的父节点存放“D”,而原来小于“D”的那些值作为左子树,原来大于“D”的那些值作为右子树。

image

插入“I”,大于“D”,往右子树,

image

右子树不是叶子节点,继续往下,这时“I”大于“F”而小于“K”,所以往第二个分支,

image

“I”小于“J”,于是放到左边,

image

类似地,插入“H”,结果如下,

image

插入“G”,往左子树,

image

往中间分支,

image

触发分裂操作,

image

选取待分裂节点的中值“H”,然后将中值“H”放到父节点中,”H”大于父节点中的“F”而小于“K”,于是放到中间,而原来小于“H”的那些值作为左子树,原来大于“H”的那些值作为右子树。

image

综上所述,插入操作的核心是分裂操作。无需分裂的情况比较简单,直接插入即可;如果插入后超过节点容量,这个容量可预先自定义,则需要进行分裂操作,需要注意的是分裂可能引起父节点需要继续分裂。

查找

对B树进行查找就比较简单,查找过程有点类似二叉搜索树,从根节点开始查找,根据比较数值找到对应的分支,继续往子树上查找。

比如查找“I”,”I”大于“D”,往右子树,

image

“I”分别与节点内值比较,大于“F”“H”而小于“K”,往第三个分支,

image

逐一比较节点内的值,找到“I”。

image

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » 看图轻松理解数据结构与算法系列(B树)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏