图解B树

栏目: IT技术 · 发布时间: 3年前

内容简介:B树即平衡查找树,一般理解为平衡多路查找树,也称为B-树、B_树。是一种自平衡树状数据结构,能对存储的数据进行O(log n)的时间复杂度进行查找、插入和删除。B树一般较多用在存储系统上,比如数据库或文件系统。以下是一个四阶B树,假设现在要构建一棵四阶B树,我们开始插入“A”,直接作为根节点。

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树,

图解B树
四阶B树

插入操作

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

图解B树

继续插入“B”,因为大于“A”,所以放右边。

图解B树

继续插入“C”,按顺序将其排到最后。

图解B树

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

图解B树

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

图解B树

继续插入“E”,因为"E"大于“B”,所以往右子节点。

图解B树

分别于“C”和“D”比较,因为大于它们,所以放到最右边。

图解B树

继续插入“F”,因为“F”大于“B”,所以往右子树。

图解B树

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

图解B树

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

图解B树

继续插入“M”,结果如下。

图解B树

继续插入“L’,由于大于“B”“D”,所以往右子树。

图解B树

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

图解B树

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

图解B树

继续插入“K”,结果如下。

图解B树

继续插入“J”,由于大于“B”“D”“F”,所以往右子树。

图解B树

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

图解B树

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

图解B树

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

图解B树

继续插入“I”,由于大于“D”,所以往右子树。

图解B树

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

图解B树

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

图解B树

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

图解B树

继续插入“G”,往左子树。

图解B树

然后再往中间分支。

图解B树

接着触发分裂操作。

图解B树

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

图解B树

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

查找操作

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

比如要查找“I”,因为"I"大于“D”,所以往第二个分支。

图解B树

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

图解B树

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

图解B树

作者的 新书《图解数据结构与算法》上市了,全彩印刷,当当现在满100减50,需要的朋友可以关注下,购书好时机。

图解B树


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

UNIX网络编程 卷2

UNIX网络编程 卷2

W.Richard Stevens / 人民邮电出版社 / 2009-11 / 89.00元

《UNIX网络编程 卷2:进程间通信(英文版·第2版)》是一部UNIX网络编程的经典之作。进程间通信(IPC)几乎是所有Unix程序性能的关键,理解IPC也是理解如何开发不同主机间网络应用程序的必要条件。《UNIX网络编程 卷2:进程间通信(英文版·第2版)》从对Posix IPC和System V IPC的内部结构开始讨论,全面深入地介绍了4种IPC形式:消息传递(管道、FIFO、消息队列)、同......一起来看看 《UNIX网络编程 卷2》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换