算法

B 树 & B+ 树

数据库索引结构——高分支因子使树高保持 O(log_B N)，每个节点恰好占一个磁盘页

B 树

自平衡搜索树，每个节点持有 ceil(t/2) 到 t 个 key（t 阶 B 树）。内部节点同时存储 key 和 data。

核心不变量

  • 非根节点至少有 ceil(t/2) 个 key；根节点至少有 1 个
  • 每个节点最多 t 个 key（内部节点最多 t+1 个子节点）
  • 所有叶节点深度相同
  • 节点内 key 有序；子树 key 满足 BST 性质

插入算法

  1. 找到新 key 应插入的叶节点位置
  2. 将 key 插入叶节点；若叶节点达到 t 个 key（上溢），则分裂
  3. 分裂：中间 key 上提至父节点；左右两半各成一个节点
  4. 分裂可能向上传播至根；若根分裂，树高加 1
// Order-3 B-tree (max 2 keys per node)
struct BNode {
    vector<int> keys;
    vector<BNode*> children;
    bool isLeaf() const { return children.empty(); }
};

class BTree {
    BNode* root = new BNode();
    void splitChild(BNode* parent, int i) {
        BNode* y = parent->children[i];
        BNode* z = new BNode();
        int mid = y->keys[1]; // median for order-3
        z->keys = {y->keys[2]}; // right half keys
        y->keys = {y->keys[0]};  // left half keys
        if (!y->isLeaf()) {
            z->children = {y->children[2], y->children[3]};
            y->children = {y->children[0], y->children[1]};
        }
        parent->keys.insert(parent->keys.begin()+i, mid);
        parent->children.insert(parent->children.begin()+i+1, z);
    }
    void insertNonFull(BNode* x, int k) {
        int i = (int)x->keys.size() - 1;
        if (x->isLeaf()) {
            x->keys.push_back(0);
            while (i >= 0 && k < x->keys[i]) { x->keys[i+1]=x->keys[i]; i--; }
            x->keys[i+1] = k;
        } else {
            while (i >= 0 && k < x->keys[i]) i--;
            i++;
            if ((int)x->children[i]->keys.size() == 2) {
                splitChild(x, i);
                if (k > x->keys[i]) i++;
            }
            insertNonFull(x->children[i], k);
        }
    }
public:
    void insert(int k) {
        if ((int)root->keys.size() == 2) {
            BNode* s = new BNode();
            s->children.push_back(root);
            splitChild(s, 0);
            root = s;
        }
        insertNonFull(root, k);
    }
    bool search(BNode* x, int k) {
        int i = 0;
        while (i < (int)x->keys.size() && k > x->keys[i]) i++;
        if (i < (int)x->keys.size() && k == x->keys[i]) return true;
        if (x->isLeaf()) return false;
        return search(x->children[i], k);
    }
    bool search(int k) { return search(root, k); }
};

应用场景

  • 通用磁盘索引（部分 KV 存储）
  • HFS+ / APFS 目录索引
  • B 树是 B+ 树的泛化：B+ 树添加叶子链表以支持范围扫描

磁盘 I/O：分支因子 B ≈ 页大小 / key 大小 ≈ 100 时，1 亿行数据的 B 树树高 log₁₀₀(1 亿) ≈ 4，每次查询最多 4 次磁盘 I/O。

练习：B 树 — B-Tree Insert & Search — 代码练习
测试用例（2 个）
用例 1
输入：I 10 I 20 I 5 I 15 I 25 S 15 S 30 S 5
期望：found not found found
用例 2
输入：I 3 I 7 I 1 I 5 S 1 S 4 S 7
期望：found not found found

B+ 树

与 B 树类似，但内部节点只存 key（无 data），所有数据存于叶节点。叶节点按序形成链表，支持高效范围扫描。

B+ 树 vs B 树

  • 内部节点仅存 key——相同页大小下分支因子更高
  • 所有数据在叶节点——所有查询的读路径一致
  • 叶节点形成有序双向链表——O(log N) 定位后 O(k) 范围扫描
  • 删除更简单：只需更新叶节点，内部节点无需移除 data

范围查询算法

  1. 从根向下找到 lower_bound(lo) 所在的叶节点
  2. 沿链表向右扫描，直到 key > hi
  3. 收集所有匹配的 key-value 对
// Simplified B+ tree for range queries.
// Stores all keys in a sorted leaf layer linked by next pointers.
// Internal nodes are not fully implemented — uses sorted vector as a stand-in.
struct BPlusLeaf {
    vector<int> keys;
    BPlusLeaf* next = nullptr;
};

class BPlusTree {
    vector<BPlusLeaf*> leaves; // sorted pages
    vector<int> allKeys;       // simplified: all keys sorted
public:
    void insert(int k) {
        allKeys.insert(lower_bound(allKeys.begin(), allKeys.end(), k), k);
    }
    vector<int> rangeQuery(int lo, int hi) {
        vector<int> res;
        auto it = lower_bound(allKeys.begin(), allKeys.end(), lo);
        while (it != allKeys.end() && *it <= hi) res.push_back(*it++);
        return res;
    }
};

应用场景

  • MySQL InnoDB——主键为聚簇 B+ 树，二级索引为独立 B+ 树
  • PostgreSQL heap + B 树索引文件
  • SQLite——表行与索引共用 B 树页
  • Oracle、SQL Server 等主流关系型数据库

聚簇索引 vs 二级索引：聚簇索引在叶节点存储行数据；二级索引在叶节点存储（索引键，主键）。通过二级索引查找需额外一次 I/O 取行数据（回表）。

练习：B 树 — B+ Tree Range Query — 代码练习
测试用例（3 个）
用例 1
输入：7 5 3 8 1 7 12 4 3 8
期望：3 4 5 7 8
用例 2
输入：5 10 20 30 40 50 15 35
期望：20 30
用例 3
输入：3 1 2 3 5 10
期望：empty