FHCY-Study08-B 树/B+树/B*树
type
status
date
slug
summary
tags
category
icon
password
1️⃣ B 树（B-Tree）
B 树是一种 平衡的多路搜索树（Multi-Way Balanced Search Tree），每个节点包含多个 key，适合用于大规模、外部存储环境（如磁盘）。
- 阶数为
m的 B 树，每个节点最多有m - 1个 key 和m个子节点
- 所有叶子节点在同一层
- 所有节点（包括非叶节点）都存储数据
- 非叶子节点用于查找路径，也可直接存储数据记录
2️⃣ B+ 树（B+Tree）
B+ 树是 B 树的变体，目前主流数据库（如 MySQL/InnoDB）使用的索引结构。
- 所有数据记录只存储在叶子节点，非叶节点仅存储索引信息
- 所有叶子节点通过 链表顺序连接
- 每个非叶节点有
n个 key 和n个子节点，key 用于导航，非叶节点不保存实际数据
- 范围查询效率极高（通过叶子链表一次遍历）
- 非叶节点较小，磁盘读写效率更高
- 所有数据都在叶节点，适合顺序扫描和范围查询
主流数据库索引结构（如 MySQL 的 InnoDB 存储引擎）
3️⃣ B* 树（B*Tree）
B* 树是对 B+ 树的进一步优化，它在节点分裂时采取 “合并再分裂” 的策略，提高空间利用率。
- 兄弟节点之间存在指针；
- 分裂前尝试向兄弟节点借数据；
- 平均每个节点利用率更高，树高度更低 → 更少磁盘访问。
商业数据库系统（如 DB2、Oracle）中常见
特性 | B 树 | B+ 树 | B* 树 |
数据存储位置 | 所有节点 | 只在叶子节点 | 只在叶子节点 |
非叶子节点是否存数据 | 是 | 否 | 否 |
叶子节点是否链表连接 | 否 | ✅ 是 | ✅ 是 |
范围查询效率 | 一般（需中间节点参与） | ✅ 高效（顺序链表） | ✅ 高效 |
空间利用率 | 一般 | 较高 | ✅ 更高 |
用途 | 较老系统、理论教材 | ✅ 主流数据库索引（如 InnoDB） | 高性能商业数据库 |
上一篇
07-图
下一篇
01-算法
Loading...