B-Tree的性质介绍

B-树是一种常见的数据结构。和他一起的还有B+树。

在这里，需要澄清一下概念。B树，B-树，B+树有什么区别？他们有什么关系呢？

其实，从数据结构来讲只有2种，也就是B-树和B+树。有时候，B-树又称为B树，他们是一个东西。请注意，B-树中间的“-”是连字符，而不是“减号”。英文中是B-Tree，翻译成中文后，也就是B树，有的翻译喜欢把连字符“-”也带着，于是就成了B-树，而B-树被有些读者误读为B减树。

介绍B-树之前，首先看一下一个重要的概念：阶。

一个树的阶，就是这个树中各个节点的子节点个数的最大值。也就是说，如果有的节点有2个子节点，有的节点有4个子节点，最多的有5个子节点，那么，这个树的阶就是5.

从这个角度来讲，二叉树的阶是2.

接下来，我们介绍一下B-树的主要性质。我们假定B-树的阶为m。一个m阶的B-树，要么是一个空树，要么是具有如下性质的树：

1，每个节点最多有m个子节点。最少有m/2（向上取整）个节点。或者这么表述：m/2 <= 子节点个数<= m。但是根节点是例外的，根节点可以最少有2个子节点。

2，每个节点的子节点的个数，比该节点中保存的关键字的个数多1. 也就是，当节点中保存k个关键字时，该节点会有k + 1个子节点（子树）。

3，每个节点中的k个关键字是按照从小到到排列的，分别记为k1，k2，k3，......kk。那么该节点会有k+1个指针，记为p0，p1，p2，......pk。并且，p3所指向的子节点中的所有元素，都大于k3，且都小于k4. 如下图所示。这一点也比较容易理解和记忆，各个指针p整好位于关键字k的插空的位置，所以，插空处的指针指向的子节点的元素的值，就理所当然的应该大于指针左边的元素，小于指针右边的元素。

4，B-树是严格的平衡查找树，它的左右子树的高度是相等的。且叶子节点处于同一层，并且可以用空节点表示。

一个B-树的例子：

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

赞 (0)

相关推荐

  • 完整B树算法Java实现代码

    完整B树算法Java实现代码

    定义 在计算机科学中,B树(英语:B-tree)是一种自平衡的树,能够保持数据有序.这种数据结构能够让查找数据.顺序访问.插入数据及删除的动作,都在对数时间内完成. 为什么要引入B树? 首先,包括前面我们介绍的红黑树是将输入存入内存的一种内部查找树. 而B树是前面平衡树算法的扩展,它支持保存在磁盘或者网络上的符号表进行外部查找,这些文件可能比我们以前考虑的输入要大的多(难以存入内存). 既然内容保存在磁盘中,那么自然会因为树的深度过大而造成磁盘I/O读写过于频繁(磁盘读写速率是有限制的),进而导

  • 浅谈MySQL的B树索引与索引优化小结

    浅谈MySQL的B树索引与索引优化小结

    MySQL的MyISAM.InnoDB引擎默认均使用B+树索引(查询时都显示为"BTREE"),本文讨论两个问题: 为什么MySQL等主流数据库选择B+树的索引结构? 如何基于索引结构,理解常见的MySQL索引优化思路? 为什么索引无法全部装入内存 索引结构的选择基于这样一个性质:大数据量时,索引无法全部装入内存. 为什么索引无法全部装入内存?假设使用树结构组织索引,简单估算一下: 假设单个索引节点12B,1000w个数据行,unique索引,则叶子节点共占约100MB,整棵树最多20

  • MySQL Hash索引和B-Tree索引的区别

    MySQL Hash索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree 索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以 Hash 索引的查询效率要远高于 B-Tree 索引. 可 能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree 高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree 索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash 索引效率高,但是 Hash 索引本身由于其特殊性也带来了很多限制和弊

  • B-树的插入过程介绍

    B-树的插入过程介绍

    上文https://www.jb51.net/article/154153.htm我们介绍了B-树的性质,本文我们来介绍一下B-树的插入过程. 插入过程和树的构建过程本质是一致的,即都是进行插入操作,并对插入后的B-树进行调整. 我们设定B-树的阶为5.用关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}来构建一棵B-树. 因为树的阶为5,那么,每个节点最多有5个子节点,每个节点内的关键字个数为3~4个. 于是,第一步是插入1,2,

  • bitmap 索引和 B-tree 索引在使用中如何选择

    现在,我们知道优化器如何对这些技术做出反应,清楚地说明 bitmap 索引和 B-tree 索引各自的最好应用. 在 GENDER 列适当地带一个 bitmap 索引,在 SAL 列上创建另外一个位图索引,然后执行一些查询.在这些列上,用 B-tree 索引重新执行查询. 从 TEST_NORMAL 表,查询工资为如下的男员工: 1000 1500 2000 2500 3000 3500 4000 4500 因此: SQL> select * from test_normal 2 where s

  • SQLite中的B-Tree实现细节分析

    SQLite在存储在外部的数据库是以B-Tree来组织的.关于B-tree的细节,参考 ** ** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3: ** "Sorting And Searching", pages 473-480. Addison-Wesley ** Publishing Company, Reading, Massachusetts. ** 基本思想是文件包含的每一页都包括N个数据库入口和N+1

  • 基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    基于B-树和B+树的使用：数据搜索和数据库索引的详细介绍

    B-树 1 .B-树定义 B-树是一种平衡的多路查找树,它在文件系统中很有用. 定义:一棵m 阶的B-树,或者为空树,或为满足下列特性的m 叉树:⑴树中每个结点至多有m 棵子树:⑵若根结点不是叶子结点,则至少有两棵子树: ⑶除根结点之外的所有非终端结点至少有[m/2] 棵子树:⑷所有的非终端结点中包含以下信息数据: (n,A0,K1,A1,K2,-,Kn,An)其中:Ki(i=1,2,-,n)为关键码,且Ki<Ki+1, Ai 为指向子树根结点的指针(i=0,1,-,n),且指针Ai-1 所指子

  • c语言B树深入理解

    c语言B树深入理解

    B树是为磁盘或其他直接存储设备设计的一种平衡查找树.如下图所示.每一个结点箭头指向的我们称为入度,指出去的称为出度.树结构的结点入度都是1,不然就变成图了,所以我们一般说树的度就是指树结点的出度,也就是一个结点的子结点个数.有了度的概念我们就简单定义一下B树(假设一棵树的最小度数为M):1.每个结点至少有M-1个关键码,至多有2M-1个关键码:2.除根结点和叶子结点外,每个结点至少有M个子结点,至多有2M个子结点:3.根结点至少有2个子结点,唯一例外是只有根结点的情况,此时没有子结点:4.所有叶

  • B-树的删除过程介绍

    B-树的删除过程介绍

    上文https://www.jb51.net/article/154157.htm我们介绍了B-树的插入过程,本文我们来介绍B-树的删除过程. 在B-树中删除节点时,可能会发生向兄弟节点借元素,和孩子节点交换元素,甚至节点合并的过程. 我们以下面的树为基础,进行删除操作. 首先明确一下这个树的定义.它是一个5阶树.所以,每个节点内元素个数为2~4个. 我们依次删除8.16.15.4这4个元素. 首先删除8,因为删除8后,不破坏树的性质,所以直接删除即可.得到如下 然后删除16,这导致该节点只剩下

  • 单调栈的基本性质介绍

    单调栈的定义: 单调栈就是栈内元素单调递增或者单调递减的栈,单调栈只能在栈顶操作. 为了更好的理解单调栈,则可将单调栈用生活情形模拟实现,例如: 我们借用拿号排队的场景来说明下.现在有很多人在排队买可乐,每个人手里都拿着号,越靠前的人手里的号越小, 但是号不一定是连续的.小明拿了号后并没有去排队,而是跑去约会了.等他回来后,发现队伍已经排得很长了, 他不能直接插入到队伍里,不然人家以为他是来插队的.小明只能跑到队伍最后,挨个询问排队人手里的号, 小明认为号比他大的人都是"插队"的,于是

  • C++中单调栈的基本性质介绍

    单调栈的定义: 单调栈就是栈内元素单调递增或者单调递减的栈,单调栈只能在栈顶操作. 为了更好的理解单调栈,则可将单调栈用生活情形模拟实现,例如: 我们借用拿号排队的场景来说明下.现在有很多人在排队买可乐,每个人手里都拿着号,越靠前的人手里的号越小, 但是号不一定是连续的.小明拿了号后并没有去排队,而是跑去约会了.等他回来后,发现队伍已经排得很长了, 他不能直接插入到队伍里,不然人家以为他是来插队的.小明只能跑到队伍最后,挨个询问排队人手里的号, 小明认为号比他大的人都是"插队"的,于是

  • B-Tree的性质介绍

    B-Tree的性质介绍

    B-树是一种常见的数据结构.和他一起的还有B+树. 在这里,需要澄清一下概念.B树,B-树,B+树有什么区别?他们有什么关系呢? 其实,从数据结构来讲只有2种,也就是B-树和B+树.有时候,B-树又称为B树,他们是一个东西.请注意,B-树中间的"-"是连字符,而不是"减号".英文中是B-Tree,翻译成中文后,也就是B树,有的翻译喜欢把连字符"-"也带着,于是就成了B-树,而B-树被有些读者误读为B减树. 介绍B-树之前,首先看一下一个重要的概念

  • jQuery EasyUI API 中文文档 - Tree树使用介绍

    用 $.fn.tree.defaults 重写了 defaults. 依赖 draggable droppable 用法 Tree 能在 <ul> 元素里定义,此标记可以定义为叶节点和子节点.下面是一个示例: 复制代码 代码如下: <ul id="tt"> <li> <span>Folder</span> <ul> <li> <span>Sub Folder 1</span> &

  • Java 递归遍历实现linux tree命令方式

    Java 递归遍历实现linux tree命令方式

    目录 Java 递归遍历实现linux tree命令 递归调用的函数traversal printName函数 java实现zTree的遍历 Java 递归遍历实现linux tree命令 看到介绍java file类的文章,有一个遍历文件夹的练习,遍历某个目录下所有文件,包括子目录.写了一个用栈实现的递归遍历. import java.io.File; import java.util.Stack; public class TraversalFile { public static void

  • ASM的tree api对匿名线程的hook操作详解

    ASM的tree api对匿名线程的hook操作详解

    目录 背景 ASM介绍 class文件 fields methods InsnList Signature 实战部分 解决“匿名”Thread 最后 背景 看完本章,你将会学习到用ASM的tree api进行对匿名线程的hook操作,同时也能够了解到asm相关的操作和背景知识介绍!对于ASM插桩来说,可能很多人都不陌生了,但是大多数可能都停留在core api上,对于现在市面上的一些插桩库,其实很多都用tree api进行编写了,因为tree api的简单与明了的特性,也越来越成为许多开源库的选

  • MySQL索引背后的之使用策略及优化(高性能索引策略)

    MySQL索引背后的之使用策略及优化(高性能索引策略)

    本章的内容完全基于上文的理论基础,实际上一旦理解了索引背后的机制,那么选择高性能的策略就变成了纯粹的推理,并且可以理解这些策略背后的逻辑. 示例数据库 为了讨论索引策略,需要一个数据量不算小的数据库作为示例.本文选用MySQL官方文档中提供的示例数据库之一:employees.这个数据库关系复杂度适中,且数据量较大.下图是这个数据库的E-R关系图(引用自MySQL官方手册): 图12 MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en

  • MySQL索引背后的数据结构及算法原理详解

    MySQL索引背后的数据结构及算法原理详解

    摘要 本文以MySQL数据库为研究对象,讨论与数据库索引相关的一些话题.特别需要说明的是,MySQL支持诸多存储引擎,而各种存储引擎对索引的支持也各不相同,因此MySQL数据库支持多种索引类型,如BTree索引,哈希索引,全文索引等等.为了避免混乱,本文将只关注于BTree索引,因为这是平常使用MySQL时主要打交道的索引,至于哈希索引和全文索引本文暂不讨论. 文章主要内容分为三个部分. 第一部分主要从数据结构及算法理论层面讨论MySQL数据库索引的数理基础. 第二部分结合MySQL数据库中My

  • Android 6.0动态权限申请教程

    PermissionManage 项目地址:https://github.com/why168/AndroidProjects/tree/master/PermissionManage 介绍 如果设备运行的是 Android 6.0(API 级别 23)或更高版本,并且应用的 targetSdkVersion 是 23 或更高版本,则应用在运行时向用户请求权限. 如果设备运行的是 Android 5.1(API 级别 22)或更低版本,并且应用的 targetSdkVersion 是 22 或更

  • Vue实现全局异常处理的几种方案

    目录 一.前端常见异常 二.实现简单的全局异常处理 三.Vue3 如何实现异常处理 四.总结 在开发组件库或者插件,经常会需要进行全局异常处理,从而实现:\ 全局统一处理异常: 为开发者提示错误信息: 方案降级处理等等. 那么如何实现上面功能呢?本文先简单实现一个异常处理方法,然后结合 Vue3 源码中的实现详细介绍,最后总结实现异常处理的几个核心. 本文 Vue3 版本为 3.0.11 一.前端常见异常 对于前端来说,常见的异常比较多,比如: JS 语法异常: Ajax 请求异常: 静态资源加

随机推荐