B 树和 B+ 树有什么区别？｜阿里巴巴后端开发面经解析

60 秒回答模板

可以从三个层次回答。第一，结构上，B 树的关键字和数据记录可以分布在内部节点和叶子节点，搜索可能在内部节点结束；B+ 树的非叶子节点只保存用于路由的键和子指针，所有完整索引项都在叶子节点，叶子节点之间按顺序相连。第二，性能上，B+ 树非叶子节点更小，同样大小的磁盘页能容纳更多分支，树高更低，访问磁盘页次数更少；同时所有查询都走到叶子，路径长度稳定，更适合数据库的页缓存和并发控制。第三，业务查询上，B+ 树做范围查询只要定位到起点叶子，再沿叶子链表顺序扫描即可，而 B 树需要中序遍历多个层级，局部性和预读效果较差。所以数据库索引通常使用 B+ 树，尤其是 MySQL InnoDB 这类存储引擎，主键索引叶子存整行，二级索引叶子存二级键和主键，再通过主键回表。

考点 先定性

主线 节点内容

易错点 把 B 树说成二叉树，或者把 B 树和二叉搜索树、红黑…

深入解析

先定性

B 树和 B+ 树都不是二叉树，而是多路平衡搜索树，设计目标是减少磁盘页访问次数。数据库索引面对的瓶颈通常不是 CPU 比较几个键，而是一次次把磁盘页或缓存页读进来，所以树的分叉数量、节点能否塞进一个页、树高是否足够低，比单纯的时间复杂度表达更重要。面试里如果只说一个数据在叶子、一个数据在所有节点，深度是不够的。

节点内容

B 树的内部节点既可以保存关键字，也可以保存与关键字对应的记录地址甚至记录本身，因此一次查询如果命中内部节点就可以结束。B+ 树把职责拆得更清楚，非叶子节点只作为目录层，用关键字划分子树范围，真实的数据项或记录指针统一放在叶子节点。这个差异会直接影响节点大小、扇出、查询路径和范围扫描方式。

关键字分布

在 B 树中，一个关键字通常只出现在树中的某个节点，内部节点的关键字本身就是可命中的索引项。B+ 树中，非叶子节点里的关键字更多是分隔符或导航键，叶子节点才保存完整索引项，所以同一个边界键可能在内部层和叶子层重复出现。重复并不是浪费的主要矛盾，它换来的是更大的目录扇出和更规整的叶子扫描。

扇出与树高

数据库页大小通常固定，节点里放的内容越大，一个页能容纳的键和子指针越少，树的扇出就越低。B 树内部节点如果携带记录信息，会挤占目录空间；B+ 树非叶子节点只放键和指针，同样一页能放更多分支，因此在海量数据下树高更容易保持在很小的范围。树高每少一层，最坏情况下就可能少一次页访问。

点查路径

B 树做等值查询时，如果目标键刚好在内部节点，确实可能比 B+ 树少走一层；但这种优势不稳定，而且内部节点放数据会降低整体扇出。B+ 树所有查询最终都到叶子节点，看似多走一步，但路径长度一致，行为更可预测，也更符合数据库缓冲池、页锁或闩锁、执行计划成本估算的工程需求。数据库更看重整体稳定收益，而不是偶然命中内部节点。

范围查询

范围查询是 B+ 树在数据库索引中非常关键的优势。B+ 树先通过目录层定位到范围起点所在叶子页，然后沿着有序叶子节点继续扫描，直到超过范围终点即可。这种访问方式接近顺序读，容易利用预读和缓存。B 树虽然也能按序遍历，但需要在内部节点和子树之间反复切换，访问路径更复杂，磁盘局部性通常更差。

叶子链表

B+ 树叶子节点通常按键顺序维护相邻指针，形成从小到大的有序链式结构，很多存储引擎还会把叶子页作为双向链表维护。这样不仅支持 between、大于小于、order by、group by 的顺序访问，也让覆盖索引扫描更自然。叶子链表不是为了替代树查找，而是在树定位到起点之后，把后续连续读取变成高效的顺序推进。

索引实现

以常见关系型数据库为例，B+ 树更适合作为磁盘索引的底层结构。聚簇索引中，叶子节点可以直接保存完整行记录；二级索引中，叶子节点通常保存二级索引键和主键值，查到后再用主键去聚簇索引中查整行，这就是回表。若查询字段都在二级索引叶子中，就可以形成覆盖索引，避免回表，这些工程行为都建立在叶子层统一承载索引项的结构上。

易错点

把 B 树说成二叉树，或者把 B 树和二叉搜索树、红黑树混为一谈。
只背“B+ 树数据都在叶子节点”这一句，却解释不出它对扇出、树高和磁盘 IO 的影响。
认为 B+ 树一定在所有点查询场景都比 B 树快，忽略 B 树内部节点命中时可提前结束。
说 B 树不能做范围查询。正确说法是 B 树能做，但 B+ 树通过叶子有序链表做得更顺序、更高效。
认为 B+ 树非叶子节点完全没有键。正确说法是非叶子节点有键和子指针，只是不保存完整数据项。
把回表说成 B+ 树的必然缺点。回表是具体存储引擎中二级索引查整行的过程，覆盖索引可以避免。
忽略磁盘页模型，只用 O(log n) 解释两者差异，导致回答缺少数据库索引的工程深度。

面试官追问

为什么数据库索引通常不用普通二叉搜索树或红黑树？

二叉树和红黑树的分叉太少，数据量很大时树高会明显增加。数据库索引节点通常对应磁盘页或缓存页，一次访问页的成本远高于页内比较成本。B+ 树通过多路分叉把树高压得很低，几层目录就能管理大量数据，因此更适合磁盘和页缓存模型。

B+ 树一定比 B 树的等值查询更快吗？

不能绝对这么说。B 树的等值查询如果命中内部节点，理论上可以提前结束；B+ 树一般要走到叶子节点。但数据库场景更看重整体 IO 次数、范围扫描、缓存局部性和稳定性。B+ 树通过更高扇出降低树高，实际综合表现通常更适合索引。

B+ 树叶子节点为什么要有链表？

树结构负责快速定位某个键所在的叶子页，链表负责定位之后的连续扫描。范围查询、按索引顺序排序、分页扫描等场景都需要访问一段连续键值。如果没有叶子链表，就要反复从根节点或依赖复杂遍历状态找下一个键，效率和实现都更差。

B+ 树的非叶子节点完全不存数据，会不会浪费空间？

它确实会让一些分隔键在非叶子节点和叶子节点重复出现，但换来的是目录层更轻、更高扇出和更稳定的扫描方式。数据库索引的主要成本常常是页访问而不是键重复占用的少量空间，因此这种空间换 IO 的设计通常是划算的。

聚簇索引和二级索引在 B+ 树中有什么区别？

聚簇索引的叶子节点通常保存完整行数据，数据行本身按主键顺序组织；二级索引的叶子节点保存二级索引键以及对应主键值。通过二级索引查到主键后，如果还需要索引中没有的列，就要再到聚簇索引查整行，这个过程通常称为回表。

为什么说 B+ 树适合范围查询和排序？

因为 B+ 树的叶子节点保存完整索引项，并按键有序连接。执行范围查询时，先从根到叶定位起点，然后顺序读取后续叶子页即可；如果排序方向和索引顺序匹配，也能减少额外排序成本。这种顺序访问对磁盘预读和缓存命中都更友好。