B树与B+树:数据库索引的底层数据结构解析

更新: 8/23/2026 字数: 0 字 时长: 0 分钟

开篇:那条慢查询,为什么加了索引就快了?

作为前端/全栈开发者,你几乎每天都在和数据库打交道,也大概率遇过这些场景:

• 一条 SELECT * FROM orders WHERE user_id = 123 在数据量小的时候飞快,数据涨到几百万行后突然卡成几秒;
• 加了一句 CREATE INDEX idx_user ON orders(user_id),同样的查询瞬间恢复毫秒级;
• 用 ORM(Prisma、TypeORM、Sequelize)写查询时,文档反复提醒你"给高频查询字段加索引";
• 面试或 Code Review 被问:"你这个 WHERE name LIKE '%关键词%' 为什么走不了索引?"

这些问题的答案,全都指向同一个底层机制——数据库索引用的是 B+ 树。理解它,你就能从"凭感觉加索引"升级到"知道为什么加、加了为什么快、什么情况会失效"。本文不推数学公式,只讲和 Web 开发强相关的原理与实战。

先给个类比锚点:索引之于数据库,就像书末的目录。 没有目录,找一个词要一页页翻(全表扫描);有了目录,先查目录定位页码,直接翻过去。而 B+ 树,就是这本"目录"被设计得极其高效的数据结构。

一、先理解一个前提:为什么索引结构要为"磁盘"而设计

要讲清 B/B+ 树,必须先理解一件事——数据库的数据主要存在磁盘上,不是内存里。 这是整个设计的出发点。

对前端来说,你平时写 JS 操作的都是内存里的数组、对象,访问快到可以忽略耗时。但数据库要处理的数据量远超内存,大部分躺在磁盘上。而磁盘 I/O 比内存访问慢成千上万倍。所以数据库索引结构的核心优化目标只有一个:

尽可能减少磁盘 I/O 的次数。

数据库读磁盘不是一个字节一个字节读,而是按"块"读,这个块叫页(Page),MySQL InnoDB 里默认一页 16KB。读一页 = 一次磁盘 I/O。 记住这个概念,后面所有的"为什么"都由它推导而来。

一棵树查一个值,要经过几个节点,大致就要几次 I/O(每个节点对应一页)。所以树越"矮",I/O 越少,查询越快。这就是理解一切的钥匙。

二、什么是 B 树(B-Tree)

2.1 从二叉查找树的缺陷说起

你熟悉的二叉查找树(BST)、红黑树,每个节点最多两个子节点。它们在内存里很优秀,但放到磁盘场景就露怯了:节点太多,树太高。

假设有 100 万条数据,二叉树的高度约为 log₂(1,000,000) ≈ 20 层。查一个值最坏要访问 20 个节点,也就是 20 次磁盘 I/O。这在磁盘场景下是灾难。

问题的根源:二叉树每个节点只存 1 个键、最多 2 个分叉,"太瘦太高"。要压矮它,就得让每个节点存更多的键、有更多的分叉——这就是 B 树的核心思想。

2.2 B 树的定义与结构

B 树是一种"多路平衡查找树"。 拆解这三个词:

• 多路:每个节点可以有多个子节点(不止 2 个),可以存多个键值;
• 平衡:所有叶子节点都在同一层,树的任何一条路径长度都相同,不会退化成链表;
• 查找树:节点内的键有序,左小右大,支持二分查找。

一棵 B 树的结构大致如下(每个节点存多个键):

关键特征:每个节点既存键值,也存该键对应的数据(或数据指针)。 因为一个节点能存很多键(比如几十上百个),分叉极多,所以同样 100 万数据,B 树可能只需要 3 层,查询最多 3 次 I/O——相比二叉树的 20 次,天壤之别。

2.3 B 树的查找、插入、删除(直观理解)

• 查找:从根节点开始,在节点内部对有序键做二分查找。命中就返回;没命中就根据大小关系走对应的子节点分叉,逐层向下。因为树矮,几层就到底。
• 插入:找到该插入的叶子节点放进去。如果节点存满了(超过容量上限),就分裂:把中间的键提升到父节点,节点一分为二。分裂可能向上传导,但因为有平衡机制,树始终保持所有叶子同层。
• 删除:删掉目标键。如果删除后节点太空(低于下限),就向兄弟节点借一个键,或与兄弟节点合并,以维持平衡。

你不用记细节,只需抓住本质:B 树靠"分裂"和"合并"始终保持矮胖且平衡,从而保证任何操作都是稳定的对数级复杂度。

三、什么是 B+ 树(B+Tree)

B 树已经很好了,但数据库(MySQL/PostgreSQL 等)实际用的是它的升级版——B+ 树。理解两者的区别,是这篇文章最核心的部分。

3.1 B+ 树相对 B 树的三个关键改动

改动一:数据只存在叶子节点,内部节点只存键(索引)。 B 树的每个节点都存数据;而 B+ 树的内部节点(非叶子)只存键值,不存数据,纯粹用来"指路"。所有真正的数据(或数据指针)都放在最底层的叶子节点。

改动二:叶子节点之间用链表串联。 B+ 树把所有叶子节点用一条双向链表从左到右按顺序连起来。这一点看似简单,却是它碾压 B 树的杀手锏(下面讲范围查询时你会拍案叫绝)。

改动三:所有查询都要走到叶子节点。 因为数据只在叶子层,任何一次查找都必然从根走到叶子,路径长度固定 = 树高。查询性能非常稳定。

B+ 树的结构如下:

注意底部那条虚线链表——它把所有数据按顺序穿成了一串。

3.2 为什么这三个改动如此重要

① 内部节点不存数据 → 树更矮 → I/O 更少。 内部节点只存键不存数据,意味着同样 16KB 一页,能塞进更多的键,分叉更多。分叉越多,树越矮。实践中,InnoDB 的 B+ 树存千万级数据通常也就 3~4 层,即一次查询仅需 3~4 次磁盘 I/O。

② 叶子链表 → 范围查询和排序快到飞起。 这是 B+ 树最实用的优势,直接关系到你的日常 SQL:

• 查 WHERE age BETWEEN 20 AND 30:B+ 树只需定位到 20 所在的叶子,然后顺着链表往右扫到 30 即可,一路顺序读取,极快;
• 而 B 树因为数据分散在各层节点,做范围查询要不断在树里上下跳转(中序遍历),效率低得多;
• ORDER BY、LIMIT 分页、GROUP BY 等都直接受益于这条有序链表。

③ 查询性能稳定。 B 树可能在离根近的节点就命中数据(快),也可能要到叶子(慢),性能波动;B+ 树每次都走到叶子,每次查询的 I/O 次数一致,性能可预测——这对数据库这种要保证稳定响应的系统至关重要。

3.3 一张表总结 B 树 vs B+ 树

对比维度	B 树	B+ 树
数据存储位置	每个节点都存数据	只有叶子节点存数据
内部节点	存键 + 数据	只存键(指路用)
叶子节点连接	无	双向链表串联
单点查询	可能提前命中,不稳定	必到叶子,稳定
范围/排序查询	慢(需树内遍历)	快(顺链表扫描)
树高(同数据量)	较高	更矮(内部节点存键更多)
数据库采用	较少	主流选择(MySQL/PG等)

四、为什么数据库索引选 B+ 树,而不是其他数据结构

这是面试高频题,也是理解索引的关键。我们把候选结构逐个拉出来对比。

4.1 为什么不用二叉查找树 / 红黑树?

二叉树、红黑树是内存友好的结构,但对磁盘不友好:每个节点只有 2 个分叉,树太高。100 万数据要 20 层,就是 20 次磁盘 I/O。红黑树虽然能保持大致平衡,但改变不了"二叉=高"的本质。B+ 树用"多路"把树压到 3~4 层,I/O 直接降一个数量级。 这是决定性的差距。

4.2 为什么不用哈希表?

哈希表(Hash)单点查询是 O(1),看起来比 B+ 树还快,为什么数据库主键索引不用它做默认结构?因为哈希表有两个致命短板:

• 不支持范围查询:哈希把键打散成无序的散列值,WHERE age > 20、ORDER BY、BETWEEN 这类查询完全无法利用哈希索引,只能全表扫描。而这些恰恰是 Web 应用的高频操作。
• 不支持最左前缀匹配和排序:分页、排序、区间统计全都做不了。

所以哈希索引只适合等值查询(=、IN)的特定场景(MySQL 的 Memory 引擎、以及 InnoDB 的自适应哈希才用),不能当通用索引结构。B+ 树则既能高效单点查询,又能范围/排序/分页通吃,综合最优。

4.3 结论:B+ 树是"磁盘存储 + Web 查询模式"下的最优解

一句话总结选型逻辑:数据库需要一个既能减少磁盘 I/O(要矮胖 → 排除二叉树)、又能高效支持范围查询和排序(要有序链表 → 排除哈希表)、还要数据存取稳定的结构,而 B+ 树恰好同时满足这三点。

五、拓展:那些让你少踩坑的实用知识

5.1 聚簇索引 vs 非聚簇索引

这是理解 MySQL 索引绕不开的一对概念,直接影响你的查询性能。

• 聚簇索引(Clustered Index):B+ 树的叶子节点直接存放整行数据。InnoDB 的主键索引就是聚簇索引——数据本身就是按主键组织存储的。所以一张表只能有一个聚簇索引(数据只能有一种物理排列)。用主键查数据,一次到叶子就拿到整行,最快。

• 非聚簇索引(二级索引 / Secondary Index):叶子节点存的不是整行数据,而是主键值。当你用非主键字段(如 idx_user_id)查询时,先在二级索引 B+ 树里找到对应的主键,再拿主键回到聚簇索引里查一次完整数据——这个过程叫回表。

回表是性能优化的关键概念。一次查询走了两棵 B+ 树,比直接主键查询慢。这也引出了下面的优化技巧。

5.2 覆盖索引:消除回表的利器

如果你的查询只需要索引里已有的字段,数据库就不需要回表了——这叫覆盖索引(Covering Index)。

-- 建了联合索引 idx_user (user_id, status)
-- 这个查询只要 user_id 和 status,索引里都有,无需回表,极快
SELECT user_id, status FROM orders WHERE user_id = 123;

-- 而这个要 * (所有列),索引里没有 amount 等字段,必须回表
SELECT * FROM orders WHERE user_id = 123;

实战建议:避免无脑 SELECT *,只查需要的列,有机会命中覆盖索引,省掉回表开销。

5.3 索引失效的常见场景(排查慢查询必看)

理解了 B+ 树"有序"的本质,就能理解为什么这些写法会让索引失效:

失效场景	示例	原因
左模糊/全模糊查询	WHERE name LIKE '%abc%'	B+ 树按前缀有序,% 开头无法利用有序性定位
对索引列做运算/函数	WHERE YEAR(created_at) = 2024	列被函数包裹后,索引存的是原值,无法匹配
联合索引不满足最左前缀	索引 (a,b,c),却 WHERE b=1	联合索引按最左列排序,跳过 a 无法用
隐式类型转换	字段是字符串,却 WHERE phone = 13800000000(传数字)	类型转换等于对列做了函数运算
OR 连接非索引列	WHERE a=1 OR d=2(d 无索引)	只要有一边没索引,整体可能走全表
不等于 / NOT IN(部分场景)	WHERE status != 1	需扫描大量数据,优化器可能放弃索引

排查工具:用 EXPLAIN 分析你的 SQL。重点看 type 列(ALL 是全表扫描,危险信号;ref/range/const 才是走了索引)和 key 列(实际用了哪个索引,为 NULL 说明没走索引)。

EXPLAIN SELECT * FROM orders WHERE user_id = 123;
-- 看 type 是不是 ALL,key 是不是 NULL,一眼定位索引是否生效

5.4 主流数据库的 B+ 树实现差异(简要)

• MySQL(InnoDB):主键索引 = 聚簇索引,叶子存整行;二级索引叶子存主键,需回表。没有主键会自动生成隐藏主键,所以建议每张表都显式定义主键。
• PostgreSQL:默认索引都是"非聚簇"的,数据行单独存放在堆(heap)中,所有索引(包括主键)叶子节点存的都是指向堆的行指针(TID),没有 InnoDB 那种"主键即数据"的聚簇结构。因此 PG 不存在"二级索引回表到聚簇索引"的概念,但有类似的"索引→堆"访问。
• 共同点:它们的默认索引都基于 B+ 树(或其变体),核心思想一致。

六、收尾:索引设计实用建议与排查清单

索引设计建议

1. 给高频查询的 WHERE、JOIN、ORDER BY 字段建索引,而不是给所有字段都建(索引会拖慢写入并占空间)。
2. 联合索引遵循最左前缀原则,把区分度高、最常用作过滤条件的列放最左边。
3. 善用覆盖索引,查询只取需要的列,避免 SELECT *,尽量让索引"自给自足"消除回表。
4. 选择合适的主键:用自增整数(或有序 ID)做主键,避免用 UUID 等随机值——随机主键会导致 B+ 树频繁分裂、页分裂,拖慢写入。
5. 不要在低区分度字段上单独建索引(如性别、状态这种只有几个取值的列,索引意义不大)。

慢查询排查速查清单

1. 用 EXPLAIN 看执行计划 → type=ALL 或 key=NULL 说明没走索引
2. 检查 WHERE 条件是否踩了"索引失效"的坑(模糊左匹配、函数、类型转换)
3. 联合索引检查是否满足最左前缀
4. 是否 SELECT * 导致大量回表 → 改成只查需要的列试试覆盖索引
5. 数据量大且范围查询 → 确认走的是 B+ 树的 range 扫描而非全表
6. 排序慢 → 确认 ORDER BY 字段有索引,能利用叶子链表的有序性

数据库索引选 B+ 树,是因为它同时做到了三件别的结构做不到的事:用"多路"把树压得足够矮以减少磁盘 I/O(胜过二叉树/红黑树),用"叶子链表"让范围查询和排序飞快(胜过哈希表),用"数据只存叶子"保证查询稳定。

理解了这一点,你再看索引失效、回表、覆盖索引这些概念,就不再是零散的规则,而是同一个底层结构自然推导出的结果。