数据库系统内幕

B

树基础知识

｜

39

2.3.3 B

树查找复杂度

可以从两个角度来讨论 B 树查找的复杂度：块传输的数量和查找期间完成的比较的次数。

就传输次数而言，对数基为 N（每个节点的键数）。从根节点每往下走一层，节点个数就

多 K 倍，并且跟随一个子指针可以将搜索空间减少至 N 分之一。在查找期间，最多寻址

log

K

M（其 中 M 是 B 树中的项的总数）个页来查找一个搜索键。在从根到叶的通路上必

须经过的子指针的数量也等于层数，换句话说，其等于树的高度 h。

从比较次数的角度来看，对数基是 2，因为在每个节点内搜索一个键是使用二分搜索完

成的。每次比较都将搜索空间减半，因此复杂度为 log

2

M。

了解寻道次数和比较次数之间的区别有助于我们从这两个角度直观地认识搜索是如何执

行的，并理解其有着怎样的查找复杂度。

在一些书籍和文章

注 2

中，B 树的查找复杂度一般记为 logM。在复杂度分析中通常不使

用对数基，因为改变基只是增加一个常数因子，而乘以常数因子并不改变复杂度。例

如，给定非零常数因子 c，O(|c| × n) == O(n)[KNUTH97]。

2.3.4 B

树查找算法

既然我们已经介绍了 B 树的结构和内部组织，我们就可以定义查找、插入和删除的算法

了。要在 B 树中找到一个项，我们必须执行从根节点到叶节点的单向遍历。这种搜索的

目的是查找被搜索的键或其前驱。查找精确匹配用于单点查询、更新和删除；查找其前

驱则对于范围扫描和插入非常有用。

该算法从根节点上开始执行二分搜索算法，将要搜索的键与存储在根节点中的键进行比 ...