B树与B+树

数据库索引的基石

核心主题： B树（B-Tree）与B+树（B+Tree）的原理、操作与工程应用

主要内容： B树的定义与性质、搜索/插入/删除操作、B+树的结构设计、B树与B+树对比、磁盘IO优化原理、数据库索引应用

关键词： B树, B+树, 数据库索引, 多路搜索树, 磁盘IO, InnoDB, 范围查询

一、引言

在计算机科学中，B树（B-Tree）与B+树（B+Tree）是最重要的多路平衡搜索树数据结构之一。它们被广泛用作数据库系统和文件系统的索引结构，特别是MySQL的InnoDB存储引擎就使用B+树作为其默认的索引实现。

为什么数据库系统不直接使用二叉搜索树（BST）或红黑树（Red-Black Tree）来构建索引？答案在于磁盘IO的性能瓶颈。数据库索引通常存储在外存（磁盘）上，而磁盘IO的读写速度比内存访问慢几个数量级。B树通过多路分支的设计，极大地降低了树的高度，从而在查找过程中显著减少了磁盘IO次数。

本笔记将从B树的基本定义出发，逐步深入到B+树的工程实现细节，并通过丰富的代码示例和对比分析，帮助读者全面理解这两种核心数据结构。

前置知识要求：

了解二叉搜索树（BST）的基本操作
熟悉时间复杂度的分析方法（O记号）
对磁盘存储和内存访问的基本概念有一定认识

二、B树的基本概念

2.1 B树的定义

B树是一种多路平衡搜索树，由Rudolf Bayer和Edward M. McCreight于1970年在波音公司（Boeing）工作时提出。关于B树名称的由来，有说法认为B代表"Boeing"，也有说法认为B代表"Balanced"（平衡）或"Bayer"（发明者之一）。

B树的严格定义

一棵m阶B树（m为大于2的正整数）满足以下性质：

每个节点最多包含 m-1 个关键字，即每个节点最多有 m 个子树
根节点至少包含 1 个关键字（除非树为空）
非根非叶节点至少包含 ⌈m/2⌉ - 1 个关键字
每个节点中的关键字按非递减顺序排列
每个关键字的左侧子树中的所有关键字均小于它，右侧子树中的所有关键字均大于它
所有叶子节点位于同一层（平衡性保证）

2.2 B树的阶数与分支因子

阶数（Order）m是衡量B树"宽度"的关键参数。一个m阶B树的节点最多包含m个指针（分支），因此称为多路搜索树。阶数越高，每个节点能容纳的关键字越多，树就越矮胖，查找所需的磁盘IO次数就越少。

阶数与数据量的关系

一棵m阶B树，高度为h，关键字总数为N，满足以下关系：

最小高度：h ≥ ⌈logₘ(N+1)⌉
最大高度：h ≤ ⌈log_{⌈m/2⌉}((N+1)/2)⌉

当 m = 500，N = 10⁹（10亿数据）时，树的高度h ≤ ⌈log_{250}((10⁹+1)/2)⌉ ≈ 4。这意味着最多只需要4次磁盘IO就能找到目标数据。

2.3 B树的节点结构

B树的每个节点包含两部分信息：关键字数组和子节点指针数组。下面是一个B树节点的典型结构：

// B树节点的数据结构定义
#define MAX_KEYS 4      // 最多关键字数 = m - 1
#define MIN_KEYS 2      // 最少关键字数 = ⌈m/2⌉ - 1 (非根)
#define ORDER 5         // B树的阶数 = 5

typedef struct BTreeNode {
    int n;                          // 当前节点中关键字数量
    int keys[MAX_KEYS];             // 关键字数组
    struct BTreeNode* children[ORDER]; // 子节点指针数组 (最多ORDER个)
    bool is_leaf;                   // 是否为叶子节点
} BTreeNode;

对于一个阶数为5（m=5）的B树：

每个节点最多包含 4 个关键字
每个节点最多有 5 个子树
非根非叶节点至少包含 2 个关键字（⌈5/2⌉ - 1 = 2）
非根非叶节点至少有 3 个子树

典型的5阶B树节点结构示意

[ 子1 | key1 | 子2 | key2 | 子3 | key3 | 子4 | key4 | 子5 ]

三、B树的搜索操作

B树的搜索操作与二叉搜索树类似，但需要在每个节点内的多个关键字中进行顺序查找或二分查找，以确定下一步进入哪个子树。

搜索算法步骤

从根节点开始
在当前节点中查找目标关键字：如果找到，返回该关键字的位置
如果当前节点是叶子节点且未找到，则关键字不存在
否则，根据查找结果确定下一个子节点，递归搜索

// B树搜索操作的C语言实现
// 时间复杂度：O(logₘN)，其中m为阶数，N为关键字总数

BTreeNode* btree_search(BTreeNode* root, int target) {
    int i = 0;

    // 在当前节点中查找第一个大于等于target的关键字位置
    while (i < root->n && target > root->keys[i]) {
        i++;
    }

    // 如果找到了目标关键字
    if (i < root->n && target == root->keys[i]) {
        return root;  // 返回包含目标关键字的节点
    }

    // 如果当前节点是叶子节点，说明关键字不存在
    if (root->is_leaf) {
        return NULL;
    }

    // 递归进入第i个子节点继续搜索
    return btree_search(root->children[i], target);
}

搜索性能分析

B树搜索的时间复杂度为 O(h * log m)，其中h是树高，m是阶数。每个节点内的二分查找时间为O(log m)，树高约为O(logₘN)。如果考虑磁盘IO，每次访问一个节点需要一次IO，因此磁盘IO次数等于树的高度。当m足够大时，树高非常小，搜索效率极高。

四、B树的插入操作

B树的插入操作比二叉搜索树复杂得多，因为插入后必须维持B树的所有性质（关键字数量范围、所有叶子在同一层等）。核心思想是：先查找到插入位置，如果节点未满则直接插入；如果节点已满，则执行分裂（Split）操作。

插入算法流程

使用搜索算法找到关键字应该插入的叶子节点
如果叶子节点未满（关键字数量 < m-1），直接插入并保持有序
如果叶子节点已满（关键字数量 = m-1）：
- 将节点分裂为两个节点：左节点包含前⌈(m-1)/2⌉个关键字，右节点包含后⌊(m-1)/2⌋个关键字
- 将中间关键字提升到父节点
- 如果父节点也满了，递归向上分裂，直到根节点
如果根节点也满了，创建新的根节点，树的高度增加1

// B树插入操作的核心实现
// 插入关键字key到以root为根的B树中

BTreeNode* btree_insert(BTreeNode* root, int key) {
    // 如果根节点已满，先创建新根再进行插入
    if (root->n == MAX_KEYS) {
        BTreeNode* new_root = create_node(0);  // 0表示非叶子
        new_root->children[0] = root;
        split_child(new_root, 0);  // 分裂子节点

        // 在分裂后的新根中插入关键字
        if (key < new_root->keys[0]) {
            insert_nonfull(new_root->children[0], key);
        } else {
            insert_nonfull(new_root->children[1], key);
        }

        return new_root;
    }

    // 根节点未满，直接插入
    insert_nonfull(root, key);
    return root;
}

// 将第i个子节点分裂为两个节点
void split_child(BTreeNode* parent, int i) {
    BTreeNode* child = parent->children[i];
    BTreeNode* new_child = create_node(child->is_leaf);

    new_child->n = MIN_KEYS - 1;  // 新节点获得最小关键字数量

    // 将child的后半部分关键字复制到new_child
    for (int j = 0; j < MIN_KEYS - 1; j++) {
        new_child->keys[j] = child->keys[j + MIN_KEYS];
    }

    // 如果非叶子，复制子节点指针
    if (!child->is_leaf) {
        for (int j = 0; j < MIN_KEYS; j++) {
            new_child->children[j] = child->children[j + MIN_KEYS];
        }
    }

    child->n = MIN_KEYS - 1;  // 更新原节点关键字数

    // 在父节点中为新子节点腾出位置
    for (int j = parent->n; j > i; j--) {
        parent->children[j + 1] = parent->children[j];
    }
    parent->children[i + 1] = new_child;

    // 将中间关键字提升到父节点
    for (int j = parent->n; j > i; j--) {
        parent->keys[j] = parent->keys[j - 1];
    }
    parent->keys[i] = child->keys[MIN_KEYS - 1];
    parent->n++;
}

插入操作的触发条件

插入操作中，分裂自底向上传播。当叶子节点分裂时，父节点获得一个新增的关键字。如果父节点因此也满了，就会继续分裂，直到根节点。根节点分裂时树的高度加1，这是B树高度增长的唯一方式。这种设计保证了所有叶子节点始终在同一层，是B树平衡性的核心保证。

五、B树的删除操作

B树的删除操作是最复杂的，因为删除后节点中的关键字数量可能低于最小值（⌈m/2⌉ - 1）。在这种情况下，需要进行借位（Borrow）或合并（Merge）操作来恢复B树的性质。

删除算法的三种情况

情况一：删除叶节点中的关键字

如果删除后节点关键字数量仍≥最小值，直接删除即可。

如果删除后低于最小值，需要从兄弟节点借一个关键字（通过父节点旋转），或与兄弟节点合并。

情况二：删除内部节点中的关键字

不直接删除内部节点的关键字，而是找到该关键字的前驱（左子树中最大值）或后继（右子树中最小值）来替换它，然后删除叶子节点中的前驱/后继。

情况三：借位与合并

当节点关键字不足时：

借位：从左兄弟或右兄弟借一个关键字。父节点的关键字下移到当前节点，兄弟节点的关键字上移到父节点
合并：如果两个兄弟都无法借出，则与其中一个兄弟及父节点中分隔它们的关键字合并为一个节点

// B树删除操作的辅助函数：从非满节点中删除关键字
// 假设当前节点不是满的（保证递归过程中不会出现下溢）

void btree_delete_nonfull(BTreeNode* node, int key) {
    int i = 0;
    while (i < node->n && key > node->keys[i]) {
        i++;
    }

    // 情况1：在当前节点中找到了目标关键字
    if (i < node->n && key == node->keys[i]) {
        if (node->is_leaf) {
            // 叶子节点：直接删除
            for (int j = i; j < node->n - 1; j++) {
                node->keys[j] = node->keys[j + 1];
            }
            node->n--;
        } else {
            // 内部节点：用前驱或后继替换后删除
            BTreeNode* pred = node->children[i];
            while (!pred->is_leaf) {
                pred = pred->children[pred->n];
            }
            node->keys[i] = pred->keys[pred->n - 1];
            btree_delete_nonfull(node->children[i], pred->keys[pred->n - 1]);
        }
        return;
    }

    // 情况2：关键字不在当前节点，需要进入子节点递归删除
    if (node->is_leaf) {
        return;  // 关键字不存在
    }

    // 进入子节点之前确保它有足够的关键字（≥最小值）
    if (node->children[i]->n == MIN_KEYS - 1) {
        fill_child(node, i);  // 借位或合并操作
    }

    // 递归在适当的子节点中删除
    if (i > node->n || key > node->keys[i-1]) {
        btree_delete_nonfull(node->children[i], key);
    } else {
        btree_delete_nonfull(node->children[i-1], key);
    }
}

// 从兄弟节点借一个关键字或与兄弟节点合并
void fill_child(BTreeNode* parent, int i) {
    // 优先从左兄弟借（如果存在且有多余关键字）
    if (i > 0 && parent->children[i-1]->n > MIN_KEYS - 1) {
        borrow_from_left(parent, i);
    }
    // 否则尝试从右兄弟借
    else if (i < parent->n && parent->children[i+1]->n > MIN_KEYS - 1) {
        borrow_from_right(parent, i);
    }
    // 两个兄弟都无法借出，执行合并
    else {
        if (i < parent->n) {
            merge_children(parent, i);  // 与右兄弟合并
        } else {
            merge_children(parent, i - 1);  // 与左兄弟合并
        }
    }
}

六、B+树的结构设计

B+树是B树的一种变体，在数据库系统中被广泛使用。它的核心设计理念是：所有数据都存储在叶子节点中，内部节点只存储索引（关键字）。

6.1 B+树的核心特性

B+树 vs B树的关键区别

内部节点只存索引：内部节点只存储关键字（用于路由查找方向），不存储实际数据
所有数据在叶子节点：所有实际数据记录都存储在叶子节点中
叶子节点形成链表：所有叶子节点通过指针连接成一个有序链表，便于范围查询
叶子节点包含全部关键字：所有关键字都会出现在叶子节点中

6.2 内部节点的作用

在B+树中，内部节点的作用类似于一个路标系统，只指引搜索方向，不携带实际数据。这使得内部节点可以容纳更多关键字，从而进一步降低树高。

由于内部节点不存储数据，同样大小的内存（如4KB页面）可以存储更多的索引项。假设每个索引项占用8字节（4字节关键字 + 4字节指针），一个4KB页面可存储约512个索引项。这意味着一个高度为3的B+树可以索引 512 × 512 × 512 ≈ 1.34亿条记录。

6.3 叶子节点的结构

B+树的叶子节点不仅存储关键字，还存储指向实际数据记录的数据指针（或直接存储数据行本身，在聚簇索引中）。

// B+树节点的数据结构定义

// B+树内部节点（只存索引，不存数据）
typedef struct {
    int n;                              // 当前关键字数
    int keys[MAX_KEYS];                 // 关键字数组（只用于路由）
    struct BPlusNode* children[ORDER];  // 子节点指针
    bool is_leaf;                      // 固定为false
} BPlusInternalNode;

// B+树叶子节点（存储实际数据）
typedef struct {
    int n;                              // 当前关键字数
    int keys[MAX_KEYS];                 // 关键字数组
    RecordPtr data[MAX_KEYS];           // 指向实际数据记录的指针
    struct BPlusLeafNode* next;         // 指向下一个叶子节点（链表）
    bool is_leaf;                      // 固定为true
} BPlusLeafNode;

B+树的三个关键优势

更高的扇出（fan-out）：内部节点不存数据，能容纳更多索引项，树更矮，IO更少
稳定的查询效率：所有查询必须到达叶子节点才能获取数据，每次查询的IO次数完全相同（等于树高）
高效的范围查询：通过叶子节点的链表结构，只需找到下界后顺序遍历即可，无需频繁回溯父节点

七、B+树的搜索与范围查询

7.1 精确查找

B+树的精确查找流程：从根节点开始，在每个内部节点中通过二分查找确定下一步方向，最终到达叶子节点获取数据。所有查找都必须到达叶子节点。

// B+树精确查找算法
// 返回指向数据记录的指针，未找到返回NULL

RecordPtr bplus_search(BPlusNode* root, int key) {
    BPlusNode* cur = root;

    // 自顶向下搜索，直到叶子节点
    while (!cur->is_leaf) {
        int i = 0;
        while (i < cur->internal.n && key >= cur->internal.keys[i]) {
            i++;
        }
        cur = cur->internal.children[i];
    }

    // 在叶子节点中查找目标关键字
    for (int i = 0; i < cur->leaf.n; i++) {
        if (cur->leaf.keys[i] == key) {
            return cur->leaf.data[i];  // 找到，返回数据指针
        }
    }

    return NULL;  // 未找到
}

7.2 范围查询（B+树的核心优势）

范围查询（如 WHERE age BETWEEN 20 AND 30）是数据库中最常見的查询类型之一。B+树的叶子节点链表结构使范围查询效率极高。

// B+树范围查询算法
// 查询所有关键字在 [lower, upper] 范围内的记录

void bplus_range_query(BPlusNode* root, int lower, int upper) {
    BPlusNode* cur = root;

    // 第一步：找到下界所在的叶子节点
    while (!cur->is_leaf) {
        int i = 0;
        while (i < cur->internal.n && lower >= cur->internal.keys[i]) {
            i++;
        }
        cur = cur->internal.children[i];
    }

    // 在叶子节点中找到第一个 >= lower 的关键字
    int start_pos = 0;
    while (start_pos < cur->leaf.n && cur->leaf.keys[start_pos] < lower) {
        start_pos++;
    }

    // 第二步：通过叶子节点的链表顺序遍历，直到超过上界
    bool done = false;
    while (cur != NULL && !done) {
        for (int i = start_pos; i < cur->leaf.n; i++) {
            if (cur->leaf.keys[i] > upper) {
                done = true;
                break;
            }
            // 输出或处理当前记录
            process_record(cur->leaf.keys[i], cur->leaf.data[i]);
        }
        cur = cur->leaf.next;   // 移动到下一个叶子节点
        start_pos = 0;          // 从新叶子节点的第一个关键字开始
    }
}

范围查询性能对比

B树的范围查询：需要中序遍历，频繁在父子节点之间回溯。每访问一个节点都需要一次磁盘IO，且回溯会增加额外的IO开销。

B+树的范围查询：找到下界后，只需沿着叶子节点链表顺序遍历。叶子节点在磁盘上通常是物理连续或预读友好的，一次IO可以读取整页数据。对于范围查询，B+树的性能远优于B树。

八、B树 vs B+树全面对比

对比维度	B树	B+树
数据存储位置	内部节点和叶子节点都存数据	仅在叶子节点存数据，内部节点只存索引
叶子节点结构	无链表连接	叶子节点通过链表连接，形成有序链表
单条查询效率	可能在内部节点就找到数据，平均略快	必须到达叶子节点，查询时间稳定
范围查询效率	需要中序遍历，递归回溯父节点，效率较低	叶子链表顺序遍历，效率极高
树的高度	相对较高（节点占用空间大）	更矮（内部节点只存索引，扇出更大）
磁盘IO次数	取决于数据是否在内部节点命中	稳定 = 树高（每次查询IO相同）
插入/删除	复杂，可能涉及内部节点数据调整	数据变化只影响叶子节点
空间利用率	内部节点也存数据，空间利用率较低	内部节点存更多索引，空间效率更高
适用场景	文件系统、需要快速随机访问	数据库索引、范围查询密集场景

为什么数据库系统偏爱B+树？

数据库系统中，范围查询和排序操作非常频繁。例如：SELECT * FROM users WHERE age > 25 ORDER BY age。B+树的叶子链表结构使得这类操作不需要像B树那样频繁回溯，显著减少了磁盘IO。此外，B+树内部节点可容纳更多索引项，树更矮，对磁盘IO的优化更彻底。

九、B+树在数据库索引中的应用

9.1 MySQL InnoDB 中的B+树索引

MySQL的InnoDB存储引擎使用B+树作为索引结构的核心实现。InnoDB有两种类型的索引：聚簇索引（Clustered Index）和二级索引（Secondary Index），两者都是B+树结构。

聚簇索引（主键索引）

InnoDB的聚簇索引是表的主键索引，它决定了表中数据的物理存储顺序。在聚簇索引的B+树中：

内部节点：存储主键关键字和子节点指针
叶子节点：直接存储完整的数据行（所有列）

由于叶子节点直接存数据行，通过主键的精确查找非常高效。这也意味着一个表只能有一个聚簇索引。

二级索引（辅助索引）

除主键索引外的其他索引称为二级索引：

内部节点：存储索引列的值和子节点指针
叶子节点：存储索引列的值 + 主键值（不是完整数据行）

通过二级索引查找数据时，需要两次B+树搜索：先在二级索引B+树中找到主键值，再通过主键值在聚簇索引B+树中找到完整数据行。这个过程称为回表。

-- MySQL InnoDB索引示例
-- 创建一个用户表，观察InnoDB的索引结构

CREATE TABLE users (
    id INT PRIMARY KEY AUTO_INCREMENT,  -- 聚簇索引
    name VARCHAR(50) NOT NULL,
    age INT NOT NULL,
    email VARCHAR(100),
    city VARCHAR(50),
    INDEX idx_age (age),           -- 二级索引B+树
    INDEX idx_city (city)          -- 二级索引B+树
) ENGINE=InnoDB;

-- 精确查找（使用主键）：一次B+树搜索即可获取完整数据行
SELECT * FROM users WHERE id = 100;

-- 范围查询（使用主键）：B+树叶子链表高效遍历
SELECT * FROM users WHERE id BETWEEN 100 AND 200;

-- 范围查询（使用二级索引）：需先查二级索引，再回表
SELECT * FROM users WHERE age BETWEEN 20 AND 30;
-- 执行流程：
-- 1. 在idx_age的B+树中找到age∈[20,30]的所有主键id
-- 2. 根据主键id在聚簇索引的B+树中回表获取完整数据行

-- 覆盖索引优化：如果查询只需要索引列本身，无需回表
SELECT age, COUNT(*) FROM users WHERE age > 20 GROUP BY age;
-- 只需在idx_age的B+树中扫描叶子节点（覆盖索引），无需回表

9.2 联合索引中的B+树

当MySQL中的索引由多个列组成时（如 INDEX idx_name_age (name, age)），B+树中的关键字也是一个复合键，按照从左到右的顺序进行排序和比较。这就是最左前缀原则的底层实现基础。

-- 联合索引示例：最左前缀原则的底层原理
CREATE INDEX idx_name_age_city ON users(name, age, city);

-- 在B+树中，关键字按(name, age, city)整体排序
-- 先按name排序，name相同按age排序，age相同按city排序

-- 可以使用索引的查询（遵循最左前缀）
WHERE name = '张三';                    -- 使用第一列
WHERE name = '张三' AND age = 25;        -- 使用前两列
WHERE name LIKE '张%';                   -- 前缀匹配，可使用

-- 无法使用索引的查询（跳过最左列）
WHERE age = 25;                          -- 未使用name列，无法使用索引
WHERE city = '上海';                      -- 未使用name和age列

十、B树的磁盘IO优化原理

10.1 局部性原理与预读

计算机系统在设计时利用了局部性原理：当访问一个数据时，其附近的数据很可能在不久的将来被访问到。因此，操作系统和磁盘控制器在读取一个数据页时，会将相邻的多个数据页一同预读到内存中（预读机制）。B树的节点大小通常设计为与磁盘页大小（通常4KB或16KB）对齐，使得一次磁盘IO读取一个完整的B树节点。

磁盘IO与B树设计

磁盘页（Page）是磁盘IO的最小单位，通常为4KB
B树的节点大小与磁盘页对齐，一次IO读取一整个节点
B树的阶数设计使得一个节点能容纳几十到几百个关键字
10亿条记录的数据，B树高度仅为3-4层，即仅需3-4次IO

10.2 红黑树 vs B树：磁盘IO的对比

如果将红黑树用于磁盘索引：红黑树是二叉树，每个节点只存1个关键字。存储10亿条记录需要约30层（2³⁰ ≈ 10亿）。在磁盘上查找一条记录需要30次IO！而B树只需要3-4次。这就是为什么文件系统和数据库系统选择B树/B+树而不是红黑树的核心原因。

性能数据对比（10亿条数据）

数据结构	树高	磁盘IO次数	耗时估计（每次IO 10ms）
红黑树	≈ 30	30	300ms
B树（阶数=500）	3-4	3-4	30-40ms
B+树（阶数=500）	2-3	2-3	20-30ms

注：实际IO时间受SSD/HDD、缓存命中率等因素影响，上表为HDD的典型随机IO时间估计。当前SSD随机IO延迟约为0.1-1ms，差距仍然显著。

10.3 缓存与B树

在现代数据库系统中，B+树的内部节点通常会被缓存在内存中（如InnoDB的Buffer Pool），因为内部节点只占B+树总节点数的一小部分。对于10亿条记录、阶数500的B+树，内部节点总数仅为数百到数千个。而在实际查询中，大多数查找只需要在内存中的内部节点中路由，只有最后一层（叶子节点）可能需要磁盘IO。这使得B+树在工程实践中的性能远超理论值。

十一、红黑树 vs B树的选择

红黑树和B树各有适用场景，选择哪种数据结构取决于具体的应用需求和硬件环境。

红黑树的优势（内存场景）

实现相对简单：红黑树的插入和删除逻辑比B树简单得多
更新代价极低：只需要进行变色和旋转操作，不涉及节点的分裂和合并
内存效率高：当数据全部在内存中时，磁盘IO不再是瓶颈，二叉结构足以胜任
适合高频更新：在频繁插入和删除的场景下，红黑树的维护成本远低于B树

B树的优势（外存场景）

磁盘IO次数少：多路分支大幅降低树高，减少磁盘访问次数
利用预读机制：节点与磁盘页对齐，一次IO读取大量关键字
空间局部性好：一个节点内的关键字在磁盘上连续存储

实战选择指南

应用场景	推荐数据结构	原因
Java TreeMap / C++ std::map	红黑树	数据全在内存，无需考虑磁盘IO
Linux内核进程调度	红黑树	内存操作，需要高效的插入/删除
MySQL InnoDB索引	B+树	数据存储在磁盘，范围查询频繁
MongoDB索引	B树	需要高效的单条随机查询
ext4/XFS文件系统目录索引	B树变体	磁盘上的目录查找需要高效IO
Redis有序集合（zset）	跳表	内存操作，实现更简单，范围查询也高效

十二、B树操作复杂度总结

操作	平均时间复杂度	最坏时间复杂度	磁盘IO次数
搜索	O(logₘN)	O(logₘN)	树高h
插入	O(logₘN)	O(logₘN)	h（查找）+ 分裂传播
删除	O(logₘN)	O(logₘN)	h（查找）+ 合并传播
范围查询（B+树）	O(logₘN + k)	O(logₘN + k)	h + k/页容量
范围查询（B树）	O(logₘN + k)	O(logₘN + k·logₘN)	h + 回溯开销

注：m为B树的阶数，N为关键字总数，k为返回的记录数。

十三、核心要点总结

B树本质：一种多路平衡搜索树，通过控制每个节点的关键字数量范围（⌈m/2⌉-1 到 m-1）和所有叶子在同一层来保证平衡性
阶数决定性能：阶数m决定了B树的"宽度"，m越大，树越矮，磁盘IO越少。实际工程中m通常取值几百到上千
B+树的创新：内部节点只存索引不存数据，叶子节点用链表连接。这带来了三个优势：树更矮、查询时间稳定、范围查询高效
数据库首选B+树：MySQL InnoDB的聚簇索引和二级索引都基于B+树，范围查询时叶子链表极大减少了回溯开销
磁盘IO是核心瓶颈：B树/B+树的节点大小与磁盘页对齐，利用预读机制将随机IO转化为顺序IO，这是设计上最关键的工程考量
红黑树 vs B树：数据全部在内存时选红黑树（实现简单、更新代价低），数据在外存时选B树/B+树（IO次数少）
联合索引本质：复合键按定义列顺序排序，B+树的搜索路径遵循最左前缀原则，这是SQL索引优化的理论基础
覆盖索引优化：当查询只需要索引中的列时，可以直接在B+树内部完成，无需回表，这是数据库性能调优的重要手段

十四、进一步思考

实践应用方向

数据库索引优化：理解B+树的结构，分析慢查询的索引使用情况（EXPLAIN命令），避免回表过多
磁盘IO模拟：尝试实现一个简单的B+树引擎，模拟磁盘页的读取和写入，加深对预读机制的理解
与其他数据结构的组合：研究LSM-Tree（LevelDB/RocksDB使用）与B+树的对比，理解不同写优化策略
分布式数据库中的B树：研究B树在分布式环境中的变体（如B-Link树、并发B树）
内存数据库的索引选择：对比B+树和跳表在内存数据库（如Redis）中的表现差异

面试常见问题

为什么MySQL InnoDB选择B+树而不是B树作为索引结构？
B+树的插入操作中，节点分裂是如何传播的？最坏情况下会造成多少次磁盘IO？
什么是聚簇索引？为什么InnoDB中不建议使用UUID作为主键？
覆盖索引是如何减少磁盘IO的？什么情况下会发生"回表"？
B树中，为什么非根非叶节点的关键字数量下限是⌈m/2⌉ - 1？