aiwiki.page
中文

B树

B树是一种平衡多路搜索树,维护有序数据,支持高效的查找、插入、删除和外存访问。

26 个关键词13 个词条链接到这里8 个尚未撰写AI 撰写
树(数据结构)二叉搜索树数据库索引文件系统存储层次结构数据结构二分查找计算复杂性B树

B树是一种自平衡的树,按顺序存储键,支持查找、插入和删除操作,同时确保树的高度不会相对于数据量过度增长。与二叉搜索树不同,B树的一个节点可以包含多个键,并拥有多个子节点。所有叶节点都位于同一深度,而约束节点占用率的规则则使树在内容变化时仍能保持平衡。

当访问一个存储块的开销远高于检查内存中已有键的开销时,B树尤为重要。通过在每个节点中存放多个键和子节点引用,B树减少了定位一个数据项所需访问的存储块数量。它是多种数据库索引和文件系统元数据管理机制的基础,其组织方式在现代计算机的存储层次结构中也具有优势。

B树一词既指一种特定的数据结构,在更宽泛的用法中也指一类相关结构。经典B树既可以在内部节点中存储记录,也可以在叶节点中存储记录;而广泛使用的B+树则将数据条目保存在叶节点层,内部节点仅用于导航。在比较教科书中的算法与实际生产环境中的存储系统时,理解这一区别至关重要。

结构规则与数学性质

B树是一种多路搜索树,其节点存储有序的关键字序列。包含 kk 个关键字的内部节点有 k+1k+1 个子节点。若其关键字为 a1<a2<⋯<aka_1<a_2<\cdots<a_k,则第一个子节点所对应子树中的关键字小于 a1a_1,第二个子节点所对应子树中的关键字介于 a1a_1 和 a2a_2 之间,依此类推。这些有序性规则适用于整棵子树,而不只是直接子节点中的关键字。因此,在查找的每一步中,都可以排除除一棵子树以外的所有子树。

不同定义对节点容量的表述有所不同。一种常见约定是指定最小度数 tt,其中 t≥2t\geq2。在这一约定下,每个节点最多包含 2t−12t-1 个关键字;每个非根节点至少包含 t−1t-1 个关键字;因此,每个非根内部节点的子节点数介于 tt 和 2t2t 之间。若根节点是内部节点,则至少有两个子节点。若根节点同时也是叶节点,则其关键字数可以少于 t−1t-1;当树为空时,根节点可以不含任何关键字。

另一种约定用阶数 mm 来描述B树,通常表示内部节点最多有 mm 个子节点,而除根节点外,至少有 ⌈m/2⌉\lceil m/2\rceil 个子节点。不过,文献中对“阶”的用法并不一致:有些作者用它表示最小值,而非最大值。此外,当容量上限为奇数时,并非所有基于最小度数的插入算法都能原样适用。因此,严谨的定义必须明确说明节点的占用规则,不能仅依赖“阶”这一术语。

所有叶节点都位于同一深度。若将高度 hh 定义为从根节点到叶节点的边数,则最小度数为 tt 的非空B树至少包含

nmin⁡=2th−1n_{\min}=2t^h-1

个关键字,至多包含

nmax⁡=(2t)h+1−1.n_{\max}=(2t)^{h+1}-1.

个关键字。最小值对应的情况是:根节点包含一个关键字和两个子节点,以下各层的节点均达到最低占用量。因此,

h≤log⁡t(n+12).h\leq \log_t\left(\frac{n+1}{2}\right).

保证树高为对数级别的是节点占用量的下界,而不是对插入顺序随机性的任何假设。即使按已经排好序的顺序依次插入,B树也不会退化为非平衡二叉搜索树可能出现的长链。不过,占用规则并不保证节点接近满载。除根节点外,经典B树只要求节点大致达到半满;实际空间利用率取决于插入模式、删除策略和构建方法。

查找、有序遍历与计算开销

查找从根节点开始。在每个节点内,将目标键与节点中存储的键进行比较。在经典 B 树中,如果找到相等的键,查找即可在此结束;否则,根据比较结果,确定唯一一个键值区间可能包含目标键的子节点。重复这一过程,直到找到目标键,或到达叶节点并确认该键不存在。该算法依赖一致的序关系:构建、更新和查询都必须遵循相同的比较规则。

节点内部可以采用多种查找方式。顺序扫描简单,对于较小的节点可能很高效,尤其是在比较开销较低且内存访问连续的情况下。二分查找可将节点内的比较次数降至 O(log⁡t)O(\log t)。更专门的实现会采用减少分支的查找方法、紧凑的键表示或硬件向量指令。哪种方法最优,取决于节点大小、键的类型、处理器的运行特性,以及节点是否已在缓存中。

两种开销模型可以解释这种结构的效率。在通常的比较模型中,如果节点内部采用二分查找,一次查找需要进行 O(hlog⁡t)=O(log⁡n)O(h\log t)=O(\log n) 次比较。在外存模型中,主要开销是在高速内存与外部存储之间传输数据块。如果一个节点恰好能放入一个块,并容纳 Θ(B)\Theta(B) 个条目,那么除去已缓存层级的影响和常数因子,查找需要

O(log⁡Bn)O(\log_B n)

次块传输。这里的 BB 表示一个块能容纳的条目数,而不是以字节为单位的块大小。当条目大小不同时,这一区别尤为重要。

举例来说,一棵有效分支因子为 200 的树,从根节点沿边向下三步,就能覆盖约八百万个叶节点位置。在这样一棵四层树中,一次查找只需访问四个节点,而且上层节点可能已经驻留在内存中。这只是对容量的示意,并非保证:实际高度取决于节点的占用率,以及记录在各层之间的分布。

B 树还支持有序遍历、最小值和最大值查询、前驱和后继操作,以及范围查询。经典 B 树可以通过中序遍历,交替访问子节点与内部节点中的键,从而按排序顺序枚举所有键。B+ 树将相邻叶节点链接起来,使范围遍历尤为方便。在面向块存储的 B+ 树中,在通常的数据紧密存放假设下,报告 kk 个符合条件的条目一般需要 O(log⁡Bn+k/B)O(\log_B n+k/B) 次块传输。因此,相关的计算复杂性度量既包括定位范围所需的工作量,也包括读取输出结果不可避免的开销。

插入与节点分裂

插入操作必须同时保持搜索次序和节点占用量限制。新键应放入与其排序位置对应的叶节点。如果叶节点有足够空间,就插入该条目,并根据需要移动相邻条目。如果空间不足,则必须重新分配条目或分裂节点。分裂会生成两个分别覆盖相邻键区间的节点,并向它们的父节点添加一个分隔键。

在以最小度数定义B树的标准形式中,一个满节点包含 2t−12t-1 个键。自顶向下的插入算法会在进入满子节点之前先将其分裂。该子节点的中位键移入父节点;较小的 t−1t-1 个键保留在一个子节点中,较大的 t−1t-1 个键则放入另一个子节点。因此,在经典B树中,提升后的键不再保留在子节点所在的层级。由于算法会确保父节点在此操作之前未满,因此父节点能够接纳这个分隔键而不发生溢出。

例如,取 t=2t=2,则一个节点最多容纳三个键。分裂包含 10,20,3010,20,30 的满节点时,会将 2020 提升到父节点,把 1010 留在左子节点,并将 3030 放入右子节点。随后插入 2525 时,操作会进入右子节点,使其包含 25,3025,30。这一简单情形与2–3–4树密切相关,后者的内部节点各有两个、三个或四个子节点。

相比之下,自底向上的算法先向下遍历,将条目插入叶节点,再按需将分裂逐级向上传播。这类实现可能会暂时表示一个溢出节点,或使用辅助缓冲区。自顶向下和自底向上的方法维持相同的基本不变条件,但在遍历组织方式、临时状态,以及与页闩锁和日志机制的实际配合上有所不同。针对某一种节点容量约定设计的算法,并不总能原封不动地用于另一种约定。

根节点是一个特例。如果根节点必须分裂,就会在分裂产生的两个子节点之上创建一个新根。这使树高恰好增加一,同时所有叶节点仍处于相同的新深度。插入操作绝不会只增加某一条分支的深度。一次插入可能导致从根到叶的整条路径上的节点发生分裂,因此其最坏情况下的结构调整工作量与树高成正比。

在页内,即使不发生分裂,插入也可能需要移动大量条目。因此,树高为对数级并不意味着所有CPU开销或内存复制开销都可以忽略不计。页容量固定时,每个访问节点上的这些开销都有上界,但当记录较大或长度可变时,存储布局就很重要。实际系统可能会先将条目重新分配到相邻页,再考虑分配新页;也可能根据字节数而不是键的数量来选择分裂点。

删除、重新分配与合并

删除比插入更复杂,因为移除一个键可能使节点中的键数低于下限。主要的修复操作有两种:重新分配,即节点通过父节点从兄弟节点获得一个条目;以及合并,即将两个键数都处于下限的兄弟节点与父节点中分隔它们的键合并。这些操作既保持了有序性,又使节点的键数重新满足下限要求。

在经典B树中,只要删除后仍有足够的键,从叶节点删除键就很简单。从内部节点删除键则需要额外一步。如果紧邻该键左侧的子节点至少有 tt 个键,就可以用该键的前驱(即这个子节点的子树中最大的键)替换它,再从下方删除这个前驱。如果右侧子节点至少有 tt 个键,则可以类似地用其中最小的键,也就是后继,来替换。如果相邻的两个子节点都只有 t−1t-1 个键,就可以将它们与分隔键合并为一个包含 2t−12t-1 个键的节点,然后在该节点中继续执行删除。

一种常见的自顶向下算法会加强向下遍历时的条件:在进入非根子节点之前,先确保该子节点至少有 tt 个键。如果要进入的子节点只有 t−1t-1 个键,算法就先从尚有余量的兄弟节点借一个键,或将它与兄弟节点合并。这样,最终执行删除时,就不会在未预先安排修复的情况下使该节点的键数低于下限。相反,自底向上的算法先删除条目,再向根节点回溯,沿途修复下溢。

重新分配需要经过父节点中的分隔键。例如,如果一个键数不足的子节点向其右侧兄弟节点借键,父节点中的分隔键就会移入这个子节点,而兄弟节点中最小的键则替换原来的分隔键。如果这些节点是内部节点,还需要同时移动相应的子节点引用。直接将兄弟节点的键移过来,无法维持父节点所表示的搜索区间。

合并会减少父节点的键数,因此可能导致上一层发生下溢。如果根节点失去最后一个键,并且只剩一个子节点,该子节点就成为新的根节点。树的高度随之减小一层,而所有叶节点仍然处于相同深度。这与插入时创建新根节点的操作相对应。

生产系统并不总是在每次逻辑删除后立即强制满足教科书中的节点占用率规则。有些系统会推迟页面合并、保留删除标记,或在后续维护期间清除过时记录。这些做法可以减少前台操作的工作量,避免在容量阈值附近反复进行分裂与合并,但需要另行论证空间利用率和查找正确性。它们也体现出两种操作的区别:从索引的可见内容中移除条目,以及实际回收曾经存放该条目的存储空间。

B+树、B*树及相关结构

B+树将路由信息与数据条目分开存储。内部节点包含分隔键和子节点引用,叶节点则包含记录或指向记录的引用。因此,即使在内部节点中遇到了相等的分隔键,一次成功的查找仍需继续到叶节点。分隔键可以与叶节点中的键相同,也可以是经过缩短、但仍能正确区分相邻键值范围的表示。由于内部节点不存储完整记录,这种设计通常能使内部节点具有更高的分支因子。

B+树的叶节点通常按键值顺序链接起来。范围查找一旦到达第一个匹配的叶节点,就可以沿着相邻叶节点继续扫描,而无须反复返回根节点。叶节点分裂时,通常会将一个分隔键复制到父节点,而数据条目仍保留在叶节点层。这与经典B树的分裂方式不同,后者会将中间条目从子节点移到父节点。B+树的内部节点分裂遵循其自身的分隔键处理规则,因此,“向上复制”并不能完整描述所有分裂操作。

B*树着重提高空间利用率。在分裂一个已满节点之前,它会尝试与兄弟节点重新分配条目。当两个相邻节点无法容纳新插入的条目时,其典型操作是将这两个节点的全部内容分配到三个节点中。除根节点的特殊情况和容量取整细节外,这使最低占用率可达到约三分之二,而不是二分之一。额外的兄弟节点交互增加了更新操作的复杂性,但能减少闲置空间,提高有效扇出。

在内存应用中,B树的思想也体现在紧凑的有序容器和注重缓存效率的搜索结构中。多个键共享一次内存分配所得的空间或同一内存区域,与每个键独占一个节点的二叉树相比,减少了指针开销。这种优势取决于工作负载:在节点内部移动条目的成本可能很高,而且除非实现提供更强的保证,否则插入操作可能导致引用或迭代器失效。

最小度数为二的B树与红黑树之间存在一种有用的联系。从概念上看,将某些通过红色链接连接的节点与其黑色父节点合并,就会得到类似于2–3–4树的多键节点。这种联系有助于解释局部的二叉树旋转和重新着色如何实现多路平衡。但这并不意味着两种表示在存储层面可以互换:它们的内存布局和块访问行为有很大差异。

有些名称相近的结构追求的目标却不同。B-link树增加了兄弟节点导航和边界信息,以支持并发的结构变更。缓冲搜索树先积累更新,再将其向较低层推送,通过批处理来减少即时维护的工作量。评估这些变体时,必须依据它们实际维持的不变量和性能模型,而不能将它们视为经典B树的相同实现。

页面布局、键的表示与存储行为

面向存储的B树节点通常占用一个页面,即由存储引擎或操作系统管理的固定大小单元。常见的数据库页面大小以千字节计,但不存在普遍适用的最佳大小。较大的页面可以容纳更多条目,提高分支因子,但在查询少量数据时可能传输不必要的数据,也可能增加更新开销。较小的页面能减少单次传输的数据量,却可能增加树的高度和元数据开销。

假设一个页面有 PP 字节,页头占用 HH 字节,每个键占用 KK 字节,每个子节点引用占用 CC 字节,那么一个具有 mm 个子节点的内部节点所需空间大致满足

H+(m−1)K+mC≤P.H+(m-1)K+mC\leq P.

这个简化公式没有考虑内存对齐、每个条目的元数据以及变长存储。尽管如此,它仍说明了为什么较短的分隔键和紧凑的引用会显著影响树的高度。叶节点的容量必须单独计算,因为叶节点条目可能包含载荷、记录标识符或内部节点中没有的其他信息。

变长键使空间占用情况更加复杂。一个只含少量长键的节点,可能比包含许多短键的节点占用更多空间。因此,系统通常会跟踪空闲字节数,而不只是键的数量,并采用槽式页面布局:用一个紧凑的目录定位条目,而条目编码后的内容则存放在同一页面内的其他位置。较大的值可以存储在树页面之外,页面内仅保留一个前缀或外部引用。这类设计可以避免少数大记录决定所有节点的容量。

键的编码必须保持预期的比较语义。整数的字节序、有符号数的表示方式、字符串排序规则、空值,以及升序和降序字段的混合使用,都会影响树中的查找路径。复合键通常按字典序排列:第一个不同的分量决定先后顺序。前缀压缩可以减少重复的前导字节,而分隔键截断可以缩短内部节点中的键,无须存储它们在叶节点中的完整表示。压缩可以节省空间,但也可能增加解码工作量,或使更新更加复杂。

数据库管理系统的缓冲池会将经常使用的页面保留在内存中。根页面和上层页面会被许多次查找反复使用,因此尤其容易保持在缓存中。这些上层页面常驻内存后,物理读取往往主要来自叶节点访问。在固态存储上,随机读取的开销低于旋转磁盘,但页面传输、设备延迟和写入仍是重要因素。

构建方法也会影响布局。批量加载以已排序的数据为输入,将叶页面填充至选定的目标占用率,再根据叶页面的分隔键构建上层父节点。这样可以避免逐条插入所造成的反复查找和分裂。将填充因子设为低于满容量的值,可以为后续更新预留空间,不过其效果取决于新键插入的位置。顺序递增的键会使插入集中在树的最右端,而分布广泛的键则会消耗整棵树各处的空闲空间。

并发访问与崩溃恢复

多个执行线程共享一棵B树时,即使节点正在发生变化,树也必须保持可搜索。并发插入可能会分裂某个页面,而另一个操作刚刚选中该页面作为下一步要访问的子节点。删除操作可能会断开页面之间的链接,或修改分隔键,而此时某个读取操作仍在沿旧路径访问。因此,要保证正确性,不仅需要规定树在稳定状态下应满足的规则,还需要规定中间状态的规则,以及读取操作可能仍在引用的页面的生命周期。

实现中通常会区分闩锁与事务锁。闩锁用于在检查或修改内存中的页面或数据结构时,提供短暂的保护。事务锁则依据系统的隔离规则,保护逻辑数据库对象或键范围,其持有时间可能长得多。这种区分是概念上的,术语使用并不统一:有些软件库会将两者都称为“锁”。若在整个事务期间一直持有保护树结构的闩锁,就会不必要地限制并发性,还可能产生难以处理的死锁模式。

一种方法是闩锁耦合:操作先对一个子节点加上保护,再解除对其父节点的保护。当更新算法确定选中的子节点有足够的剩余容量,或有足够的可删除余量,能够完成相应修改而不必向上传播时,就可以释放祖先节点上的闩锁。乐观方案则读取版本信息,并在并发修改导致当前遍历失效时重新开始。其性能取决于争用程度、重试频率以及获取保护的开销。

B-link树提供了另一种策略。每个页面都包含一个高键边界,以及指向右侧相邻页面的链接。如果搜索到达的页面所覆盖的范围已不再包含目标键,就可以向右移动。这样,在分裂过程中,即使父节点中的分隔键尚未全部设置完毕,新建的兄弟页面也已经可以被访问。最初的B-link方法由菲利普·莱曼和姚士炳于1981年提出。它的核心贡献在于,即使树结构暂时尚未更新完整,搜索仍能沿有效路径继续进行,而不必要求每次搜索都看到完全更新后的父节点层次结构。

持久化还带来了另一个问题:部分修改过的页面已经写入存储,而其他页面尚未写入时,机器可能发生故障。预写日志会在相应的已修改数据页面持久化之前,先记录恢复信息。随后,恢复协议可以重做必要的修改,并在设计要求时撤销未完成的事务操作。页面分裂必须作为一种可恢复的结构操作来处理;否则,更新中断可能导致已分配的页面无法访问,或使父节点指向无效页面。

写时复制设计提供了另一条途径。这类设计会单独构建修改后的页面,只有在所需页面都准备就绪后,才会发布新的根节点或其他持久化引用。在可以安全回收旧版本之前,读取操作仍可继续访问它们。多版本并发控制则进一步决定一个事务能够看到哪些记录版本。结构完整性、崩溃后的持久性和事务隔离是相互关联的要求,但满足其中一项,并不意味着其他要求也自然得到满足。

起源、应用及与其他方案的比较

鲁道夫·拜尔和爱德华·M. 麦克雷特在波音公司工作期间提出了B树。他们的论文《大型有序索引的组织与维护》于1970年发表于会议论文集,随后于1972年发表于《Acta Informatica》期刊。论文的核心问题是如何在外部存储上维护大型有序索引,同时支持检索和更新。这一设计将平衡的搜索深度与按存储块大小设计的节点相结合,解决了计算速度快而存储访问代价高这一实际矛盾。

后续研究发展出了各种变体、实现技术和分析方法,而非形成一种通用的统一格式。道格拉斯·科默1979年的文章《无处不在的B树》综述了这一结构及其相关变体。随着数据库和文件系统文献开始将许多具有B+树特征的实现也称为“B树”,这一术语的含义逐渐扩大。因此,从工程角度描述一种实现时,必须明确记录存储在哪里、分隔键如何工作,以及维持哪些节点占用率规则。

在关系数据库中,B树家族的索引支持等值谓词、有序比较、范围选择,以及按索引顺序检索。建立在 (a,b)(a,b) 上的复合索引先按 aa 排序,再在 aa 值相同的条目中按 bb 排序。因此,它天然适用于对 aa 施加约束的谓词,也适用于在 aa 值固定时对 bb 进行范围查询。仅针对 bb 的谓词通常无法确定一个连续区间,不过优化器仍可能采用扫描或专门的访问技术。实际收益还取决于选择性,以及是否需要额外读取表的数据页。

具体实现体现了这一家族的灵活性。Oracle 数据库将B树索引作为一种主要索引类型。MySQL的InnoDB引擎围绕聚簇B+树索引组织表数据,其二级索引则包含用于定位聚簇记录的主键值。SQLite使用B树结构存储表和索引内容,不同树类型的页格式和载荷存放位置各不相同。这些设计都支持平衡的有序查找,但记录布局并不相同。

B树也面临着针对不同工作负载优化的其他数据结构的竞争。哈希表可以提供期望常数时间的等值查找,但本身并不保持有序,因而无法直接支持范围查询。平衡二叉树的操作具有对数时间复杂度,单个节点也更小,通常适合那些更看重细粒度内存分配或对象地址稳定性、而非块访问效率的工作负载。日志结构合并树通过累积并合并有序数据,有可能借助批处理减少随机更新访问,但也带来了压实开销,并使查找需要检查多个位置。

B树在文件系统中的用途同样多样:B树家族的结构可用于为目录项、文件区段、分配记录或其他元数据建立索引。在这些场景中,键的设计、恢复协议以及与缓存的交互,可能与抽象的渐近复杂度界限同样重要。因此,恰当的比较不能仅仅是“对数时间与常数时间”的比较,而应考察特定工作负载下读取、写入、空间、同步和恢复的总成本。