概述

B树是一种自平衡的树，B树将二叉查找树一般化，每个节点可以拥有2个以上的子节点，适用于读写比较大的数据块的存储系统，常用于数据库与文件系统的实现上。

定义

一个 m 阶B树具有以下属性

  1. 每个节点最多有 m 个子节点。
  2. 每个非叶子节点最少有 \lfloor m/2 \rfloor 个子节点。
  3. 根节点至少有两个子节点。
  4. 有 k 个子节点的非叶子节点拥有 k-1 个键。
  5. 所有叶子节点在同一层。

实现

B树内部每个节点拥有可变数量的子节点，因为子节点数量为一个预先设定的范围，所以不需要像AVL树一样频繁地改变结构以保持平衡。当子节点数量在范围外时只需要进行合并或分离操作。

B树每个节点里面大概包含了：

  1. 节点当前子节点个数 k（范围预先确定，比如2-3树每个节点内部只能有2至3个子节点）
  2. 父节点指针
  3. k 个子节点指针
  4. k - 1 个键

1920pxBtree.svg.png

B树约束其叶子节点处在同一深度来保持平衡。如果一个节点处于一个磁盘块，B树的深度降低了，缩小了磁盘的读取次数，提高读取效率。并且平衡的操作次数也减小了。