一、B树
1、B树的定义
B树是一种平衡的多分树,通常我们说m阶的B树,它必须满足如下条件:
(1)每个结点至多有m个子结点;
(2)除根结点和叶结点外,其它每个结点至少有 个子结点;
(3)若根结点不是叶子结点,则至少有两个子结点;
(4)所有的叶结点在同一层;
(5)有k个子结点的非根结点恰好包含k-1个关键码。
2、B树的查找
B树上的查找是一个顺指针查找结点和在结点内的关键码中查找交叉进行的过程。从根结点开始,在结点包含的关键码中查找给定的关键码,找到则查找成功;否则确定给定关键码可能在的子树,重复上面的操作,直到查找成功或者指针为空为止。
下图显示了在B树中查找关键码21的过程。
3、B树的插入
首先是在恰当的叶子结点中添加关键码,如果该结点中关键码不超过m-1个,则插入成功。否则要把这个结点分裂为两个。并把中间的一个关键码拿出来插到结点的父结点里去。父结点也可能是满的,就需要再分裂,再往上插。最坏的情况,这个过程可能一直传到根,如果需要分裂根,由于根是没有父结点的,这时就建立一个新的根结点。插入可能导致B树朝着根的方向生长。
下图显示了在B树中插入关键码33的过程。
4、B树的删除
B树中的删除操作与插入操作类似,但要稍微复杂些。如果删除的关键码不在叶结点层,则先把此关键码与它在B树里的后继对换位置,然后再删除该关键码。如果删除的关键码在叶结点层,则把它从它所在的结点里去掉,这可能导致此结点所包含的关键码的个数小于 -1。这种情况下,考察该结点的左或右兄弟,从兄弟结点移若干个关键码到该结点中来(这也涉及到它们的父结点中的一个关键码要做相应变化),使两个结点所含关键码个数基本相同。只有在兄弟结点的关键码个数也很少,刚好等于 -1时,这个移动不能进行。这种情况下,要把将删除关键码的结点,它的兄弟结点及它们的父结点中的一个关键码合并为一个结点。
二、B+树
1、B+树的概念
B+树是B树的一种变形树,它与B树的差异在于:
有k个子结点的结点必然有k个关键码;
非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
2、B+树的查找
跟B树的查找类似,但是也有不同。由于跟记录有关的信息存放在叶结点中,查找时若在上层已找到待查的关键码,并不停止,而是继续沿指针向下一直查到叶结点层的关键码。此外,B+树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。上面两种方式结合起来,使得B+树非常适合范围检索。
3、B+树的插入
B+树的插入与B树的插入过程类似。不同的是B+树在叶结点上进行,如果叶结点中的关键码个数超过m,就必须分裂成关键码数目大致相同的两个结点,并保证上层结点中有这两个结点的最大关键码。
4、B+树的删除
B+树中的关键码在叶结点层删除后,其在上层的复本可以保留,作为一个"分解关键码"存在,如果因为删除而造成结点中关键码数小于 ,其处理过程与B树的处理一样。
不同于B树只适合随机检索,B+树同时支持随机检索和顺序检索,在实际中应用比较多。
相关推荐
详细介绍了B/B+树的区别和各自的操作,内容详实,通俗易懂,介绍的很清晰
B-树和B+树的C语言实现(数据结构)。
转B树,B树,B+树,B树转B树,B树,B+树,B树转B树,B树,B+树,B树
c语言的代码实现B+树。基于文件操作。模拟B+树的建立索引
B+树索引 B+树索引 B+树索引 B+树索引 B+树索引 B+树索引
步骤为数据库文件创建一个B+树索引: (1)生成数据文件, (2)为数据库文件的属性创建B+ 树文件。 (3)给定键值,通过B+树进行查找。同时比较与直接扫描表的性能差别。(利用B+树时可根据内存大小决定放置多少层次到...
B+树,源代码,java实现,B+树,B+树,源代码,java实现,B+树
B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_B+ 树的组织结构_
本文是对B+树数据结构和算法的详细介绍文档。文章详细,生动的描述了如何构建一个B+树。
一个B树,B+树,B*树的详细讲解,可以作为初学者的一个学习资料。
B+树实现源码 B+树实现源码 B+树实现源码 B+树实现源码 B+树实现源码
B+树实现,利用文件在硬盘上存储,具体使用说明在文档中
这个程序是swing版本的b+树的实现及演示,适合学些b+树实现方式的同学们,详细情况可以参考我的博文:http://blog.csdn.net/cdnight/article/details/10973281, 希望对大家有所帮助。
B树、B-树、B+树、B树 算法实现及原理
B+树的C++实现版本 用法举例: /* * @param bkSize 区块大小,及每个数据块的大小,建议与硬盘的区块大小相同(一般为512或4096),此值不能过小否则会导致初始化失败. * @param filePath b+树关联的文件位置. * @...
B树、B-树、B+树、B树++、R_tree总结
第一节、B树、B+树、B*树 1.前言: 动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree/B+-tree/ B*-tree (B~Tree)。前三者是...
详细讲解b+树及各种操作:插入,删除,更新等。
相关理论知识参见 《数据结构基础》 张力译版 ,我是先实现的B—树, 有B-树的基础上实现的B+树 可以先看B-树 ,再看B+树 。二者实现我已经尽量的使他们相互独立了。
国外的B+树的讲义 与本站的《B+树分析》好像是一套的。