第 8 章 · 02 B+树索引:数据库的标准索引

第 8 章 · 02 B+树索引:数据库的标准索引

本节摘要:几乎所有数据库都用 B+树做索引——它高扇出(每节点很多键)、矮胖(深度浅,IO 次数少)、叶子链表(范围查询友好)。本节讲清 B+树与二叉树/哈希表的对比,它的结构(非叶子只存键与子指针、叶子存数据并串联),以及插入时的页分裂。理解 B+树,你就理解了「为什么数据库索引这么快」「为什么用 B+树而非二叉树」。

内容来源:基于数据库索引整理的导读。

学习目标

1. 说清 B+树的结构:非叶子(键+子指针)、叶子(数据+链表)。
2. 解释 B+树相对二叉树(太深)、哈希(无范围查询)的优势。
3. 描述插入与页分裂。
4. 理解「聚簇索引」(数据本身存在 B+树叶子)。

一、学习价值:索引是数据库的灵魂

数据库快,很大程度上靠索引。而索引的事实标准是 B+树(或其变体如 B-tree、LSM-Tree)。理解 B+树,你才理解:

• 为什么索引能加速查询(从 O(n) 全表扫描降到 O(log n))。
• 为什么主键查询特别快(聚簇索引)。
• 为什么范围查询 WHERE age BETWEEN 20 AND 30 快(叶子链表)。
• 索引建多了为何插入变慢(每次插入要更新索引树,可能分裂)。

二、子系统拆解

B+树结构

        [键10 | 键20 | 键30]               ← 根(非叶子, 只存键与子指针)
        /        |         |        \
   [1,5,8]  [10,12,15]  [20,25]  [30,35,40]  ← 叶子(存数据, 用链表串联)
     →        →           →        →
​

• 非叶子节点:只存「键 + 指向子节点的指针」,不存数据。这让每节点能塞很多键(高扇出),树很矮(几层就能索引上亿条)。
• 叶子节点:存实际数据(或数据指针),叶子之间用链表串联(方便范围查询)。
• 矮胖:即使索引上亿条,树深可能只 3-4 层(每次查 3-4 次 IO)。

为何不用二叉树或哈希

• 二叉树:每节点最多 2 子,索引百万条深约 20 层,IO 次数多。
• 哈希:O(1) 等值查询快,但不支持范围(BETWEEN、<)与排序(ORDER BY)。
• B+树:兼顾等值(O(log n))与范围(叶子链表),是数据库综合最优。

插入与页分裂

插入新键:沿树找到对应叶子页,插入。若叶子页满了,分裂:取半键建新页,中间键上推到父节点。父节点满同样分裂,可能一路传到根(根分裂,树加深一层)。

聚簇索引

「聚簇索引」:数据本身按主键存在 B+树的叶子里(而非单独存)。主键查询直接拿到数据。一个表通常只有一个聚簇索引(主键),其他索引(非聚簇)存「主键值」,需二次查找。

三、上手第一步

1. 先实现最简 B+树(固定阶,如每节点最多 4 键)。
2. 实现插入:找叶子页→插入→满则分裂→上推。
3. 实现等值查询:沿树到叶子。
4. 实现范围查询:沿叶子链表。

本节要点回顾

1. B+树:非叶子(键+子指针,高扇出)、叶子(数据+链表,范围友好)、矮胖(深 3-4 层索引亿条)。
2. 相对二叉树:矮得多,IO 少;相对哈希:支持范围与排序。
3. 插入页分裂:叶满分裂,中间键上推,可能传到根。
4. 聚簇索引:数据按主键存在 B+树叶子;主键查询直接拿数据。
5. 索引多的代价:插入要更新索引树(可能分裂),变慢。

推荐上手顺序

1. 实现最简 B+树(小阶数,便于手算)。
2. 插入与分裂(纸笔练几遍,再写代码)。
3. 等值查询、范围查询。
4. 结合第 1 节页式存储,把节点存成页。

下一节讲数据的插入与查询(把前两节合起来)。