热门标签 | HotTags
当前位置:  开发笔记 > 程序员 > 正文

数据结构中什么是B树?

数据结构中什么是B树?B树是为了磁盘或其它存储设备而设计的一种多叉(下面你会看到,相对于二叉,B树每个内结点有多个分支,即多叉)平衡查找树。B树又叫平衡多路查找树。一棵m阶的B树(

数据结构中什么是B树?

B 树是为了磁盘或其它存储设备而设计的一种多叉(下面你会看到,相对于二叉,B树每个内结点有多个分支,即多叉)平衡查找树。B 树又叫平衡多路查找树。

一棵m阶的B 树 (m叉树)的特性如下:树中每个结点最多含有m个孩子(m>=2);除根结点和叶子结点外,其它每个结点至少有[ceil(m / 2)]个孩子(其中ceil(x)是一个取上限的函数);若根结点不是叶子结点,则至少有2个孩子(特殊情况:没有孩子的根结点,即根结点为叶子结点,整棵树只有一个根节点);所有叶子结点都出现在同一层,叶子结点不包含任何关键字信息(可以看做是外部接点或查询失败的接点,实际上这些结点不存在,指向这些结点的指针都为null);每个非终端结点中包含有n个关键字信息: (n,P0,K1,P1,K2,P2,......,Kn,Pn)。

其中: a) Ki (i=1...n)为关键字,且关键字按顺序升序排序K(i-1)

B+树结构参考

B+树的内部节点包括:Key键值,Index索引值 B+树的叶子节点包括:Key键值,Index索引值,Data数据 B+树的内部节点也可称为索引节点,叶子节点也可称为外部节点 它与B树的差异在于: 如下图,是一个B+树: 下图是B+树的插入动画: B树、B+树和二叉树、平衡二叉树一样,都是经典的数据结构。 B+树由B树和索引顺序访问方法(ISAM,是不是很熟悉?对,这也是MyISAM引擎最初参考的数据结构)演化而来,但是在实际使用过程中几乎已经没有使用B树的情况了。

B+树的定义十分复杂,因此只简要地介绍B+树:B+树是为磁盘或其他直接存取辅助设备而设计的一种平衡查找树,在B+树中,所有记录节点都是按键值的大小顺序存放在同一层的叶节点中,各叶节点指针进行连接。

B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。 由于B+树在内部节点上不包含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子节点上关联的数据也具有更好的缓存命中率。

B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。

相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。 但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。下面是B 树和B+树的区别图: 对于一颗节点为N度为M的子树,查找和插入需要logM-1N ~ logM/2N次比较。

这个很好证明,对于度为M的B树,每一个节点的子节点个数为M/2 到 M-1之间,所以树的高度在logM-1N至logM/2N之间。 这种效率是很高的,对于N=62*1000000000个节点,如果度为1024,则logM/2N <=4,即在620亿个元素中,如果这棵树的度为1024,则只需要小于4次即可定位到该节点,然后再采用二分查找即可找到要找的值。

数据结构中B树、B+树的区别

一、B树的起源 B树,最早是由德国计算机科学家Rudolf Bayer等人于1972年在论文 《Organization and Maintenance of Large Ordered Indexes》提出的,不过我去看了看原文,发现作者也没有解释为什么就叫B-trees了,所以把B树的B,简单地解释为Balanced或者Binary都不是特别严谨,也许作者就是取其名字Bayer的首字母命名的也说不定啊…… 二、B树长啥样 还是直接看图比较清楚,图中所示,B树事实上是一种平衡的多叉查找树,也就是说最多可以开m个叉(m>=2),我们称之为m阶b树,为了体现本博客的良心之处,不同于其他地方都能看到2阶B树,这里特意画了一棵5阶B树 。 总的来说,m阶B树满足以下条件: 每个节点至多可以拥有m棵子树 根节点,只有至少有2个节点(要么极端情况,就是一棵树就一个根节点,单细胞生物,即是根,也是叶,也是树) 非根非叶的节点至少有的Ceil(m/2)个子树(Ceil表示向上取整,图中5阶B树,每个节点至少有3个子树,也就是至少有3个叉) 非叶节点中的信息包括[n,A0,K1,A1,K2,A2,…,Kn,An],,其中n表示该节点中保存的关键字个数,K为关键字且Ki

推荐阅读
  • 本文探讨了Java编程的核心要素,特别是其面向对象的特性,并详细介绍了Java虚拟机、类装载器体系结构、Java类文件和Java API等关键技术。这些技术使得Java成为一种功能强大且易于使用的编程语言。 ... [详细]
  • 对象自省自省在计算机编程领域里,是指在运行时判断一个对象的类型和能力。dir能够返回一个列表,列举了一个对象所拥有的属性和方法。my_list[ ... [详细]
  • 深入解析for与foreach遍历集合时的性能差异
    本文将详细探讨for循环和foreach(迭代器)在遍历集合时的性能差异,并通过实际代码示例和源码分析,帮助读者理解这两种遍历方式的不同之处。文章内容丰富且专业,旨在为编程爱好者提供有价值的参考。 ... [详细]
  • JavaScript 基础语法指南
    本文详细介绍了 JavaScript 的基础语法,包括变量、数据类型、运算符、语句和函数等内容,旨在为初学者提供全面的入门指导。 ... [详细]
  • 异常要理解Java异常处理是如何工作的,需要掌握一下三种异常类型:检查性异常:最具代表性的检查性异常是用户错误或问题引起的异常ÿ ... [详细]
  • Java每日一题:876. 链表的中间节点解析
    本文详细介绍了LeetCode上编号为876的题目——链表的中间节点,包括问题描述、解决方案和代码实现。 ... [详细]
  • Python处理Word文档的高效技巧
    本文详细介绍了如何使用Python处理Word文档,涵盖从基础操作到高级功能的各种技巧。我们将探讨如何生成文档、定义样式、提取表格数据以及处理超链接和图片等内容。 ... [详细]
  • 本文介绍了如何利用 Spring Boot 和 Groovy 构建一个灵活且可扩展的动态计算引擎,以满足钱包应用中类似余额宝功能的推广需求。我们将探讨不同的设计方案,并最终选择最适合的技术栈来实现这一目标。 ... [详细]
  • ThinkPad USB 硬盘启动 Ubuntu 系统的详细步骤
    本文介绍如何通过USB硬盘在联想ThinkPad上启动Ubuntu系统,包括BIOS设置和启动优先级调整。 ... [详细]
  • 本文将探讨Java编程语言中对象和类的核心概念,帮助读者更好地理解和应用面向对象编程的思想。通过实际例子和代码演示,我们将揭示如何在Java中定义、创建和使用对象。 ... [详细]
  • 本文详细介绍了如何通过现代化工具快速、高效地安装Python第三方模块,帮助开发者简化安装流程并提高开发效率。 ... [详细]
  • 雨林木风 GHOST XP SP3 经典珍藏版 V2017.11
    雨林木风 GHOST XP SP3 经典珍藏版 V2017.11 ... [详细]
  • Hadoop发行版本选择指南:技术解析与应用实践
    本文详细介绍了Hadoop的不同发行版本及其特点,帮助读者根据实际需求选择最合适的Hadoop版本。内容涵盖Apache Hadoop、Cloudera CDH等主流版本的特性及应用场景。 ... [详细]
  • 编写了几个500行左右代码的程序,但基本上解决问题还是面向过程的思维,如何从问题中抽象出类,形成类的划分和设计,从而用面向对象的思维解决问题?有这方面的入门好书吗?最好是结合几个具体的案例分析的 ... [详细]
  • Python 内存管理机制详解
    本文深入探讨了Python的内存管理机制,涵盖了垃圾回收、引用计数和内存池机制。通过具体示例和专业解释,帮助读者理解Python如何高效地管理和释放内存资源。 ... [详细]
author-avatar
小女人的忧伤--
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有