B+树是一个n叉树,每个结点通常有多个孩子,一棵B+树包含根结点、内部结点和叶子结点。根结点可能没有子女,也可能有两个或两个以上子女(就是说不可能只有一个子女)。
m阶B+树和m阶B-树的差异在于:
1.有n棵子树的结点中含有n个关键字;
2.所有的叶子结点中包含了全部关键码的信息,及指向含有这些关键码记录的指针,且叶子结点本身依关键码的大小自小而大的顺序链接。
3.所有的非终端结点可以看成是索引部分,结点中仅
含有其子树根结点中最大(或最小)关键码。
通常在B+树上有两个头指针,一个指向根结点,另一个指向关键字最小的叶子节点。因此可以对B+树进行两种查找运算:一种是从最小关键字起顺序查找,另一种是从根节点开始,进行随机查找。在B+树上进行随机查找、插入和删除的过程基本上与B-树类似。只是在查找时,若非终端结点上的关键码等于给定值,并不终止,而是继续向下直到叶子结点。因此,在B+树,不管查找成功与否,每次查找都是走了一条从根到叶子结点的路径。
B+树在数据库中的应用
目前大部分数据库系统及文件系统都采用B-Tree或其变种B+Tree作为索引结构。在数据库索引的应用中,B+树按照下列方式进行组织:
① 叶结点的组织方式 。B+树的查找键 是数据文件的主键 ,且索引是稠密的。也就是说 ,叶结点 中为数据文件的第一个记录设有一个键、指针对 ,该数据文件可以按主键排序,也可以不按主键排序 (即数据文件的排序可以跟索引的排序无关) ;数据文件按主键排序,则B +树上的关键码为稀疏索引,即在叶结点中为数据文件的每一个“块”设有一个键、指针对 ;数据文件不按键属性排序 ,且该属性是 B +树 的查找键 , 叶结点中为数据文件里出现的每个“属性”K设有一个键、指针对,其中指针执行排序键值为 K的 记录中的第一个。
② 非叶结点 的组织方式。B+树中的非叶结点形成了叶结点上的一个多级稀疏索引。 每个非叶结点中至少有ceil( m/2 ) 个指针 , 至多有 m 个指针 。
PS:
稠密索引:如果记录是排好序的,我们就可以在记录上建立稠密索引,它是这样一系列存储块:块中只存放记录的键以及指向记录本身的指针,指针就是一个指向记录或存储块地址。稠密索引文件中的索引块保持键的顺序与文件中的排序顺序一致。既然我们假定查找键和指针所占存储空间远小于记录本身,我们就可以认为存储索引文件比存储数据文件所需存储块要少得多。当内存容纳不下数据文件,但能容纳下索引文件时,索引的优势尤为明显。这时,通过使用索引文件,我们每次查询只用一次I/O操作就能找到给定键值的记录。
稀疏索引:稀疏索引只为数据文件的每个存储块设一个键-指针对,它比稠密索引节省了更多的存储空间,但查找给定值的记录需更多的时间。只有当数据文件是按照某个查找键排序时,在该查找键上建立的稀疏索引才能被使用,而稠密索引则可以应用在任何的查找键。
分享到:
相关推荐
一个B树,B+树,B*树的详细讲解,可以作为初学者的一个学习资料。
基于B+树数据库的图书管理系统c++源码+详细注释+详细说明文档.zip 基于B+树数据库的图书管理系统c++源码+详细注释+详细说明文档.zip 基于B+树数据库的图书管理系统c++源码+详细注释+详细说明文档.zip 基于B+树数据库...
一个外国人写的B+树算法,由于注释比较少,故个人在参照时加上了自己的注释。该代码还用带了LRR和折半查找技术,很值得参考学习!!
算法学习:B-树与B+树
算法学习:从B树、B+树、B_树谈到R_树
最简单的B加树源码,只实现了添加和删除、打印操作,方便学习。
很详细的c++版的B+树的算法实现,正在学习算法的同学很有用哦
最近看了B+树的存储,在网上找到几个实例,最后把一个作者整理的分享下。该源码来自网上,作者说已经在生产环境使用,所以选择了它
数据库一般由B+树实现,B+树又是由B树演化来的。学习B树可以帮助理解数据库的数据结构,包括数据库索引。项目由VS2015创建,已经测试通过,代码参考了算法导论。大家共同学习进步!
C++课程设计-基于B+树数据库的图书管理系统+源代码+文档说明+pdf - 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心...
Linux操作系统大作业,通过数据结构实现B+树,红黑树,堆排序等操作+源代码+文档说明+实验报告 - 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码都测试ok,都是运行成功后才...
主要介绍了多路搜索树B树、B+树,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧
在Linux环境下,通过C语言编程实现四个程序,分别为:堆排序、用栈实现表达式求值、B+树和红黑树+源代码+文档说明+实验报告 - 小白不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的课程设计,代码...
课设-基于B+树数据库的图书管理系统c++实现源码(含程序说明+函数文档说明等).zip 程序功能 基础功能 1.登录注册 2.查找书籍(支持多条件查询) a)根据id(唯一) b)根据ISBN c)根据作者 d)根据出版社 3.用户操作 a)...
B + Tree基于Posix的数百万(数十亿)键值存储的最小B + Tree实现。 分支内存用于学习和调试。 演示./demo_build.sh代码覆盖率测试B + Tree基于Posix的数百万(数十亿)键值存储的最小B + Tree实现。 分支内存用于...
B +树 基于Posix的数百万(数十亿)键值存储的最小B + Tree实现。 科 用于学习和调试。 演示版 ./demo_build.sh 代码覆盖率测试 注意:此测试需要首先使用rm /tmp/coverage.index* ! ./coverage_build.sh
B+树的Java ,python和c#代码,适合直接使用,非常不错的学习资源
针对蓝桥杯的考察内容,结合B站等在线学习平台上的资源,我们可以构建一条详细的算法学习路线,以下是对这一路线的扩展描述。 一、基础算法与数据结构 蓝桥杯竞赛的基础是扎实的算法与数据结构知识。这包括但不...
本人学习数据结构时写的B-树的代码,用C++编写的,在Linux上用Gcc 4.5.1编译通过,实现了B-树的构造与删除,以及节点的查找,插入和删除。