数据库索引需要同时满足：
SELECT * FROM user WHERE id = 1234SELECT * FROM user WHERE id > 1000 AND id < 2000为什么散列表、平衡二叉树、跳表都不够好？
| 数据结构 | 等值查询 | 区间查询 | 磁盘友好 |
|---|---|---|---|
| 散列表 | O(1) | ❌ 不支持 | 一般 |
| AVL/红黑树 | O(log n) | 需中序遍历 | ❌ 树高大，IO 多 |
| 跳表 | O(log n) | ✅ 链表遍历 | 一般 |
| B+树 | O(log_m n) | ✅ 叶子链表 | ✅ 矮胖，IO 少 |
将 BST 的叶子节点用链表串联 → 支持区间查询。
问题：树高 = log₂n。1 亿数据 → 树高约 27 层 → 27 次磁盘 IO。
将每个节点扩展为 m 个子节点：
| 数据量 | 二叉树高 | 100 叉树高 |
|---|---|---|
| 1 亿 | 27 | 4 |
| 10 亿 | 30 | 5 |
树高 = 磁盘 IO 次数。m 越大，树越矮，IO 越少。
操作系统按**页（Page）**读取磁盘，通常 4KB/页。
设计原则：让每个节点大小恰好等于一页，读一个节点 = 一次 IO。
PAGE_SIZE = (m-1) × key_size + m × child_pointer_size
例如 key=8B，指针=8B，页=16KB：m ≈ 16384/16 ≈ 1000。
graph TD R[30 | 60] --> A[10|20|30] R --> B[40|50|60] R --> C[70|80|90] A --> A1[data] B --> B1[data] C --> C1[data] A1 -.->|next| B1 B1 -.->|next| C1
| 特征 | 说明 |
|---|---|
| 非叶节点只存索引 | 不存数据，最大化扇出 |
| 叶子节点存数据 | 包含键值 + 数据地址 |
| 叶子节点双向链表 | 支持正/反向区间扫描 |
| 所有叶子同层 | 保证等值查询路径等长 |
| 节点子树数 ∈ [⌈m/2⌉, m] | 保证树不会太"瘦" |
| 对比项 | B 树 | B+树 |
|---|---|---|
| 数据存储位置 | 所有节点 | 仅叶子节点 |
| 叶子链表 | 无 | 有（双向） |
| 区间查询 | 需中序遍历 | 叶子链表顺序扫描 |
| 非叶节点大小 | 较大（含数据） | 较小（纯索引）→ 扇出更大 |
当某节点子节点数超过 m 时触发分裂：
当某节点子节点数少于 ⌈m/2⌉ 时触发合并：
// 非叶子节点
public class BPlusTreeNode {
public static int m = 5; // m 叉树
public int[] keys = new int[m - 1]; // 键值，划分数据区间
public BPlusTreeNode[] children = new BPlusTreeNode[m];
}
// 叶子节点
public class BPlusTreeLeafNode {
public static int k = 3;
public int[] keys = new int[k]; // 数据键值
public long[] dataAddr = new long[k]; // 数据磁盘地址
public BPlusTreeLeafNode prev; // 双向链表前驱
public BPlusTreeLeafNode next; // 双向链表后继
}| 索引类型 | 叶子节点存储 | 说明 |
|---|---|---|
| 聚簇索引（主键） | 完整行数据 | 一张表只有一个 |
| 二级索引（非主键） | 主键值 | 查完整行需"回表" |
WHERE age BETWEEN 20 AND 30）ORDER BY）| 代价 | 说明 |
|---|---|
| 写入变慢 | 每次 INSERT/UPDATE/DELETE 都要维护索引 |
| 空间占用 | 每个索引都是一棵独立的 B+树 |
| 优化器选择 | 索引过多时优化器可能选错索引 |
实践建议：单表索引不超过 5~6 个；高频查询字段建索引，低区分度字段（如性别）不建。
Q：一棵 B+树能存多少数据？
假设：主键 bigint=8B，指针=6B，页=16KB。
Q：B+树中叶子链表是单向还是双向？
InnoDB 使用双向链表，支持 ORDER BY ... DESC 反向扫描。
B+树是磁盘 IO 友好的多路平衡搜索树，核心设计哲学：