首页 > 全部内容 > 编程书籍 > 漫画算法:什么是B树?
2017
08-17

漫画算法:什么是B树?

本文提到的「B-树」,就是「B树」,都是 B-tree 的翻译,里面不是减号-,是连接符-。因为有人把 B-tree 翻成 「B-树」,让人以为「B树」和「B-树」是两种树,实际上两者就是同一种树。

漫画算法:什么是B树? - 第1张  | Hello word !

漫画算法:什么是B树? - 第2张  | Hello word !

漫画算法:什么是B树? - 第3张  | Hello word !

漫画算法:什么是B树? - 第4张  | Hello word !

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

漫画算法:什么是B树? - 第5张  | Hello word !

漫画算法:什么是B树? - 第6张  | Hello word !

漫画算法:什么是B树? - 第7张  | Hello word !

漫画算法:什么是B树? - 第8张  | Hello word !

漫画算法:什么是B树? - 第9张  | Hello word !

漫画算法:什么是B树? - 第10张  | Hello word !

漫画算法:什么是B树? - 第11张  | Hello word !

漫画算法:什么是B树? - 第12张  | Hello word !

漫画算法:什么是B树? - 第13张  | Hello word !

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

漫画算法:什么是B树? - 第14张  | Hello word !

漫画算法:什么是B树? - 第15张  | Hello word !

漫画算法:什么是B树? - 第16张  | Hello word !

漫画算法:什么是B树? - 第17张  | Hello word !

漫画算法:什么是B树? - 第18张  | Hello word !

漫画算法:什么是B树? - 第19张  | Hello word !

漫画算法:什么是B树? - 第20张  | Hello word !

漫画算法:什么是B树? - 第21张  | Hello word !

漫画算法:什么是B树? - 第22张  | Hello word !

漫画算法:什么是B树? - 第23张  | Hello word !

漫画算法:什么是B树? - 第24张  | Hello word !

漫画算法:什么是B树? - 第25张  | Hello word !

漫画算法:什么是B树? - 第26张  | Hello word !

漫画算法:什么是B树? - 第27张  | Hello word !

二叉查找树的结构:

漫画算法:什么是B树? - 第28张  | Hello word !

第1次磁盘IO:

漫画算法:什么是B树? - 第29张  | Hello word !

第2次磁盘IO:

漫画算法:什么是B树? - 第30张  | Hello word !

第3次磁盘IO:

漫画算法:什么是B树? - 第31张  | Hello word !

第4次磁盘IO:

漫画算法:什么是B树? - 第32张  | Hello word !

漫画算法:什么是B树? - 第33张  | Hello word !

漫画算法:什么是B树? - 第34张  | Hello word !

漫画算法:什么是B树? - 第35张  | Hello word !

漫画算法:什么是B树? - 第36张  | Hello word !

下面来具体介绍一下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个孩子包含的元素的值域分划。

漫画算法:什么是B树? - 第37张  | Hello word !

漫画算法:什么是B树? - 第38张  | Hello word !

漫画算法:什么是B树? - 第39张  | Hello word !

漫画算法:什么是B树? - 第40张  | Hello word !

漫画算法:什么是B树? - 第41张  | Hello word !

漫画算法:什么是B树? - 第42张  | Hello word !

漫画算法:什么是B树? - 第43张  | Hello word !

第1次磁盘IO:

漫画算法:什么是B树? - 第44张  | Hello word !

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

漫画算法:什么是B树? - 第45张  | Hello word !

第2次磁盘IO:

漫画算法:什么是B树? - 第46张  | Hello word !

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

漫画算法:什么是B树? - 第47张  | Hello word !

第3次磁盘IO:

漫画算法:什么是B树? - 第48张  | Hello word !

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

漫画算法:什么是B树? - 第49张  | Hello word !

漫画算法:什么是B树? - 第50张  | Hello word !

漫画算法:什么是B树? - 第51张  | Hello word !

漫画算法:什么是B树? - 第52张  | Hello word !

漫画算法:什么是B树? - 第53张  | Hello word !

漫画算法:什么是B树? - 第54张  | Hello word !

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

漫画算法:什么是B树? - 第55张  | Hello word !

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

漫画算法:什么是B树? - 第56张  | Hello word !

漫画算法:什么是B树? - 第57张  | Hello word !

漫画算法:什么是B树? - 第58张  | Hello word !

漫画算法:什么是B树? - 第59张  | Hello word !

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

漫画算法:什么是B树? - 第60张  | Hello word !

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

漫画算法:什么是B树? - 第61张  | Hello word !

漫画算法:什么是B树? - 第62张  | Hello word !

漫画算法:什么是B树? - 第63张  | Hello word !

漫画算法:什么是B树? - 第64张  | Hello word !

最后编辑:
作者:Null
这个作者貌似有点懒,什么都没有留下。