[ 10, 20 ]          ← 非叶子节点，只有键
                /    |    \
               /     |     \
    [3,5,8] ->[10,15] ->[20,25]    ← 叶子节点，有键和数据，且相互链接

B+树与B树的区别及其在数据库索引中的应用 B+树是数据库系统中广泛使用的索引数据结构，它与B树在结构和性能特性上有显著差异。让我们一步步深入理解。 1. 核心概念与背景 数据库需要高效地根据某个键（如用户ID）来查找、插入、删除数据记录。由于数据量远大于内存容量，索引结构必须设计为适合磁盘I/O的特性： 磁盘I/O以“页”（通常4KB）为单位，速度很慢。 设计目标： 减少磁盘I/O次数 ，让每次I/O读取/写入尽可能多的有用数据。 B树和B+树都是平衡多路搜索树，能在少量I/O内访问海量数据。 2. B树（B-Tree）结构回顾 B树是一个 自平衡 的多路搜索树，每个节点可包含多个键和多个子节点指针。 关键特性 ： 一个 m 阶B树，每个节点最多有 m 个子节点，非根节点至少有 ceil(m/2) 个子节点。 每个节点包含： 键（Key）：用于在树中导航。 对应的数据（或数据指针）：键关联的实际数据（或指向数据行的指针） 直接存储 在节点中。 所有叶子节点在同一层。 查找过程 ： 从根节点开始，在节点内部进行二分查找，找到键所在的区间，进入对应的子节点，重复直到找到目标键， 直接在非叶子节点就能获取数据 。 3. B+树（B+ Tree）的详细结构 B+树是B树的变种，是大部分数据库（如MySQL的InnoDB引擎）和文件系统的标准索引结构。 关键特性 ： 与B树类似，也是多路平衡树。 核心区别 ： 非叶子节点（内部节点） ：只存储 键 ，不存储实际的数据记录（或数据指针）。它仅作为 导航目录 。 叶子节点 ：存储全部 键 ，并且每个键 关联着实际的数据记录（或数据指针） 。此外，所有叶子节点通过指针 按顺序链接成一个双向链表 。 查找任何数据都必须走到叶子节点才能获得。 结构示例（简化） ： 4. B+树与B树的详细对比 | 特性 | B树 | B+树 | |------|-----|------| | 数据存储位置 | 键和数据可在任意节点 | 数据仅在叶子节点 | | 键的重复 | 键不重复 | 内部节点的键会在叶子节点中重复出现 | | 叶子节点链接 | 叶子节点之间无链接 | 叶子节点通过双向链表顺序链接 | | 查找性能 | 可能在内部节点找到，平均较快 | 必须走到叶子节点，稳定但平均稍慢 | | 范围查询 | 需要中序遍历树，效率较低 | 通过叶子节点链表顺序扫描，极高效 | | 节点容量 | 每个节点有键+数据，相同大小下键数较少 | 内部节点只存键，相同大小下键数更多，树更矮 | | 磁盘I/O | 树相对较高，I/O次数可能较多 | 树更矮，I/O次数更少 | 5. 为何数据库索引首选B+树？ 更矮的树，更少的I/O 由于内部节点不存储数据，相同大小的磁盘页能容纳更多键，从而树的 扇出（Fan-out）更大 ， 高度更低 。查找一个键需要更少的磁盘I/O。 范围查询（Range Query）效率极高 这是B+树最重要的优势。SQL中 WHERE age BETWEEN 20 AND 30 这类查询非常常见。 B树：需要不断进行树的遍历（中序遍历）来访问范围内的所有节点，I/O跳跃且不可预测。 B+树：在叶子节点找到起始键后，只需沿着叶子节点的链表顺序扫描即可， 无需回溯到上层节点 。这是顺序I/O，速度极快。 查询性能更稳定 B树中，可能在根节点就找到数据，也可能在叶子节点找到。性能不稳定。 B+树中， 任何一次查找都必须走到叶子节点 ，路径长度总是等于树高，性能稳定可预测。稳定的性能对数据库查询优化器至关重要。 全表扫描更高效 当不需要索引时（如 SELECT * FROM table ），B+树只需遍历叶子节点链表即可获得全部数据。B树则需要对整棵树进行复杂的中序遍历。 6. 实例：在数据库中查找与范围查询 假设有一个用户表，以 user_id 为主键建立B+树索引，树高为3。 场景A：精确查找 user_id=15 从根节点（第1层）开始，找到键值区间，进入第2层对应节点。 在第2层节点中再次比较，进入第3层（叶子节点）。 在叶子节点中通过二分查找找到 user_id=15 ，读取其对应的数据行地址，然后访问数据。 场景B：范围查找 user_id BETWEEN 15 AND 25 首先同样执行一次查找，定位到 user_id=15 所在的叶子节点。 从该节点开始，顺序读取节点内的键和数据指针，直到遇到 user_id > 25 。 如果当前叶子节点读完，则通过链表指针跳到下一个叶子节点继续。 整个过程几乎都是顺序I/O，效率非常高。 7. 总结 B树 像一个“矮胖的、数据分散在各处的目录”，适用于键和数据体积小、精确查找为主、范围查询少的场景（如某些文件系统）。 B+树 像一个“分层目录+末端完整电话簿”， 牺牲了内部节点的数据携带能力，换来了更矮的树、更稳定的查询性能和无敌的范围查询效率 。这完美契合了关系型数据库的查询模式。 因此，当你听到“数据库索引默认使用B+树”时，核心原因就是： 它通过将数据集中在叶子节点并用链表连接，极大地优化了数据库中最耗时的操作——范围扫描和全表扫描，同时保持了高效的精确查找能力。