每周学点大数据 | No.26外存数据结构——B 树

No.26期

外存数据结构——B 树

小可:看来在磁盘上二叉搜索树对新来的数据插入树中支持得不好,那么究竟怎么解决这个问题呢?

Mr. 王:有一个非常经典的解决方案,叫作B 树。

小可:B 树?这个B 树和二叉搜索树有什么区别呢?

Mr. 王:顾名思义,二叉搜索树是二叉的,这个B 树就是B 叉的。BFS 块自然对应于每个节点出度为Q(B) 的一棵树。而且在每一个磁盘块中,不放置来自树的多层的数据项,只放一层中的数据项。这样做的一大好处是,更新都可以通过变化节点的度来实现,此时我们进行树的平衡操作时,不再依赖旋转,而是利用节点的分裂和合并。

小可:太抽象了,这样说还是不太懂。

Mr. 王:好,我们来看一个例子。

这就是一棵B 树。可以注意到,B 树上的每一个节点都有k 个值和k+1 个指针。每一个值两侧的指针,分别表示小于它和大于它的子树。比如13 左侧的指针指向小于13 的子树,13和17 之间的指针指向键值在13 和17 之间的子树,依此类推。

举一个查找的例子吧。

当我们要查找键值17 的时候,首先会和树根进行比较,17>13,所以要继续访问右子树,将其右子树的这个磁盘块读入内存进行处理,在右边的子树中发现17<23,所以在23 的左子树中,再将这一块读入内存中,然后在它的左子树的根节点中找到了键值17。

小可:这样看来,B 树的查找效率很高啊。

Mr. 王:不过这里我们要研究一下,满足什么样性质的B 树才能有这样高的查找效率。这里提出一个概念叫作(a,b) 树。

小可:这个(a,b) 分别表示什么呢?

Mr. 王:a,b 分别表示键值数量的上界和下界。

如果T 是一棵(a,b) 树(a ≥ 2 且b ≥ 2a-1),那么它应该满足下面三个条件:

— 所有的叶子在同一层上并且包括a 到b 个元素。

— 除了根节点,所有的节点的度在a 到b 之间。

— 根节点的度在2 到b 之间。

这里先以(2,4) 树为例。这样的树,在空间上是线性的,即O(N/B)。

小可:这是为什么呢?

Mr. 王:首先,我们要存储的数据项有N 个,将它们都存到叶子节点中。而每个节点的度均在(a,b) 之间,即使在最坏的情况下,每个节点只有两个出度,此时内部节点的数量也是小于叶子节点的。更何况多数节点是在a,b 之间的,内部节点数小于叶子节点数,说明它是线性空间的。

当所有节点的出度都是a 时,树的高度h 刚好是O(logaN),而节点的度普遍大于a,所以logaN 是树高度的上界。同时我们选取a,b 与B 同阶,即a,b=Q(B),这样每个节点或者说每个叶子节点都能恰好装在一个磁盘块中。进行查找的时间复杂度就是O(logBN)。

小可:这是因为B 与a 同阶吧?

Mr. 王:是的,我们进行了替换,使其与我们使用的参数相关联。

小可:到现在为止,我们研究的都是关于B 树的性质和对建好的B 树的使用,那么一棵B 树是怎么建立起来的呢?

Mr. 王:好,接下来我们就谈谈B 树的插入和删除。首先看插入,这是建立B 树和新增数据项时维护B 树的过程。

当某个节点容纳的数据项没有超过其限制b 时,这种插入就很朴素了,我们讨论的关键是当节点v 上面有b+1 个元素时,对v 如何处理。

此时我们要拆分节点v,即创建节点v’和v”,让它们分别有

个元素。根据前面的约定,可以保证

,但此时,消除了v 却产生了两个新的节点,所以我们要把元素或指针插入parent(v)。

这里还涉及一个问题,如果在拆分的过程中其父亲节点也填满了,那么还要再去拆分它的父亲节点;如果父亲节点的父亲节点也填满了,那么还要去拆分它的父亲节点的父亲节点。

小可:可是这一路拆分上去,恰好根节点也填满了,拆到了根节点怎么办?

Mr. 王:那就把根节点也拆了,使B 树升高一层就可以了啊。现在想想,一次拆分会涉及多少个节点?

小可:自底向上的拆分和自顶向下的搜索应该是一致的,也是从树叶到达树根,最多再在树根上面加一层,所以都是O(logaN)。

Mr. 王:很好,接下来我们讨论(a,b) 树的删除操作。在正常情况下,我们将需要删除的元素从树中剔除就可以了。那么什么情况下会出现问题呢?

小可:我觉得和插入是同理的,当某个节点出现a-1 个儿子节点时,就不行了。

Mr. 王:所以当v 有a-1 个元素/ 儿子节点时,将v 和兄弟节点v’ 合并,将v’的儿子节点移到v’,再从v 的父亲节点中删除相应的元素和指针。一旦有需要,根节点被删除了也是有可能的,此时B 树的高度会降低一层。

小可:我考虑到这样一种情况,如果合并之后又发现节点中的数据项数目大于b 了,是不是还要拆分啊?

Mr. 王:没错,如果真的出现这种情况,还要按照插入的形式拆分v,最终使得整棵树满足(a,b)树的性质。同样,这个过程也是要递归进行的,(a,b) 树也是涉及O(logaN) 个节点。

接下来我们来总结一下B 树的性质。

B 树:(a,b 树,其中a,b=Q(B)。它满足O(N/B) 空间、O(logB N) 查询、O(logB N) 更新。另外,元素都在叶子节点中的B 树有时被称为B+ 树。

建立一棵B 树需要

次I/O。这个复杂度包括排列元素、创建叶子节点,以及从底向上一层层建树。可以看出,B 树是一种性质非常好的数据结构,其广为做磁盘算法的计算机科学家所热爱。有一位著名的计算机科学家,更是在他的主页中写道:我喜欢B 树。

小可:有空我是不是也应该试着去实现一棵B 树呢?

Mr. 王:如果是要在开发软件系统中使用B 树,不妨参考一些开源关系数据库的源代码,那里面一定有优质的B 树的实现。

内容来源:灯塔大数据

本文分享自微信公众号 - 灯塔大数据(DTbigdata)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2017-02-17

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏灯塔大数据

每周学点大数据 | No.25二叉搜索树回顾(二)

No.25期 二叉搜索树回顾(二) Mr. 王:既然提到了有序的状态,那么我们就来谈谈有根树的遍历问题。 小可:我知道,遍历就是访问一个数据集合中的所...

35960
来自专栏aCloudDeveloper

探秘堆结构

一、概述   此处所说的堆为数据结构中的堆,而非内存分区中的堆。堆通常可以被看做是树结构,满足两个性质:1)堆中任意节点的值总是不大于(不小于)其子节点的值;2...

261100
来自专栏SeanCheney的专栏

《大话数据结构》总结第一章 绪论第二章 算法第三章 线性表第四章 栈和队列第五章 字符串第六章 树第七章 图第八章 查找第九章 排序

第一章 绪论 什么是数据结构? 数据结构的定义:数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 第二章 算法 算法的特性:有穷性、确定性、可行性、输...

39350
来自专栏JavaEdge

二分查找复杂度分析

45950
来自专栏Petrichor的专栏

leetcode: 78. Subsets

12210
来自专栏彭湖湾的编程世界

【算法】赫夫曼树(Huffman)的构建和应用(编码、译码)

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

77150
来自专栏java一日一条

Calendar 详解

究竟什么是一个 Calendar 呢?中文的翻译就是日历,那我们立刻可以想到我们生活中有阳(公)历、阴(农)历之分。它们的区别在哪呢?

9710
来自专栏机器之心

资源 | 从算法到数据结构,百道面试问题实现答案集合

选自GitHub 作者:Sherali Obidov 机器之心编译 参与:李亚洲、微胖、蒋思源 该资源是算法、数据结构以及面试问题解决方案的集合,里面的 rep...

29860
来自专栏Golang语言社区

完全二叉树判断,简单而复杂

今天有个人问我如何判断一棵树是完全二叉树。我一下子想不出怎么解决这个问题,按照定义, 严蔚敏那本教材上的说法:一个深度为k,节点个数为 2^k - 1 的二叉树...

40230
来自专栏Golang语言社区

解决连通性问题的四种算法

连通性问题 问题概述 先来看一张图: ? 在这个彼此连接和断开的点网络中,我们可以找到一条 p 点到 q 点的路径。在计算机网络中判断两台主机是否连通、在社交网...

76390

扫码关注云+社区

领取腾讯云代金券