B-树
是一种多路搜索树(并不是二叉的):
1.定义任意非叶子结点最多只有M个儿子;且M>2;
2.根结点的儿子数为[2, M];
3.除根结点以外的非叶子结点的儿子数为[M/2, M];
4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)
5.非叶子结点的关键字个数=指向儿子的指针个数-1;
6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
7.非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的
子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
8.所有叶子结点位于同一层;
如:(M=3)
B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果
命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为
空,或已经是叶子结点;
B-树的特性:
1.关键字集合分布在整颗树中;
2.任何一个关键字出现且只出现在一个结点中;
3.搜索有可能在非叶子结点结束;
4.其搜索性能等价于在关键字全集内做一次二分查找;
5.自动层次控制;
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少
利用率,其最底搜索性能为:
其中,M为设定的非叶子结点最多子树个数,N为关键字总数;
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占
M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;
B+树
B+树是B-树的变体,也是一种多路搜索树:
1.其定义基本与B-树同,除了:
2.非叶子结点的子树指针与关键字个数相同;
3.非叶子结点的子树指针P[i],指向关键字值属于[K[i], K[i+1])的子树
(B-树是开区间);
5.为所有叶子结点增加一个链指针;
6.所有关键字都在叶子结点出现;
如:(M=3)
B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在
非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;
B+的特性:
1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好
是有序的;
2.不可能在非叶子结点命中;
3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储
(关键字)数据的数据层;
4.更适合文件索引系统;
相关推荐
使用java实现B+ tree, 可以编译运行通过。
实现了B tree的添加删除,查找。key value 用C++模板方式。希望对学习数据结构的有帮助。作者曾成功用在大型文件的查找中 建立Map映射。
B tree 插入算法(2 加入了 栈和队列操作代码) ,在原来基础上增加了底层操作代码,适合unix和windows
b plus tree in windows c++
数据结构中的B-TREE的实现
B tree 的一个插入算法 C++完成,面向对象特性很突出,值得学习,但是代码可能需要一点点优化,需要继续改进,但是基本结构已经很不错
c 语言开发b-tree数据文件索引 .zipc 语言开发b-tree数据文件索引 .zip
B+树的实现,利用JAVA写的,有详细的注释说明
B+ tree implementation
三阶B-树的节点插入与删除 三阶B-树的节点插入与删除
also về mô phỏ ng b-tree bằ ng c # have a few missing số t
一个用Basic实现的B-Tree算法
综合2叉树及B+树优点的能根据增删改而分裂或合并的完整程序(现在以8bit(BYTE key)为关键字,可扩充到64bit的double为key,用户数据包现在以float ton表示,可扩充到任意结构struct)
简单介绍B-tree与B+tree,帮助大家对其有个深入的理解
BTREE 树形文件处理系统 灵活,好用 欢迎下载使用
BTree,B-Tree,B+Tree,BTree都是什么.doc
B-Tree代码,包含完整工程,可执行 B-Tree代码,包含完整工程,可执行
In this project you are supposed to implement a B+ tree of order 3 with the following operations: initialize insert (with splitting) and search. The B+ tree should be able to print out itself.Input ...
been so successful It discusses the major variations of the B-tree, especially the B+-tree, contrasting the relatwe merits and costs of each implementatmn. It illustrates a general purpose access ...
B-Tree的C++版本,可以实现B树的建立,插入,查找,删除,本代码中默认为3阶B-Tree,通过修改宏定义,可以修改为任意阶B-Tree