# B树和B+树
# B树
# 简介
B树是一种自平衡的树，能够保持数据有序，并且支持在O(log n)时间内进行查找、顺序访问、插入和删除。B树的设计初衷是为了优化磁盘存取性能，它通过增加节点的分支数来减少树的高度，从而减少磁盘I/O次数。
# 特点
- 所有叶子节点都在同一层
- 每个节点可以存储多个键值对（阶数决定具体数量）
- 所有节点（除根节点）至少半满
- 节点的子节点数量总是比键值对数量多1
- 适合磁盘存储系统，每个节点大小通常等于磁盘块大小
# 基本操作
查找
- 从根节点开始，根据键值的大小关系选择合适的子树
- 在节点内部使用二分查找定位键值
- 平均时间复杂度O(log n)
插入
- 先找到合适的叶子节点
- 如果节点未满，直接插入
- 如果节点已满，进行分裂操作
节点分裂示例
# 应用场景
文件系统
- 用于管理文件的索引结构
- 支持快速的文件查找和目录遍历
数据库索引
- 支持高效的范围查询
- 适应大规模数据的存储和检索
# B+树
# 简介
B+树是B树的变体，专门针对数据库系统的文件组织和索引而设计。它在B树的基础上做了重要的改进，使其更适合数据库和文件系统的应用场景。
# 特点
所有数据都存储在叶子节点
- 非叶子节点只存储键值，不存储数据
- 数据存储在叶子节点可以提高空间利用率
叶子节点通过指针连接
- 形成有序链表
- 支持高效的顺序访问
非叶子节点结构
- 只存储键值和指针
- 可以容纳更多索引项
- 降低树的高度
查询优化
- 所有查询都要到达叶子节点
- 查询路径统一，效率稳定
- 范围查询性能优异
# 优势
范围扫描效率高
- 叶子节点链表支持顺序访问
- 适合范围查询和排序操作
磁盘读写效率高
- 节点大小匹配磁盘块
- 减少I/O次数
树高度更低
- 非叶子节点可存储更多索引
- 减少查询时的磁盘访问次数
# 应用场景
关系型数据库索引
- MySQL（InnoDB存储引擎）
- PostgreSQL
- Oracle
文件系统
- NTFS
- ext4
- XFS
特点比较
- B树：适合随机访问，键值对分布在所有节点
- B+树：适合范围查询，数据集中在叶子节点