一:简介
B树是为磁盘而设计的一种平衡查找树,类似于红黑树,但在降低磁盘io次数上更好一些!常用于数据库系统。B树不同于红黑树主要在于B树的结点可以有许多子女,这是由磁盘的特性决定的。因此,B树可以在O(lgN)的时间内完成许多动态几何的操作!
二:性质
如果B树的内结点x含有N[x]个关键字,则x就含有N[x]+1个子女。结点X用来将x的关键字域划分成n[x]+1个域。在查找某个关键字时,就可以通过对X中的x[n]个关键字的比较,来得出n[x]+1路的决定!
因为是对磁盘而设计的数据结构,故对磁盘的读取次数是对数据结构的衡量标准之一!一个B树的分支因子越大,则同样的关键字时,B树的高度就越小,对磁盘的读取次数也就越小!
三:B树的定义
一颗B树是具有如下性质的有根树:
1. 每个节点有三个域:n[x]:节点x中的关键字数;n[x]个关键字本身,并且按非减次序排序;布尔量leaf[x] 指示x是否是叶节点。
2. 每个内结点有n[x]+1个指向其子女的指针:c1[x],c2[x]…Cn[x]+1[x]。其中,叶节点的c域为空。
3. 各个关键字keyi[x]对存储在各子树中的关键字范围加以分割!假设ki为存储在以keyi[x]为根节点的子树中的关键字,则有:
K1<KEY1[x]<K2<KEY2[x]<K3<KEY3[x]……KEY n[x][X]<K n[x]+1
4. 每个叶节点有相同的高度,即树的高度为H
5. 每个节点包含的关键字树有一个上界和一个下界,这些界用一个称作B树的最小度数的固定整数t来表示!
6. 一个非根的结点至少有t-1个关键字,有t个子节点,如果一个树是非空树,则该树的根节点至少有一个关键字!
7. 每个结点可以至多包含2t-1个关键字和2t个子女,如果一个结点包含2t-1个关键字,则该节点称为满结点!
四:B树的高度
B树上的大多数操作所需的磁盘存取次数与B树的高度成正比的!
可以得到证明得到高度H和关键字树N和最小度数t的关系如下:
H<logt(N+1)/2
五:B树的基本操作之搜索
在每个内结点x处要做N[x]+1次的分支决定,而对于二叉树则只需2次分支决定,
他是对二叉树查找的一次推广!
伪代码如下:
B—TREE-SEARCH(x,k)
i=1
while i<n[x] and k>keyi[x]
do i=i+1
if i<n[x] and k==keyi[x]
then return(x,i)
if leaf[x]
then return null
else DISK-READ(ci[x])
return B-TREE- SEARCH(ci[x],k)
时间分析:B—TREE-SEARCH(x,k)所需的磁盘读取次数为:O(h)
由于n[x]<2t,故第三行的循环的时间为O(t) ,故总的才cpu时间为O(t*LOG t N)
六:B树的基本操作之插入
步骤是先调用B—TREE-CREATE(T)来创建一个空的根节点,再调用B—TREE-INSERT()来加入新的关键字,另外,还有一个辅助过程ALLOCATE-NODE他在O(1)的时间内创建一个新的结点!
1、创建一个新节点,这个比较简单伪代码如下:
B—TREE-CREATE(T)
x=ALLOCATE-NODE()
leaf[x]=true
n[x]=0
DISK-WRITE(x)
root[T]=x
2、对已经创建的空的根结点进行插入处理,这个比较复杂一些,因为创建了一个结点并不能简单的插入,而要保持B树的7大性质!此处,先用B—TREE-SPITE-CHILD来确保要插入处的结点以及该节点的双亲结点不是满结点。
A:B树中结点的分裂:伪代码如下
B—TREE-SPITE-CHILD(x,i,y) //其中Ci[x]=y
z= ALLOCATE-NODE()
leaf[z]=leaf[y]
n[z]=t-1
for j=1 to j=t-1
do key j[z]=key j+t[y]
if not leaf[y]
then for j=1 to t
do Cj[z]=Cj+t[y]
n[y]=t-1
for j=n[x]+1 down to i+1
do Cj+1[x]=Cj[x]
Ci+1=z
For j=n[x] down to i
do key(j+1)[x]=key(j)[x]
key(i)[x]=key(t)[y]
n[x]=n[x]+1
DISK-WRITE(y)
DISK-WRITE(z)
DISK-WRITE(x)
从以上的伪代码可以看出,B—TREE-SPITE-CHILD(x,i,y)是以“剪贴”的方式进行操作的,其中y是x的第i个孩子,也是要被分裂的结点!
B:对B树用单程下行的遍历方式插入关键字
在一颗高度为h的B树T中,插入一个关键字k的操作,是在延树下降的过程中一次完成的,共需要O(h)次的磁盘读取时间,并且此过程通过B—TREE-SPITE-CHILD保证递归始终不会降到一个满结点上。伪代码如下:
B—TREE-INSERT(T,k)
r=root[T]
if n[r]=2t-1
then s= ALLOCATE-NODE()
root[T]=s
leaf[s]=false
n[s]=0
C1[s]=r
B—TREE-SPITE-CHILD(s,1,r)
B—TREE-INSERT-NONFULL(s,k)
else B—TREE-INSERT-NONFULL(r,k)
C:调用B—TREE-INSERT-NONFULL将关键字k插入到非满的根节点中,此过程中适当的加入B—TREE-SPITE-CHILD操作,来确保每个结点都是非满的!直到结束为止,伪代码如下:
B—TREE-INSERT-NONFULL(x,k)
i=n[x]
if leaf[x]
then while i>1 and k<key(i) [x]
do key(i+1)[x]=key(i)[x]
i=i-1
key(i+1)=k
n[x]=n[x]+1
DISK-WRITE(x)
Else while i>1 and k<key(i)[x]
do i=i-1
i=i+1
DISK-READ(C(i)[x])
if n[C(i)[x]]=2t-1
then B—TREE-SPITE-CHILD(x,I,C(i)[x])
if k>key(i)[x]
then i=i+1
B—TREE-INSERT-NONFULL(C(i)[x],k)
时间分析:B—TREE-INSERT要做的磁盘存取次数为O(h),总的cpu时间O(t h)=O(t*LOGt N)!
七:B树的基本操作之删除
对B树的删除是B树操作中最为复杂的事情了,因为不止是从叶子结点中删除,而且会从内结点中删除,这样就要重新布置B树的结构,使其继续满足B树性质!
删除的操作比较复杂,故不再给出伪代码,主要分为如下几个大类:
<1>如果关键字k在结点x中,并且x是叶节点,则直接从x中删除k
<2>如果关键字所在的结点是内结点,则做如下操作:
A. 如果结点x中前于k的子节点y中至少包含t个关键字,即找出k在以y为根的子树中的前驱k’,递归的删除k’,并在x中用k’代替k。
B. 对称的,如果结点x中位于k之后的子节点z中至少包含t个关键字,即找出k在以z为根的子树中的后继k’,递归的删除k’,并在x中用k’代替k
C. 否则,如果y和z都只有t-1个关键字,则将k和z中的所有关键字合并到y中,使得x失去k和指向z的指针,然后释放z并在y中删除k。
<3>如果关键字k不在内结点x中,则确定必包含k的正确的子树的根C(i)[x],如果C(i)[x]只有t-1个关键字,执行以下的A或B来保证我们降至一个包含至少t个关键字的结点,然后,通过对x的某个子节点递归而结束。
A. 如果C(i)[x]只包含t-1个关键字,但他的一个相邻兄弟包含至少t个关键字,则将x中的某一个关键字降至C(i)[x]中,将C(i)[x]的相邻兄弟或者右兄弟中的某一关键字升至x中,并将该兄弟中合适的子女指针指向C(i)[x]中。
B. 如果C(i)[x]和她的所有兄弟都只包含t-1个关键字,则将C(i)[x]和任意一个兄弟结点合并,并在x结点中找出一个合适的关键字移植到新合并的结点中当做中间关键字。
删除操作的时间分析:
磁盘存取次数为O(h),总的cpu时间O(t h)=O(t*LOGt N)!
——记录于2013/3/17
分享到:
相关推荐
在本项目中,作者根据《算法导论》中的描述实现了B-树的源代码。 首先,`bMinusTree.cpp`文件很可能是B-树的主体实现部分,包含了插入、删除和查找等基本操作的函数。这些操作需要遵循B-树的平衡原则,确保树的高度...
读书笔记:《算法导论》B树实现
《算法导论第四版》涉及了如红黑树、B树、二叉搜索树、平衡查找树、哈希表、图的搜索算法(深度优先搜索和广度优先搜索)以及最小生成树、最短路径问题等高级主题。这部分内容为读者提供了处理更复杂数据结构和算法...
6. 高级数据结构:包括红黑树、B树、B+树、伸展树等自平衡树结构,及其在数据库和文件系统中的应用。 7. 图算法:介绍图的基本概念,如路径、连通性、有向图和无向图等,深入分析图的遍历算法(深度优先搜索和广度...
7. **第9章:高级数据结构** - 这一章可能会介绍更复杂的数据结构,如红黑树、B树、Trie树等,以及与之相关的搜索和操作算法。 通过解决这些章节的课后习题,读者不仅可以深化对算法的理解,还能提升解决问题的能力...
《算法导论》原书名——《Introduction to Algorithms》,是一本十分经典的计算机算法书籍,与高德纳(Donald E.Knuth)的《计算机程序设计艺术》(《The Art Of Computer Programming》)相媲美。 《算法导论》由...
1. **排序与搜索算法**:包括冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等基本排序算法,以及二分查找、哈希表和B树等搜索数据结构。这些算法对于优化数据处理速度至关重要。 2. **图算法**:如...
二叉树、平衡二叉树(如AVL树和红黑树)、B树、B+树等都是常见的树类型。这些数据结构在数据库索引、文件系统、图搜索等领域有广泛应用。理解树的遍历(前序、中序、后序)和操作(如插入、删除)是掌握树算法的基础...
2. **查找算法**:二分查找、哈希表查找、B树和B+树等,它们在数据库和信息检索中扮演着重要角色。 3. **图算法**:包括最短路径算法(如Dijkstra算法、Floyd-Warshall算法)、最小生成树(Prim算法、Kruskal算法)...
8. **数据结构**:算法往往与特定的数据结构密切相关,如数组、链表、栈、队列、树(二叉树、平衡树、B树等)、图、哈希表等。理解并能灵活运用这些数据结构,对于设计和实现高效算法至关重要。 9. **递归与迭代**...
在大数据算法导论第四周的课程中,重点讲解了用于数据查找(搜索)的各种数据结构,包括散列表、布隆过滤器、二叉树、红黑树、B树等。同时,还详细讨论了散列函数的概念和选择好的散列函数的方法,以及在散列表中...
- **教学意义**: 在中国科学技术大学的算法导论课程中,回溯法作为计算机科学与技术专业学生必须掌握的重要内容之一,有助于培养学生的算法设计与分析能力。 **2. 搜索算法简介** - **穷举搜索**: 对所有可能的...
根据给定文件的信息,我们可以提炼出以下相关的IT知识点: ...以上知识点总结了《算法导论》第三章中关于数据结构和红黑树的核心概念、性质及其实现原理,对于深入理解红黑树的工作机制和应用场景具有重要意义。
- 如红黑树、B树等,这些数据结构在数据库系统、文件系统中有广泛应用。 - 数据结构的选择对算法性能有重要影响。 2. **图算法**: - 图算法涉及到图论中的基本概念和算法,如最小生成树算法、最短路径算法等。 ...
从给定的文件信息来看,这是一份关于算法导论的测试题,主要涉及了算法分析中的关键概念和技巧,包括递归式求解、真假判断题以及简答题。下面,我们将对这些知识点进行详细解析。 ### 1. 递归式的解决方法 递归式...
9. **数据结构设计**:如平衡二叉搜索树(AVL树、红黑树)、字典树(Trie)和B树等。这些数据结构优化了查找、插入和删除操作的时间复杂度。 10. **模板类和泛型编程**:C++的模板机制允许编写通用的代码,适用于多...
第16章可能涉及查找算法,如二分查找、B树和B+树等。 9. **图论与网络流**:第24章可能涵盖图论的更多内容,如最大流问题和最小割问题,这是网络流理论的一部分。第25章可能涉及更复杂的算法,如网络简单路径和多源...
- 树结构:二叉树、平衡树(如AVL树、红黑树)、B树和B+树,广泛应用于数据库索引和搜索。 - 图结构:图的表示(邻接矩阵、邻接表),遍历方法(深度优先搜索DFS和广度优先搜索BFS)。 3. **排序算法**: - 冒泡...