Guide

Appearance

B 树与 B+ 树：数据库索引核心 ​

为什么数据库不用二叉树做索引？ ​

你的表有 1000 万条数据，主键是自增整数。

如果用二叉树做索引，树的高度大约是 log₂(10⁷) ≈ 24。这意味着查找最多需要 24 次磁盘 IO。

但如果用 M 叉树（每个节点有 M 个分叉）呢？

假设 M = 100，树的高度变成了 log₁₀₀(10⁷) ≈ 3.5。查找最多只需要 3-4 次磁盘 IO。

这就是数据库选择 B 树系的原因——让树更「矮胖」，减少磁盘 IO。

B 树：多路平衡查找树 ​

B 树的定义 ​

一棵 m 阶的 B 树满足：

  1. 每个节点最多有 m 个子节点
  2. 根节点至少有 2 个子节点（除非是叶子）
  3. 非根非叶节点至少有 m/2 个子节点
  4. 所有叶子节点在同一层（高度相同）
  5. 每个节点包含关键字（用于分叉和查找）
m=3 的 B 树（简化示例）:

        [15 | 30]
       /    |    \
   [5|10] [18|25] [35|40|50]
   /  |  \   |    /   |   \
 叶  叶  叶   叶   叶  叶  叶（叶子节点在同一层）

B 树的节点结构 ​

java
class BTreeNode {
    int n;              // 当前节点关键字数量
    int[] keys;         // 关键字数组（升序）
    BTreeNode[] children; // 孩子指针数组
    boolean isLeaf;     // 是否是叶子节点
    
    // 关键字数量：n+1 个孩子指针
    // 关键字关系：key[i] < keys[i] < key[i+1]
}

B 树的查找 ​

java
public BTreeNode search(BTreeNode node, int key) {
    int i = 0;
    // 找到第一个 >= key 的位置
    while (i < node.n && key > node.keys[i]) {
        i++;
    }
    
    // 找到了
    if (i < node.n && key == node.keys[i]) {
        return node;
    }
    
    // 是叶子节点，没找到
    if (node.isLeaf) {
        return null;
    }
    
    // 递归到子树
    return search(node.children[i], key);
}

查找最多需要访问的节点数 = 树的高度。

B 树的插入 ​

分裂上溢：当节点关键字数 > m-1 时，分裂成两个节点，中间的关键字上升到父节点。

java
public void insertNonFull(BTreeNode node, int key) {
    int i = node.n - 1;
    
    if (node.isLeaf) {
        // 叶子节点：找到合适位置插入
        while (i >= 0 && key < node.keys[i]) {
            node.keys[i + 1] = node.keys[i];
            i--;
        }
        node.keys[i + 1] = key;
        node.n++;
    } else {
        // 内部节点：找到合适的子树
        while (i >= 0 && key < node.keys[i]) {
            i--;
        }
        i++;
        
        if (node.children[i].n == MAX_KEYS) {
            // 子树满了，先分裂
            splitChild(node, i, node.children[i]);
            
            if (key > node.keys[i]) {
                i++;
            }
        }
        insertNonFull(node.children[i], key);
    }
}

B 树的分裂过程 ​

插入 10 导致上溢，分裂过程：

分裂前:                    分裂后:
   [5|15|25|30]            [5|15|25]       [15上升到父节点]
   /  |  |   \             /  |   \       /  |   \
 [子节点...]              [子节点...]  [10][...新的...] [子节点...]
          ↑
        满了(4个关键字，5个指向)

B+ 树：B 树的进化 ​

B+ 树 vs B 树 ​

特性B 树B+ 树
关键字位置叶子+内部仅叶子
叶子节点不连续通过指针串联（链表）
范围查询需要回溯直接遍历链表
查询稳定性可能在叶子或内部结束必须在叶子结束
IO 次数最多树高次最多树高次（但更稳定）

B+ 树的结构 ​

                根节点/内部节点（只存索引）
                    [20 | 40]
                   /    |    \
         [10|15]  [25|35]  [50|60]
         / | \    / | \    / | \
        ↓  ↓  ↓   ↓  ↓  ↓   ↓  ↓
      数据 数据 数据 数据 数据 数据  ← B 树：叶子存数据
      指针 指针 指针 指针 指针 指针  ← B+ 树：叶子存所有数据
        |   |   |   |   |   |      + 链表串联
        ↓___↓___↓___↓___↓___↓
         有序链表（范围查询）

B+ 树的优势 ​

  1. 更好的范围查询：叶子节点用链表串联，范围查询只需遍历链表
  2. 查询更稳定：所有查询都要到叶子节点，IO 次数固定
  3. 更高的扇出：内部节点只存索引，可以有更多分叉，树更矮
  4. 更适合磁盘存储：每次 IO 读取一页（通常 16KB），内部节点可以容纳更多索引

MySQL InnoDB 索引的实现 ​

聚集索引（Clustered Index） ​

InnoDB 表数据按主键顺序存储，主键索引就是聚集索引——叶子节点存储完整的行数据。

sql
CREATE TABLE users (
    id BIGINT PRIMARY KEY,  -- 主键 → 聚集索引
    name VARCHAR(50),
    age INT
);
-- 数据直接存储在主键索引的叶子节点中

辅助索引（Secondary Index） ​

非主键列上的索引是辅助索引，叶子节点存储的是主键值，而不是行数据。

sql
CREATE INDEX idx_age ON users(age);
-- 辅助索引叶子节点：[age值, 主键id]
-- 查找时：先在辅助索引找到主键，再用主键去聚集索引查找完整数据（回表）

为什么主键建议自增？ ​

自增主键保证了插入的顺序性，新行总是插入到叶子末尾，不需要移动已有数据页。

如果用 UUID 或字符串做主键，新插入的值可能落在数据页中间，导致页分裂和大量 IO。

B+ 树的工程实践 ​

阶数的选择 ​

B+ 树的阶数（每个节点最多有多少个孩子）取决于：

  1. 磁盘页大小：通常 16KB
  2. 主键大小：通常是 8 字节（BIGINT + 指针）
  3. 索引列大小：取决于列类型

计算示例：

  • 假设索引列是 BIGINT（8 字节）
  • 每行需要：8 字节（值）+ 6 字节（指针）= 14 字节
  • 16KB 页可以存储：16 × 1024 / 14 ≈ 1170 个索引项
  • 树高 3 时，可以索引：1170 × 1170 × 1170 ≈ 16 亿行

页分裂与性能 ​

插入顺序: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10...
自增主键 → 始终追加到末尾 → 高效

插入顺序: 10, 8, 3, 15, 1...
随机主键 → 可能需要页分裂 → 低效

索引失效的情况 ​

  1. 函数/计算：在索引列上使用函数会导致索引失效
  2. 类型转换：字符串列用数字查询
  3. 前导模糊查询：LIKE '%abc' 无法使用索引
  4. OR 条件：OR 两边必须都有索引

实战：计算 B+ 树的容量 ​

java
public class BTreeCapacity {
    public static void main(String[] args) {
        // 假设
        long pageSize = 16 * 1024;      // 16KB
        long keySize = 8;               // BIGINT 主键
        long pointerSize = 6;            // 指针
        long entrySize = keySize + pointerSize;
        
        // 每个非叶子节点可存储的索引数
        long maxKeysPerNode = pageSize / entrySize;
        
        // 树容量估算
        long fanout = maxKeysPerNode;  // 阶数
        
        System.out.println("每节点最大关键字数: " + maxKeysPerNode);
        
        // 计算不同高度的容量
        for (int height = 1; height <= 4; height++) {
            long capacity = (long) Math.pow(fanout, height - 1) * fanout * 100; // ×100 估算叶子节点
            System.out.println("高度 " + height + " 约可存储 " + 
                String.format("%,d", capacity) + " 条记录");
        }
    }
}

总结 ​

B 树和 B+ 树是数据库索引的核心，理解它们的关键是理解磁盘 IO 与内存访问的权衡。

核心要点：

  1. B 树：多路平衡树，每个节点可以有多于 2 个的孩子
  2. B+ 树：B 树的进化，叶子节点存储所有数据并用链表串联
  3. 为什么用 B+ 树：减少磁盘 IO，矮胖树更适合磁盘存储
  4. MySQL InnoDB：聚集索引（主键）+ 辅助索引（回表）

B+ 树的设计哲学：用「空间换时间」和「减少 IO 次数」的思路，在磁盘存储场景下达到了查找性能的极致。

面试追问方向 ​

  • B 树和 B+ 树的区别？（关键字位置、叶子串联、范围查询效率）
  • MySQL 为什么用 B+ 树而不是 B 树？（范围查询更高效、查询更稳定、扇出更高）
  • InnoDB 聚集索引和辅助索引的区别？（聚集索引叶子存完整数据，辅助索引存主键）
  • 什么是回表？（辅助索引查到主键后，再去聚集索引查找完整数据）
  • B+ 树的阶数如何计算？（磁盘页大小 / 每条索引大小）
  • 什么情况下索引会失效？（函数、前导通配符、OR 条件、类型转换）

基于 VitePress 构建

Copyright © 2025-2026 Guide