我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:六合特肖 > 访问局部性 >

多路查找树:2-3树、2-3-4树、BB+R树

归档日期:05-09       文本归类:访问局部性      文章编辑:爱尚语录

  每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。由于它是查找树,所有元素之间存在某种特定的排序关系。

  1、2-3树是这样的一棵多路查找树:其中的每一个结点都具有两个孩子(我们称它为2结点)或三个孩子(我们称它为3结点)。

  2、一个2结点包含一个元素和两个孩子(或没有孩子),且与二叉排序树类似,左子树包含的元素小于该元素,右子树包含的元素大于该元素。不过,与二叉排序树不同的是,这个2结点要么没有孩子,要有就有两个,不能只有一个孩子。

  3、一个3结点包含一小一大两个元素和三个孩子(或没有孩子),一个3结点要么没有孩子,要么具有3个孩子。如果某个3结点有孩子的话,左子树包含小于较小元素的元素,右子树包含大于较大元素的元素,中间子树包含介于两元素之间的元素。

  注意:2-3树复杂的地方在于新结点的插入和已有结点的删除。每个结点可能是2结点也可能是3结点,要保证所有叶子结点在同一层次。

  对于2-3树的插入来说,与二叉排序树相同,插入操作一定是发生在叶子结点上。可与二叉排序树不同的是,2-3树插入一个元素的过程有可能对该树的其余结构造成连锁反应。

  2、插入结点到一个2结点的叶子上,由于其本身就只有一个## 标题 ##元素,所以只需要将其升级为3结点即可。

  3、要往3结点中插入一个新元素,因为3结点本身已经是2-3树的结点最大容量,已经有两个元素,因此就需要将其拆分,且将树中两元素或插入元素的三者中选择其一向上移动一层。这里又分为三种情况:

  结论:如果2-3树的插入的传播效应导致了根结点的拆分,则树的高度就会增加。

  1、所删除元素位于一个3结点的叶子结点上,只需要在该结点处删除该元素即可,不会影响到整棵树的其他结点结构。

  2-3-4树是2-3树的概念扩展,包括了4结点的使用。一个4结点包含小中大三个元素和四个孩子(或没有孩子),一个4结点要么没有孩子,要么具有4个孩子。如果某个4结点右孩子的话,左子树包含小于最小元素的元素;第二个子树包含大于最小元素,小于第二元素的元素;第三字数包含书大于第二元素,小于最大元素的元素;右子树包含大于最大元素的元素。

  B树是一种平衡的多路查找树,2-3树和2-3-4树都是B树的特例。结点最大的孩子数目称为B树的阶,因此2-3树是3阶B树,2-3-4树是4阶B树。

  比方说,我们要查找数字7,首先从外存(比如硬盘中)读取得到根结点3 、5 、8三个元素,发现7不在当中,但在5和8之间,因此就通过A2再读取外存的6 、7结点,查找到所耍的元素。

  至于B树的插入和删除,方式是与2-3树2-3-4树相类似的,只不过阶数可能会很大而已。

  对于树结构来说,我们都可以通过中序遍历来顺序查找树中的元素,这一切都是在内存中进行。

  如果要随机查找,我们就从根结点出发,与B树的查找的方式不同,只不过即使在分支结点找到了待查找的关键字,它也只是用来索引的,不能提供实际记录的访问,还是需要到达包含此关键字的终端结点。

  如果我们是需要从最小关键字进行从小到大的顺序查找,我们就可以从最左侧的叶子结点出发,不经过分支结点,而是延着指向下一叶子的指针就可遍历所有的关键字。

  B/B+树通过对每个节点存储个数的扩展,使得对连续的数据能够进行较快的定位和访问,能够有效减少查找时间,提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中,如:

  根据B+树的结构,我们可以发现B+树相比于B树,在文件系统,数据库系统当中,更有优势,原因如下:

  B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B树更小。如果把所有同一内部结点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说I/O读写次数也就降低了。

  举个例子,假设磁盘中的一个盘块容纳16bytes,而一个关键字2bytes,一个关键字具体信息指针2bytes。一棵9阶B-tree(一个结点最多8个关键字)的内部结点需要2个盘快。而B+ 树内部结点只需要1个盘快。当需要把内部结点读入内存中的时候,B 树就比B+ 树多一次盘块查找时间(在磁盘中就是盘片旋转的时间)。

  由于内部结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

  B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题,而B+树只需要遍历叶子节点就可以解决对全部关键字信息的扫描,所以对于数据库中频繁使用的range query,B+树有着更高的性能。

  B*-tree是B+-tree的变体,在B+树的基础上(所有的叶子结点中包含了全部关键字的信息,及指向含有这些关键字记录的指针),B*树中非根和非叶子结点再增加指向兄弟的指针;B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2)。给出了一个简单实例,如下图所示:

  B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。

  B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针。

  B树是一棵平衡树,它是把一维直线分为若干段线段,当我们查找满足某个要求的点的时候,只要去查找它所属的线段即可。依我看来,这种思想其实就是先找一个大的空间,再逐步缩小所要查找的空间,最终在一个自己设定的最小不可分空间内找出满足要求的解。一个典型的B树查找如下:

  R树在数据库等领域做出的功绩是非常显著的。它很好的解决了在高维空间搜索等问题。举个R树在现实领域中能够解决的例子:查找20英里以内所有的餐厅。如果没有R树你会怎么解决?一般情况下我们会把餐厅的坐标(x,y)分为两个字段存放在数据库中,一个字段记录经度,另一个字段记录纬度。这样的话我们就需要遍历所有的餐厅获取其位置信息,然后计算是否满足要求。如果一个地区有100家餐厅的线次位置计算操作了,如果应用到谷歌地图这种超大数据库中,这种方法便必定不可行了。

  R树就很好的解决了这种高维空间搜索问题。它把B树的思想很好的扩展到了多维空间,采用了B树分割空间的思想,并在添加、删除操作时采用合并、分解结点的方法,保证树的平衡性。因此,R树就是一棵用来存储高维数据的平衡树。

  本片博客前面部分截取自算法(第4版)定义: 查找:要判断一个键是否存在树中,先将它和根节点中的键比较,如果它和其中任意一个相等,查找命中;否则就根据比较的结果找到指向相应区间的连接,并在其指向的子树中...博文来自:早起的虫儿灬

  2-3树插入删除操作,由于时间原因,仅仅只实现了插入操作。 2-3树插入操作,分三类。 1.在头节点插入这个可以直接生成一个二节点容纳就行。 2.插入的是一个二节点直接将二节点升级成为三节点,保留原本...博文来自:cty的博客

  1、2-3-4树介绍2-3-4树每个节点最多有四个字节点和三个数据项,名字中2,3,4的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况:①、有一个数据项的节点总是有两个子...博文来自:那年少年

  1.B树平衡二叉树的查找效率为O(log2N)与树的深度相关,通过降低树的深度,可以提高查找效率,但是还有一个瓶颈就是,每次查找一次就只能得到一个节点元素,如果查找一次能得到多个节点元素,那么在同样的...博文来自:huangwei18351的博客

  多路查找树    其每一个结点的孩子数可以多于两个,且每一个结点处可以存储多个元素。由于它是查找树,所有元素之间存在某种特定的排序关系。在这里,每一个结点可以存储多少个元素,以及它的孩子数的多少是非常...博文来自:的博客

  应用场景:解决在硬盘中的大量数据中的查找。因为大量数据存储在硬盘中,不能一次全部加载到内存中,而每次查一个数据读一次硬盘,读取速度太慢,这时就需要使用一种数据结构一部分一部分读入,这就是多路查找树的作...博文来自:Kerer的博客

  本文详细讲解B树、B-树、B+树、B*树的原理,通过参照网络资源整理编写1.B树B树也就是最基本的二叉搜索树,只不过换了个名字而已。每个非叶子节点最多只能存放两个孩子,其中节点的左孩子一定比该节点小,...博文来自:chixujohnny

  1.0什么是2-3树2-3树是具有如下性质的树对于每一个结点他有1或者2个关键码那么什么时候关键码为1个呢?或者说关键码为1个的时候有什么性质呢当有一个关键码的时候这个节点的子树会有两个当这个节点的关...博文来自:靠脑袋是真滴记不住啊!!!!!!!!

  年前实现了一个2-3树,后来就玩儿去了,再后来看书去了,所以就耽搁了。基本上网上找不到什么2-3树的实现,大概是因为这东西基本真正被用过吧。基于它的思想而发明的B树,B+树才是线树...博文来自:茅屋

  树(Tree)是N(N=0)个结点的有限集。当N=0时成为空树,在任意一棵非空树种:-有且仅有一个特定的成为根(Root)的结点。-当N1时,其余结点可分为m(m0)个互不相交的有限集T1,T2...博文来自:luobo140716的专栏

  二叉树二叉查找树(BST) 笛卡尔树 MVP树 Toptree T树 自平衡二叉查找树AA树 AVL树 左倾红黑树 红黑树 替罪羊树 伸展树 树堆 节点大小平衡树 B树B+树 B*树 Bx树 UB树 ...博文来自:Augusdi的专栏

  1、树的基本概念深度:计算一个节点的深度,从根节点算起(记住从1开始计数),到该节点所经过的节点数。高度:计算一个节点的高度,从叶子节点算起(记住从1开始计数),到该节点所经过的节点数。节点的度:树的...博文来自:u012133048的博客

  1.B树是一种平衡的多路查找树,其中每一个节点的孩子数可以多于2个,且每一个节点可以存储多个元素。2.节点最大的孩子数目称为B树的阶。一个M阶的B树具有以下属性:  .如果根节点不是叶子节点,则至少有...博文来自:qingcunsuiyue的博客

  B树插入满节点分裂有两种方法。一种是递归写法,即先往下找到要插入的节点,直接插入。满了就传值到上层进行分裂,一种是迭代写法,在找要插入的节点过程中遇到满街点就分裂,自然当插入的节点满了往上传时其父节点...博文来自:BenjaminYoung29的博客

  目录多路搜索树B树B+树:多路搜索树首先,介绍一下2-3树,指的是其中每一个节点2结点--有两个孩子或者3结点--三个孩子或者没有孩子,2节点指的是该节点有一个元素和两个孩子OR没有孩子,3节点指的是...博文来自:QiwzDeBLOG的博客

  2-3查找树第一次接触它是在刷数据结构那本书时,有它的介绍。而那时候只是单纯的理解它的节点是如何分裂,以及整个构建过程,并不清楚它的实际用处,所以看了也就忘了。而当看完《算法》查找章节时,顿时有种顿悟...博文来自:Demon-初来驾到

  多路查找树(muitl-waysearchtree),其每一个节点的孩子数可以多于两个,且每一个节点处可以存储多个元素。主要有4中特殊形式。一、2-3树定义:其中的每一个节点都具有两个孩子(称为2节点...博文来自:小地盘的诺克萨斯

  B-tree就是我们常说的B树,常常用于实现数据库索引,因为它的查找效率比较高前面提到的2-3树可以看作B树的一种实例一.为什么不用二叉搜索树用B树?  二叉查找树的时间复杂度是O(logN),查找次...博文来自:kaka

  转载自:这哥们讲的太好了2-3树是二叉查找树的变种,树中的2和3代表两种节点,以下...博文来自:的博客

  1.2-3-4树是什么在二叉树中,每个节点有一个数据项,最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点,就是多叉树(multiwaytree)。2-3-4树就是一种阶为4的多叉树,...博文来自:冰河

  2-3树一棵2-3树具有下例性质:一个节点包含一个或者两个关键码;每个内部节点有2个子女(如果它包含一个关键码),或者3个子女(包含2个关键码);所有叶子节点在树的同一层,因此树总是高...博文

  本人今天学习了一种数据结构,那,就是2-3树。2-3树,一种平衡查找树。首先,要知道什么是2-3树,就得了解二叉排序树。定义:二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:(1)若左子树不空,...博文来自:O.K的博客

  二叉树二叉树 · 二叉查找树 (BST)· 笛卡尔树 · Toptree · T树 自平衡二叉查找树AA树 · AVL树 · 红黑树 · 伸展树 · 树堆 · 节点大小平衡树 B树B树 · B+树 ·...博文来自:积累

  从B树、B+树、B*树谈到R树目录(?)[+]第一节B树B树B树4B树的高度第二节R树处理空间存储问题简介R树的数据结构叶子结点的结构非叶子结点R树的操作搜索删除结语从B树、B+树、B*树谈到R树 作...博文来自:m0_37232228的博客

  B+树的优势:1.单一节点存储更多的元素,使得查询的IO次数更少。2.所有查询都要查找到叶子节点,查询性能稳定。3.所有叶子节点形成有序链表,便于范围查询...博文来自:的博客

  一、B+树的结点组成B+树包含两种结点:0、根结点:(一般区分为两种,这里我将根结点分开说明,因为根节点非常特殊而且唯一)   若树只有一层:仅有根结点,此根结点也是叶结点,根结点中索引值个数无最少限...博文来自:Calcular的博客

  前面介绍的BST(二叉排序树)和AVL(平衡二叉树)都是二叉树,用作内部查找的数据结构,即被查找的数据集不大,可以放在内存中。这篇博客将主要介绍B树,是非二叉树,用作外部查找的数据结构...博文来自:u012256398的专栏

  介绍红黑树之前,要先了解其他几种树(二叉树,二叉排序树,平衡二叉树),红黑树就是在其他树的变形(特别是平衡二叉树,要先明白平衡二叉树,读者要先去了解一下)。一、红黑树介绍:1、性质:性质1、每个节点是...博文来自:田园园野的博客

  二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在...博文来自:coderecord的博客

  刚开始学习的时候,百度去查,但发现好多说得太复杂不好理解,结合各个文章总结一下(建议大概看文字,不理解不要紧,然后再看图的执行步骤然后在结合文字,这样一切就清晰好多)B-tree,B是balance,...博文来自:许恕

  从二叉查找树、2-3树彻底理解红黑树引言在学习红黑树的时候,看了很多文章,发现都没有讲明白红黑树的原理,只是简单列了红黑树的几条规则,就开始讲解红黑树的插入,让人一直不知其所以然。也很难深刻的理解红黑...博文来自:勿在浮沙筑高台

  一、定义2-3查找树的定义如下:要么为空,要么:对于2节点,该节点保存一个key及对应value,以及两个指向左右节点的节点,左节点也是一个2-3节点,所有的值都比key要小,右节点也是一个2-3节点...博文来自:Programming is an art form.

  2-3树简介实现过程代码实现2-3树简介2-3树是最简单的B-树(或-树)结构,其每个非叶节点都有两个或三个子女,而且所有叶都在统一层上。2-3树的模拟过程可以看链接:InsertSortion实现过...博文来自:fpk2014的博客

  一、什么是2-3-4树2-3-4树和红黑树一样,也是平衡树。只不过不是二叉树,它的子节点数目可以达到4个。每个节点存储的数据项可以达到3个。名字中的2,3,4是指节点可能包含的子节点数目。具体而言:1...博文来自:想作会飞的鱼的博客

  日志结构的合并树TheLog-StructuredMerge-Tree近年来,随着互联网数据的日益增长,管理分布式数据需求的日益增加,Bigtable[1]等一系列NoSQL数据库开始涌现。Bigta...博文来自:pi9nc的专栏

  译者:July。出处:。    在上一篇文章--从B树、B+树、B*树谈到R树里已提到2-3-4树,那么本文,咱们就从2-3-4树开始谈起,...博文来自:Ella.ting的专栏

  最近很多人问,如何将内网的摄像机流媒体数据发布到公网,如果用公网与局域网间的端口映射方式太过麻烦,一个摄像机要做一组映射,而且不是每一个局域网都是有固定ip地址,即使外网主机配置好了每一个摄像机的映射...博文来自:Babosa的专栏

  对于J2EE项目导入导出Excel是最普通和实用功能,本工具类使用步骤简单,功能强大,只需要对实体类进行简单的注解就能实现导入导出功能,导入导出操作的都是实体对象. 请看一下这个类都有哪些功能:   ...博文来自:李坤 大米时代 第五期

  原文地址:因为需要用,所以才翻译了这个文档。但总归赖于英语水平很有限,翻译出来的中文有可能...博文来自:ymj7150697的专栏

  帐号相关流程注册范围 企业 政府 媒体 其他组织换句话讲就是不让个人开发者注册。 :)填写企业信息不能使用和之前的公众号账户相同的邮箱,也就是说小程序是和微信公众号一个层级的。填写公司机构信息,对公账...博文来自:小雨同学的技术博客

  练习1:实现 first-fit 连续物理内存分配算法 在实现first fit 内存分配算法的回收函数时,要考虑地址连续的空闲块之间的合并操作。提示:在建立空闲页块链表时,需要按照空闲页块起始地址来...博文来自:cs_assult的专栏

  相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。        常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是: ⑴ 找出算法...博文来自:杨威的博客

  webService学习(二)—— 调用自定义对象参数 本文主要内容: 1、如何通过idea进行webService Client的简单实现(不再使用wsimport的方式,其实是ide帮我们做了...博文来自:止水的专栏

  SSH是一种以安全、加密方式连接远程主机或服务器的方法。SSH服务器接受从有SSH的客户机的连接,允许操作者象在本地一样地登录系统。你可以用SSH从远程运行shell和X程序。它是一种服务器维护管理的...博文来自:天涯路的专栏

  概念: java中单例模式是一种常见的设计模式,单例模式分三种:懒汉式单例、饿汉式单例、登记式单例三种。 单例模式有一下特点: 1、单例类只能有一个实例。 2、单例类必须自己自己创建自...博文来自:一个本科小生的奋斗史

  最近比较有空,大四出来实习几个月了,作为实习狗的我,被叫去研究Docker了,汗汗! Docker的三大核心概念:镜像、容器、仓库 镜像:类似虚拟机的镜像、用俗话说就是安装文件。 容器:类似一个轻量...博文来自:我走小路的博客

  本篇文章是根据我的上篇博客,给出的改进版,由于时间有限,仅做了一个简单的优化。相关文章:将excel导入数据库2018年4月1日,新增下载地址链接:点击打开源码下载地址十分抱歉,这个链接地址没有在这篇...博文来自:Lynn_Blog

  本文的目的是用C实现生成Gabor模版,并对图像卷积。并简单提一下,Gabor滤波器在纹理特征提取上的应用。 一、什么是Gabor函数(以下内容含部分翻译自维基百科)   在图像处理中,Gabor...博文来自:Where there is life, there is hope

  Weka为一个Java基础上的机器学习工具,上手简单,并提供图形化界面,提供如分类、聚类、频繁项挖掘等工具,本篇文章主要写一下分类器算法中的J48算法及其实现。 一、算法 J4...博文来自:路远,漫步前行

  目前市场上比较多的应用在用户卸载后会弹出意见反馈界面,比如360手机卫士,腾讯手机管家,应用宝等等,虽然本人不太认同其交互方式,但是在技术实现上还是可以稍微研究下的。其实要实现这个功能,最主要的就是监...博文

  扫二维码关注,获取更多技术分享 本文承接之前发布的博客《 微信支付V3微信公众号支付PHP教程/thinkPHP5公众号支付》必须阅读上篇文章后才可以阅读这篇文章。由于最近一段时间工作比较忙,...博文来自:Marswill

  强连通分量: 简言之 就是找环(每条边只走一次,两两可达) 孤立的一个点也是一个连通分量   使用tarjan算法 在嵌套的多个环中优先得到最大环( 最小环就是每个孤立点)   定义: int Ti...博文来自:九野的博客

  我们可能经常会用到这一功能,比如有时,我们不希望用户没有进行登录访问后台的操作页面,而且这样的非法访问会让系统极为的不安全,所以我们常常需要进行登录才授权访问其它页面,否则只会出现登录页面,当然我的思...博文来自:沉默的鲨鱼的专栏

  jquery/js实现一个网页同时调用多个倒计时(最新的) 最近需要网页添加多个倒计时. 查阅网络,基本上都是千遍一律的不好用. 自己按需写了个.希望对大家有用. 有用请赞一个哦! //js ...博文来自:Websites

  使用taocode作为SVN的服务器,地址在网站上注册和登录 新建一个项目 输入相关信息 复制这个地址,一会要用 下一步在MyEclipse中向SV...博文来自:weiyi556的博客

  以下从Java角度解释面试常见的算法和数据结构:字符串,链表,树,图,排序,递归 vs. 迭代,动态规划,位操作,概率问题,排列组合,以及一些需要寻找规律的题目。 1. 字符串和数组 字符...博文来自:DUANJIEFEI的专栏

  自己整理编写的逻辑回归模板,作为学习笔记记录分享。数据集用的是14个自变量Xi,一个因变量Y的australian数据集。 1. 测试集和训练集3、7分组 australian ...博文来自:Tiaaaaa的博客

  一、概述最近在springboot项目引入thymeleaf模板时,使用非严格标签时,运行会报错。默认thymeleaf模板对html5标签是严格检查的。二、在项目中加NekoHTML库在Maven中...博文来自:Luck_ZZ的博客

  一、代理模式为某个对象提供一个代理,从而控制这个代理的访问。代理类和委托类具有共同的父类或父接口,这样在任何使用委托类对象的地方都可以使用代理类对象替代。代理类负责请求的预处理、过滤、将请求分配给委托...博文来自:小小本科生成长之路

  第五 添加数据库管理员数据与用户数据 这个比较无聊 用java拼接了一下sql语句 然后写入数据库 这个放在附件上传就好了 第六 管理员与用户的登入验证 1、验证码。验证码一般就是...博文来自:得之我幸--失之我命

  花了一天!因为要用Keil,又苦于主题不好看,一个个换主题又嫌麻烦,就写了这个东西。代码有点多,先放出配置步骤,源码在文末。V1.0,没有图片预览功能,但是随插件附赠几个类似VS的配色方案。 本是按...博文来自:Q1275918492

  hfut31415926:1、auto_ptr存储的指针应该为NULL或者指向动态分配的内存块。 2、auto_ptr存储的指针应该指向单一物件(是new出来的,而不是new[]出来的)。 3、两个auto_ptr对象不会同时指向同一块内存块。要明白2个auto_ptr对象赋值会发生什么。 4、千万不要把auto_ptr对象放在容器中

  hfut31415926:现在的代码,不会泄露Type类型的对象。不管是函数正常结束,还是抛出异常结束,都会调用pt的析构函数,从而删除分配的对象。

本文链接:http://shawntierney.com/fangwenjubuxing/323.html