B树是平衡树的一种,主要用于操作存储在磁盘等二级存储设备上的大量数据。相比起内存(主存)来说,磁盘操作的速度非常慢(慢几个数量级),所以涉及到存储在磁盘的数据的时候,尽量减少磁盘的读取和写入操作对于提高操作速度是非常重要的。B树就是针对这个特点进行设计以满足相应要求的。
B树的性质:
- 1. B树内的每一个节点x都具有以下字段:
- 当前存储在节点x中的关键字(key)个数n[x]。
- 存储在x节点中的n[x]个关键字是以非降序的顺序排列的,即:key1[x] ≤key2[x]......≤keyn[x][x]。
- 一个表示x节点否是叶节点的bool值leaf[x]。
- 2. 每个内节点拥有指向n[x]+1个指向叶节点的指针,c1[x],c2[x]......cn[x]+1[x]。叶节点没有ci[x]域
- 3. 节点x的key值,将子节点的key值范围分开了。如果ki是ci[x]指向的子节点的任意一个key的值,那么有:
k1 ≤ key1[x] ≤ k2 ≤ key2[x] ≤ ≤ keyn[x][x] ≤ kn[x]+1.
- 4. 所有的叶节点具有相同的深度,这个深度也就是树高h。
- 5. 一个节点可容纳的关键字数目是有上下限的。这个界限可以用包含一个大于2的整数t的表达式来表示,这个数t称为B树的最小度。
- 除根节点外,每个节点至少要包含t-1个关键字(key),每个内节点(除根外)至少要包含t个关键字。一棵非空的B树,根节点至少要包含一个key。
- 每个节点最多包含2t-1个关键字,因此,内节点最多有2t个子节点。对于一个包含2t-1个关键的节点,我们就称这个节点满了。
B树的每个节点都会拥有大量的子节点,而B树树高也很小。一般情况下,每个节点都会存储大量的关键字,使得节点大小接近磁盘页面大小,因为磁盘读取一个页面的数据时,相对会快一些(由于机械结构方面的原因,读取连续一个页面的数据,机械臂移动很小)。另外,根据B树的构造方式,节点的关键越多,也就能拥有越多的子节点,这对降低B树的高度很关键,B树的树高越小,那么读取磁盘的操作也会越少。速度也就相应得到提高。
B树的高度: h<logt(n+1/2)
B树的查找操作(Search):
B树的查找操作比较简单,可以看成是二叉查找树查找操作的简单扩展。因为每个节点中的key都是有序排列的,所以只需要从根节点开始,对每个节点进行如下的递归操作:
将目标keyTarget从节点x的最小关键值key1[x]开始比对,一直找到keyTarget第一次大于某个关键值keyi[x],可知,如果keyTarget等于keyi+1[x],则keyi+1[x]就是要找查找的对象,如果keyTarget不等于keyi+1[x],那么,keyTarget就是存在于ci+1[x]所指向的子树中。然后在这个子树根节点重复上述查找过程,一种到找到目标对象,或是到叶节点后仍然无法找到该对象,则返回NULL。
B树的创建
B树的创建很简单,就是创建一个空的根节点即可。要注意的是,不论是B树的创建或是插入操作中,都需要创建新的节点的操作(ALLOCATT_NODE)。这个操作会分配一般是分配一个新的磁盘页的空间供B树使用。
B树的插入操作
B树插入操作不像二叉查找树(先找到合适位置,然后创新一个新节点插入该位置)那样单纯,显然这样做会破坏B树的应有性质。因此,对于B树,新的key值会插入到某个节点中。但对于满的节点,也是不能直接插入新key值的。这时就需要一个节点的split(分裂)操作。把满的节点,分成两个新节点,这两个新节点各得原节点的一半key值和一半节点,原节点中最中间的key提升到父节点去作为新节点的区分标志。这样,就解决了向满节点插入的key值的问题。但这样求父节点本身是非满状态的,否则子节点中提升上来的key值就不能正常插入了。因此,对于B树的插入操作来说,从根开始往下寻找新key值插入位置的时候,只要一遇到满节点,就立即进行split,而不是等到在叶节点进行插入操作后遇到节点满状态再split。这样,就可以在进行split操作时,保证被分裂的节点始终有一个非满状态的父节点。
对于根节点,也要进行特殊和处理,(根很特殊,因为我们知道树根只有一个,而且根节点是始终放在主存中的,指向它的引用也是唯一且需要保持的。根节点可以存任意不超过2t-1个key而没有下限限制。)在根节点进行split时,我们还需要维持一些其它的属性(特别是对树根的引用)。
B树的删除操作
- 1. 如果键值k是在一个叶节点x中,那么直接从x中删除掉k。
- 2. 如果键值k是在一个内节点x中,那么要分下面几种情况处理:
- A) 如果x的子节点y(这个节点是关键值k的直接前趋键值所在的子节点)含有至少t个键值,则找到这个键值的直接前趋k',递归地删除k'值,然后在x节点中用k'代替k值。(查找和删除k'值可以在单向向下的过程中完成)
- B) 对称地,如果x的子节点z(关键值k的直接后继键值所在的子节点)含有至少t个键值,则查找找到并递归删除掉直接后继k',然后在x节点中用k'代替k。
- C) 如果上面两种情况中说的y和z中都只有t-1个键值存在,那么就将k和z的全部键值合并到y节点中,这样x节点就失去了一个键值k和指向z的指针。然后释放z节点,并继续递归地删除y中的k值。
- 3. 如果k不在内节点x中,则找到以ci[x]为根的包含k值的那棵子树(如果k值确实存在的话)。如果ci[x]只有t-1个键值,就执行3a或是3b以保证我们在向下寻找的过程中到达的节点都是含有至少t个键值的。最后递归过程会在某个节点终止(删除了k或是找不到k)
- A) 如果ci[x]只有t-1个键值但其直接相邻的兄弟节点有t个以上的键值,那么,从x节点中移一个键值给ci[x],再从ci[x]相邻的兄弟节点中移一个键值上来给x,并对指向子节点的指针进行适当地调整。
- B) 如果ci[x]和它相邻的兄弟节点都只有t-1个键值,那么就将ci[x]和其中一个兄弟节点合并(这还需要把x中的一个键值移动到新节点中成为一个中间键值。)
分享到:
相关推荐
读书笔记:《算法导论》B树实现
二叉树、平衡二叉树(如AVL树和红黑树)、B树、B+树等都是常见的树类型。这些数据结构在数据库索引、文件系统、图搜索等领域有广泛应用。理解树的遍历(前序、中序、后序)和操作(如插入、删除)是掌握树算法的基础...
《算法导论》是计算机科学领域的一本经典之作,它深入浅出地介绍了算法的设计、分析和实现。在第四章中,我们主要探讨了“主定理”和“主方法”,这两个概念对于理解和解决复杂度为递归形式的算法至关重要。 主定理...
在这个“MIT算法导论公开课之课程笔记 9.二叉搜索树”中,我们将会深入探讨这种数据结构的特点、操作以及其在算法中的应用。 首先,二叉搜索树的关键特性是:对于任意节点,其左子树中所有节点的键都小于该节点的键...
5. **B树和B+树**:B树和B+树是多路搜索树,常用于数据库和文件系统中。这些树的每个节点可以有多个子节点,允许每个节点存储多个关键字。B树适合于磁盘等外部存储,因为它减少了I/O操作的次数。B+树的所有关键字都...
《MIT算法导论公开课之课程笔记 4.竞争性分析、自组织表》涵盖了两个重要的算法分析主题:竞争性分析和自组织表。这两个概念在计算机科学,特别是算法设计与分析领域具有深远的影响。 首先,让我们深入理解竞争性...
github:还有除了算法导论外一些基础知识的笔记 我们能做到的排序有多快? 速度取决于计算模型【哪些操作是被允许的】 比较排序的算法模型 在模型中只能进行两两之间的大小比较来决定顺序 快速排序 归并排序 插入...
在上述文档中,我们看到的是关于数据结构的一些核心知识点的串讲笔记,涵盖了栈、队列、二叉树、树以及图的存储结构和遍历方法。 1. **栈**: 栈是一种具有“后进先出”(LIFO)特性的数据结构。题目中提到了已知出栈...
7. **工具与资源**:利用在线平台如LeetCode、HackerRank进行练习,参考经典的教材如《算法导论》、《数据结构与算法分析》等。 在“ljg_resource1”中,可能包含了以上部分或全部内容的讲解,可能是详细的文章、...
介绍 《算法导论》(CLRS)第三版中的一些练习和问题。 永远不要相信回购单字。 您可以使用 Chrome扩展程序读取。 如果Markdown和TeX的语法存在冲突,请告诉我是否格式错误。笔记本摘要我基础1算法在计算中的作用2...