B树、B-tree与B+树

在计算机科学，尤其是数据库和文件系统的领域中，B树、B-tree和B+树是理解数据如何被高效存储和检索的关键。它们之间关系紧密，但功能和应用上又存在着决定性的差异。

一、核心概念澄清：B树就是B-tree

首先需要明确一个最基本的概念：B树和B-tree是完全相同的概念。B-tree是其英文原名，在国内的翻译过程中，有时被直译为“B-树”，有时被意译为“B树”。这两种叫法指代的都是同一种自平衡的多路搜索树结构，它能在对数时间内完成数据的查找、插入和删除操作。

二、主角登场：为什么数据库索引偏爱B+树？

当您听到“数据库索引”时，可以有九成的把握认为其底层实现是B+树。是的，绝大多数现代关系型数据库（如MySQL的InnoDB、PostgreSQL）都选择B+树作为其标准和默认的索引结构。

这并非偶然，而是因为B+树的结构特性完美地解决了数据库存储的核心痛点：最大限度地减少昂贵的磁盘I/O操作。

B+树之所以能成为主流，主要有以下几点关键优势：

更低的树高，更少的磁盘I/O：
- B+树：其内部节点（非叶子节点）只存储键（key）和指向下一层节点的指针，不包含实际的数据记录。这使得在同样大小的节点空间内（通常为一个磁盘页，如16KB），B+树的内部节点可以容纳成百上千个键，其“扇出”（fan-out）非常高。极高的扇出意味着树的整体高度会非常低。对于一个存储着数亿条记录的表，其B+树索引的高度通常也只有3-4层，这意味着查找任何数据最多只需要3-4次磁盘I/O。
- B树：其内部节点既存储键，也存储数据。这限制了每个节点能容纳的键的数量，导致在同等数据量下，B树的高度可能比B+树更高，从而需要更多的磁盘I/O。
极其稳定的查询效率：
- B+树：所有的数据记录都只存在于叶子节点上。因此，任何一次查找都必须从根节点开始，完整地走到某个叶子节点才能获取数据。这保证了每次查询的I/O次数是稳定且可预测的。
- B树：数据分散在所有节点中。虽然运气好的时候可能在根节点或中间节点就找到数据，路径更短，但这也意味着查询性能是不稳定的，路径长度在1到树高之间波动。
对范围查询的完美支持：
- B+树：这是它的“杀手锏”。所有叶子节点通过一个双向链表相互连接，并且叶子节点内部的数据本身是有序的。当执行范围查询（如 WHERE age > 25 AND age < 40）时，引擎只需定位到起始叶子节点（age=25），然后就可以沿着链表顺序扫描，直到范围结束。这个过程高效且连续，极大地提升了范围查询的性能。
- B树：要进行范围查询，必须对树进行复杂的中序遍历，这会涉及到更多节点的访问和回溯，效率远低于B+树。

三、核心差异速览表

特性	B树 (B-tree)	B+树 (B±tree)
数据存储位置	所有节点（内部节点和叶子节点）都存储键和数据。	只有叶子节点存储键和数据，内部节点仅作为索引。
叶子节点结构	叶子节点之间相互独立，没有链接。	所有叶子节点通过双向链表连接，形成一个有序序列。
查询效率	不稳定，最好的情况是O(1)（数据在根节点），最差是O(logN)。	非常稳定，任何查询的路径长度都相同，为O(logN)。
范围查询	效率低，需要进行中序遍历。	效率极高，利用叶子节点的有序链表即可完成。
空间与I/O	内部节点存储数据，导致扇出较小，树高可能更高，I/O次数可能更多。	内部节点不存数据，扇出极大，树高很低，I/O次数少。

四、数据库索引的“非主流”选择

尽管B+树是当之无愧的主角，但一个成熟的数据库系统也会根据特定场景提供其他索引结构作为补充：

哈希索引 (Hash Index)：在进行精确的等值查询时（如 WHERE email = '...'），其速度极快，理论上时间复杂度为O(1)。但它完全不支持范围查询。
R树 (R-Tree)：专门用于处理多维空间数据，如地理位置信息。能高效回答“查找我附近5公里内的所有餐馆”这类空间查询。
全文索引 (Full-Text Index)：专门用于在大量文本中快速搜索关键词，其底层是倒排索引（Inverted Index），可以高效处理 LIKE '%keyword%' 这种B+树无能为力的模糊查询。