B-Tree and B+Tree Search

Definition & structure

B-Tree: multiway balanced search tree used in DBs and filesystems.
B+Tree: variant where all keys live in leaves (linked), great for range scans.

B树/B+树查找演示

此处可扩展为B树/B+树结构和查找过程的可视化。

• 多路平衡树结构
• 节点分裂与合并
• 范围查找演示

B-Tree traits

• Up to $m$ children per node (order $m$)
• Root has at least 2 children (unless single-node tree)
• Non-root nodes have $\lceil m/2 \rceil$ or more children
• Keys in-node are ascending; subtrees are ordered intervals

B+Tree traits

• All keys in leaves, leaves linked
• Internal nodes store only indexes
• Optimized for range queries

Search process

1. From root, sequentially search keys in node
2. If found, success
3. Else follow child pointer
4. Repeat until leaf or success

B+Tree search similar, but always ends at leaves.

When to use

• Large on-disk data; DB indexes
• Heavy range queries (B+Tree)

Algorithm (pseudo)

node = root
while node != null:
    顺序查node内关键字找x
    if found:
        return position
    else:
        follow child pointer
return -1

Complexity

• Search: $O(\log_m n)$ where $m$ is order, $n$ keys
• B+Tree similar, better for range scan

Exercises

Exercise 1

Differences between B-Tree and B+Tree? Scenarios?

参考答案

思路：结构与适用对比。

步骤：

1. B-Tree keys across all nodes；B+Tree keys only in leaves
2. B+Tree leaves linked—range-friendly

答案：B-Tree通用查找；B+Tree擅长范围查找。

Exercise 2

In a 4-way B-Tree, min children of non-root?

参考答案

思路：阶数与子女数。

步骤：

1. 非根至少 $\lceil m/2 \rceil$
2. $m=4$，故 2

答案：2 个子女。

Past exam

2019·408

关于 B 树的说法哪项错误？

参考答案

思路：逐项核对性质。

步骤：

1. (A) 正确；(B) 正确
2. (C) 错误：根可只有 1 子女（特殊）
3. (D) 条件不足，无法定高度

答案：(C) 错误。根可 1 子女。

PreviousHash Table SearchHash-table searching: hash functions, collision handling, complexity, and practice. NextString Pattern MatchingString matching basics, classic algorithms, complexity, and practice.