便于理解,引入多个定义,从多个角度讨论。
B-树的定义1:
一棵m(m≥3)阶的B-树是满足如下性质的m叉树:
(1)每个结点至少包含下列数据域:
(j,P 0 ,K l ,P 1 ,K 2 ,…,K i ,P i )
其中: j为关键字总数,
K i (1≤i≤j)是关键字,关键字序列递增有序:K 1 <K 2 <…<K i
P i (0≤i≤j)是孩子指针。对于叶结点,每个P i 为空指针。
注意:
①实用中为节省空间,叶结点中可省去指针域P i ,但必须在每个结点中增加一个标志域leaf,其值为真时表示叶结点,否则为内部结点。
②在每个内部结点中,假设用keys(Pi)来表示子树Pi中的所有关键字,
则有:keys(P 0 )<K 1 <keys(P 1 )<K 2 <…<K i <keys(P i )
即关键字是分界点,任一关键字Ki左边子树中的所有关键字均小于K i ,右边子树中的所有关键字均大于K i 。
(2)所有叶子是在同一层上,叶子的层数为树的高度h。
(3)每个非根结点中所包含的关键字个数j满足:若树非空,则根至少有1个关键字,故若根不是叶子,则它至少有2棵子树。根至多有m-1个关键字,故至多有m棵子树。
B-树的定义2
B-树是一种平衡的多路查找树(与二叉查找树,平衡二叉树相对应而言),它有较高的查找的效率,在文件系统中很有用.主要用于文件索引。
一、B-树的定义
一棵"m 阶的B树"或为空树,或为具有以下特性的 m 叉查找树:
以下(1),(2)是保证其为平衡树的特性
(1)树中每个结点至多有 m 棵子树;
(2)除根以外的所有非叶结点至少有 [m/2 ](向上取整)棵子树,根结点若是非叶结点,则至少有两棵子树;
补充;对于每个非叶节点,它有n个索引项/关键字,有n+1个指向子树根结点的指针;
以下(3),(4)是保证其为查找树的特性
(3)所有的非叶结点中含有如下信息:
(n,A0,(K1,D1),A1,(K2,D2),……,An-1,(Kn,Dn),An)
(Ki,Di)(i=1,…,n)为索引项,ki为索引项的关键码,Di为指向索引项内容(或记录)的指针。
Ki<Ki+1(i=1,…,n-1);
Ai(i=0,…,n) 为指向子树根结点的指针。
Ai-1 所指子树中所有索引项的关键码小于Ki(i=1,…,n),An 所指子树中索引项的关键码大于 Kn,n(m/2-1≤n≤m-1) 为结点中索引项的个数。
(4)所有叶结点都在同一层上,且不含任何信息。
下图为一棵3阶B-树:
相比定义一,定义二更加具体。
二 B-树的特性
假如M为设定的非叶子结点最多子树个数,N为关键字总数;
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,确保它为平衡查找树,所以B-树的搜索性能总是等价于二分查找(与M值无关),也就没有B 树平衡的问题, 时间复杂度: O(log m/2 n);
1.关键字集合分布在整颗树中;
2.任何一个关键字出现且只出现在一个结点中;
3.搜索有可能在非叶子结点结束;
4.由于M/2的限制,插入和删除节点后能保证B树的平衡,且非叶的非根结点一般会有指向父节点的指针,使得插入和删除更加便利。在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合。
相关推荐
实验内容及要求:定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按...
网络红书 数据结构高分笔记 书中详尽且通俗的总结了新大纲计算机考研的知识点 对于数据结构基础不好的同学,无疑是最佳选择,2010年 最具影响力的计算机考研辅导书
数据结构-B树和B键树.ppt
数据结构B树的完整实现,自己写的,看完后一定有所启发。
B-树和B+树的C语言实现(数据结构)。
定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
该设计要实现B-数的算法,要求输入一个序列,建立B-树,能够查找指定节点,并且能够遍历整个B-树,输出遍历序列结果。
相关理论知识参见 《数据结构基础》 张力译版 ,我是先实现的B—树, 有B-树的基础上实现的B+树 可以先看B-树 ,再看B+树 。二者实现我已经尽量的使他们相互独立了。
实现了严蔚敏版《数据结构》上的B-树,通过千万随机数测试。
想研究算法的可以参考一下, 本文所讨论的m路查找树多为可以动态调整的多路查找树
定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
B-树的各种操作 C++ 数据结构 严蔚敏 完全是课本上的 花了好长时间
电大数据结构-选择题 电大数据结构-选择题全文共5页,当前为第1页。电大数据结构-选择题全文共5页,当前为第1页。02.同一种逻辑结构 B.可以有不同的存储结构 电大数据结构-选择题全文共5页,当前为第1页。 电大...
这学期数据结构的课程设计,用B—树模拟索引文件。
定义B-树存储结构(要求m3;为方便操作,结点中增加双亲结点指针域,最底层的Fail结点用NULL指针表示并且所有结点均存储于内存)。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
B树、B-树、B+树、B*树,B树即二叉搜索树: 1、所有非叶子节点至多拥有两个儿子; 2、所有节点存储一个关键字; 3、非叶子节点的左指针指向小于其关键字的子树,右指针指向大于其关键字 的子树; .......
包括实验报告 编程环境:Vs Code 编程语言:C 利用C语言数据类型表示B树的抽象数据类型,以及B树的抽象数据类型的实现。 抽象数据类型树的定义:树的结构定义和树的一组基本操作
山东大学数据结构实验B-树(java实现)
1.1 针对考研数据结构的代码书写规范以及C 与C 语言基础1 1.1.1 考研综合应用题中算法设计部分的代码书写规范1 1.1.2 考研中的C 与C 语言基础3 1.2 算法的时间复杂度与空间复杂度分析基础 12 1.2.1 考研中的算法时间...
无向图、有向图、带权图(网) 2022/7/9 3 第七章 图 A B C D E F A B C D E A B C D 8 6 3 9 4 1 2 5 数据结构-图的存储表示全文共28页,当前为第3页。 Graph=( V, E ) V = { v " v 某数据对象} 顶点的有穷非空...