专栏首页CSDN搜“看,未来”浅谈多路查找树(B树)

浅谈多路查找树(B树)

1、序言

曾今我不知道多叉树有上面用,所以对于多叉树并没有过多的关注,或者说,基本没关注。 直到我了解到了多路查找树(B树),我知道,是我浅薄了。

先不说那些高深莫测的内容,我们就通俗的聊聊。

我们现在常说大数据大数据,就算没说过也听过不少了。但是我们的系统的内存就那么大,而外部硬盘却可以达到成千上百个G。

我们之前聊的数据结构,都是基于内存的,因此考虑的是内存中的运算时间复杂度。但是如果我们操作的数据集非常大,大到内存已经无法处理了,这也是很正常的现象,比方说某个程序要从文件系统中取一个文件出来,这个时间复杂度就会发生变化了。

试想一下,要在一个拥有几十万个文件的文件系统中查找一个文件,你所设计的算法需要读取磁盘上千次还是几十次,这是有本质上的差异的,后者可能是几秒,前者可能就要几分钟了,你能忍?找个文件都要等几分钟!!!

2、2-3树

这是一个简单的多路查找树,学新东西嘛,自然从最简单的开始。什么是多路查找树?和二叉树做个比较可能会比较直观:二叉树,你可以叫它二路查找树。明白了吧。

那么2-3树是一颗怎样的树?长这样: 1、其中每一个节点都有两个孩子(称为2节点)或三个孩子(三节点)或者没有。 2、子节点排序参考二叉树 3、一个二节点包含一个元素和两个子节点(或没有子节点),一个三节点包含两个元素和三个子节点(或没有子节点) 4、2-3树中所有的叶子节点都在同一层次上。

2.1、2-3树的插入

这个比较开始复杂了,不过咱就随便聊聊,聊到哪儿算哪儿。

首先,要明白每个新插入的节点都是二节点。

插入情景1: 插入空树,直接插入,完事儿。

插入情景2: 插入到一个二节点的叶子上,这也没什么,就像上面最左叶子节点,在“1"旁边给新节点“3”留个位置就好了。

插入情景3: 插入到一个三节点的叶子上,这就很尴尬了,2-3树的节点极限就是3,比方说上面要插个5进去。 那怎么弄? 先看一下,要插入节点的父节点是个二节点,那就好办了,把那个二节点变成三节点,自然就有地方插入了。怎么变?把“6”提上去啊,图自己画。 如果要插入节点的父节点是个三节点,那就比较尴尬一点。比方说我现在要插个“11”进去。 那怎么弄? 那就一直往上找,找到二节点为止,然后该怎么做上面已经讲了。

还是刚刚最后一种场景,如果往上找,找到根节点都是三节点,那怎么办? 那就意味着当前=层次已经无法满足我们的需要了,从根开始,全拆成二节点吧。

也不要去钻牛角尖了,咱就随便聊聊,要钻牛角尖咱往后去把代码实现写一下。现在知道是这么回事儿就好。

2.2 2-3树的删除

删除其实就是增加的逆过程,如果增加看懂了,删除就很简单。

以下场景针对删除节点为叶子节点: 删除场景1:要删除的节点位于一个三节点上,直接删了。

删除场景2:删除根节点,也是直接删了吧。

删除场景3:删除的节点位于一个二节点上。就像插入节点在三节点上一样的尴尬。不,更尴尬。

删除场景3.1:该节点的父节点为三节点:将父节点拆开下放一个节点。 删除场景3.2:上面场景不存在,但是 该节点的兄弟节点是三节点,将它的兄弟节点拆开,然后做单旋转。

其他的删除场景嘛,日后深入研究的时候再行探讨,过于复杂。

3、B树

B树是一种平衡的多路查找树。 节点最大的孩子的数量的树叫做m阶B数。 所以2-3树就是3阶B树,二叉树就是2阶B树。

B树有如下性质:

  1. 如果根节点不是叶节点,那么B树至少有两叉。
  2. 所有叶子节点都位于同一层次。
  3. 每一个非根的分支结点都有k-1个元素和k个孩子,其中[m/2]<k<m. 21每一个叶子结点n都有k-1个元素,其中[m/2]<k< m.

在B树上的查找过程是一个顺指针查找节点和在节点中查找关键字的交叉过程。

关于B树的插入删除,和2-3树一样,只不过阶数可能会大了些。

4、B树的典型应用

我们的外存,比如硬盘,是将所有的信息分割成相等大小的页面,每次硬盘读写的都是一个或多个完整的页面,对于一个硬盘来说,-页的长度可能是 211到214个字节。

在一个典型的B树应用中,要处理的硬盘数据量很大,因此无法一次全部装入内存。因此我们会对 B树进行调整, 使得B树的阶数 (或结点的元素)与硬盘存储的页面大小相匹配。比如说一棵B树的阶为1001 (即1个结点包含1000个关键字),高度为2,它可以储存超过10亿个关键字,我们只要让根结点持久地保留在内存中,那么在这棵树上,寻找某一个关键字至多需要两次硬盘的读取即可。

B树查找的时间复杂度:O(log n).

下次再深挖的时候我一定带上B+树的!!!

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拥抱STL -树的导览

    树,一种十分基础的数据结构。 本篇将重点讲一些树的基础知识,作为下一篇《走进STL - 红黑树》的支持。

    看、未来
  • 【LeetCode】每日一题(8.2)二叉树展开为链表

    具体做法是,对于当前节点,如果其左子节点不为空,则在其左子树中找到最右边的节点,作为前驱节点,将当前节点的右子节点赋给前驱节点的右子节点(其实就是找左子节点的最...

    看、未来
  • 种树:二叉树、二叉搜索树、AVL树、红黑树、哈夫曼树、B树、树与森林

    树是我们计算机中非常重要的一种数据结构,同时使用树这种数据结构,可以描述现实生活中的很多事物,例如家 谱、单位的组织架构、等等。 树是由n(n>=1)个有限...

    看、未来
  • Linux之HA高可用集群的基础概念总结

    HA(High Availability)高可用集群,其特点为根据实际需求为前端Diretor,后端RS-server,数据库服务器,共享存储等集群节点做一个...

    小小科
  • Zookeeper系列(5) —— Zookeeper 常用的客户端操作命令

    创建节点的命令格式 create [-s] [-e] /path data acl

    求和小熊猫
  • 第15期:索引设计(索引组织方式 B+ 树)

    谈到索引,大家并不陌生。索引本身是一种数据结构,存在的目的主要是为了缩短数据检索的时间,最大程度减少磁盘 IO。

    爱可生开源社区
  • 动图展示,让你彻底理解红黑树!

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    业余草
  • 数据结构:堆(Heap)

    堆就是用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

    sunsky
  • 动图演示:如何彻底理解红黑树?

    简单地理解,二叉树(Binary tree)是每个节点最多只有两个分支(即不存在分支度大于 2 的节点)的树结构。通常分支被称作“左子树”或“右子树”。

    架构师修炼
  • 使用图进行特征提取:最有用的图特征机器学习模型介绍

    从图中提取特征与从正常数据中提取特征完全不同。图中的每个节点都是相互连接的,这是我们不能忽视的重要信息。幸运的是,许多适合于图的特征提取方法已经创建,这些技术...

    deephub

扫码关注云+社区

领取腾讯云代金券