漫画:什么是B-树?

简介: 下面来具体介绍一下B-树(Balance Tree),一个m阶的B树具有如下几个特征。

640.jpg

640.jpgimage.gif

640.jpg

640.jpg

image.gif

————————————

640.jpg

image.gif640.jpg640.jpg

640.jpg

image.gif640.jpg

640.jpg

image.gif640.jpg

640.jpg

640.jpg

640.jpgimage.gif

640.jpg

image.gif640.jpg

640.jpg

640.jpg

image.gif

640.jpg

640.jpg

image.gif

640.jpg

image.gif640.jpg

640.jpg

image.gif640.jpg

640.jpg

————————————

640.jpg

640.jpg

image.gif

二叉查找树的结构:

640.jpg

第1次磁盘IO:

640.jpg

第2次磁盘IO:

640.jpg

第3次磁盘IO:

640.jpg


第4次磁盘IO:

640.jpg

640.jpg

image.gif

640.jpg

image.gif640.jpg

640.jpg

image.gif

image.gif

下面来具体介绍一下B-树(Balance Tree),一个m阶的B树具有如下几个特征:

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

image.gif640.jpg

image.gif640.jpg

640.jpg

640.jpg

image.gif

640.jpg

image.gif

640.jpg

image.gif

640.jpg

第1次磁盘IO:

640.jpg


在内存中定位(和9比较):

640.jpg

第2次磁盘IO:

640.jpg

在内存中定位(和2,6比较):

640.jpg

第3次磁盘IO:

640.jpg

在内存中定位(和3,5比较):

image.gif640.jpg640.jpg

640.jpg

image.gif640.jpg

640.jpg

image.gif640.jpg

自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间。

640.jpg

节点3,5已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点9是单元素节点,可以升级为两元素节点。于是拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个孩子。

640.jpg

640.jpgimage.gif

640.jpg

image.gif640.jpg

自顶向下查找元素11的节点位置。

640.jpg

删除11后,节点12只有一个孩子,不符合B树规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。(这个过程称为左旋)

640.jpg

image.gif640.jpg

image.gif640.jpg

640.jpg

image.gif640.jpg

640.jpg

image.gif

相关文章
|
6月前
|
存储 算法 关系型数据库
【面试普通人VS高手系列】b树和b+树的理解
【面试普通人VS高手系列】b树和b+树的理解
|
存储 关系型数据库 MySQL
浅浅谈一谈B树和B+树
浅浅谈一谈B树和B+树
2021年圣诞节送自己一颗树吧
2021年圣诞节送自己一颗树吧
2021年圣诞节送自己一颗树吧
|
前端开发
前端知识案例-树的广度优先遍历
前端知识案例-树的广度优先遍历
67 0
前端知识案例-树的广度优先遍历
|
存储 算法
漫画:什么是 “哈夫曼树” ?
哈夫曼树是由麻省理工学院的哈夫曼博士于1952年发明,这到底是一颗什么样的树呢? 刚才我们学习了树的带权路径长度(WPL),而哈夫曼树(Huffman Tree)是在叶子结点和权重确定的情况下,带权路径长度最小的二叉树,也被称为最优二叉树。 举个例子,给定权重分别为1,3,4,6,8的叶子结点,我们应当构建怎样的二叉树,才能保证其带权路径长度最小? 原则上,我们应该让权重小的叶子结点远离树根,权重大的叶子结点靠近树根。
327 0
漫画:什么是 “哈夫曼树” ?
|
机器学习/深度学习 存储 算法
刷穿剑指offer-Day22-树I 树的基础知识讲解!
刷穿剑指offer-Day22-树I 树的基础知识讲解!
140 0
|
存储 数据库 索引
漫画:什么是B+树?
这一次我们来介绍B+树。
140 0
漫画:什么是B+树?
|
存储 SQL 缓存
拜托,别再问我什么是 B+ 树了
拜托,别再问我什么是 B+ 树了
漫画:什么是AVL树?(修订版)
而在AVL树当中,我们通过“平衡因子”来判断一颗二叉树是否符合高度平衡。 到底什么是AVL树的平衡因子呢? 对于AVL树的每一个结点,平衡因子是它的左子树高度和右子树高度的差值。只有当二叉树所有结点的平衡因子都是-1, 0, 1这三个值的时候,这颗二叉树才是一颗合格的AVL树。
170 0
漫画:什么是AVL树?(修订版)
|
索引
漫画:什么是 “跳表” ?
如何进行二分查找呢? 首先根据数组下标,定位到数组的中间元素:由于要查找的元素20,大于中间元素12,再次定位到数组右半部分的中间元素:这一次定位到的元素正好是20,查找成功。
219 0
漫画:什么是 “跳表” ?