一直以来对B-树的认识停留在它是一个平衡树，其变体被广泛应用在数据库系统仅此而已。今天花时间了解了一下它的特性和结构。

定义

既然说是平衡树，那么它自然就是一个树状结构。和以往的平衡二叉树/红黑树相比，它的每个节点可以有多个值，同时可以指向多个叶子结点。

#define ORDER 4
struct BTreeNode {
		int val[ORDER - 1];
		int count;		
		struct BTreeNode *link[ORDER];
}

代码中的ORDER，被翻译为阶数，它决定每个节点有多少个值和子节点。

那么对于任意非根节点：

• 最少有 ⌈ORDER/2⌉ - 1 个值（键）
• 最多有 ORDER - 1 个值（键）
• 子节点数量 = 值的数量 + 1 (和二叉树类似，B树里两个节点链接夹着一个值，因此有值数量+1的关系）

通常会根据磁盘块的大小来选择阶数，以便一个节点刚好能填满一个磁盘块。

同时节点的大小也有一些其他影响：

• 缓存效率：较大的节点可以减少I/O操作，但可能会影响缓存效率。
• 内存使用：较大的节点会占用更多内存。
• 操作复杂度：较大的节点可能会增加插入和删除操作的复杂度。

优点

先摘录一段经典的计算机延迟对比表

B-树最初被设计的目的就是为了在磁盘存储数据。因为它有更好的“局部性（locality)“:B树的每个节点有多个值，这些相邻的数据可以存储到连续的磁盘空间中。

正因为是连续的数据，所以读取时可以避免多次的磁盘寻道。（如表里记载，一次磁盘寻道需要8,000,000ns的时间）。同时，大节点结构允许在一次IO操作中批量读取多个数值，显著减少IO操作次数。

数据相邻存储的另一个好处是，现代操作系统 以页为单位管理数据，因此在读取某一数据时，有极大可能相邻数据也会被提前读取至内存中，这也间接提高了下次读取的效率，表现出更好的缓存命中率。

细节

• 磁盘页中除了相关节点的数据，也有额外meta数据，所以严格意义上节点内存大小并不是与磁盘页大小完全一样。
• B-树一个特性是要保证每个中间节点都至少要有[m/2]-1个值，也就是至少半满。
• 每个节点同时有数据和子树节点链接。这两个互相形成“交错”关系。

节点拆分

• 插入流程总会从根节点一路向下找到目标叶子节点
• 分裂节点：如果叶子节点已满，选择中间的键作为分割点，分出新的节点，并将中间值和新的节点插入到父节点
• 向上传播：如果父节点因为插入而变满，重复分裂过程，直到找到未满的节点或者到达根结点
• 创建新根（如果需要）：如果分裂一直传播到根结点，创建新的根结点，树的高度+1
• 也正因为是这个顺序，树可以保持平衡

扩展: B+树

虽然上面说B树广泛应用于数据库系统，但实际上在工业环境中更常用的是B+树。 B+树相比B树做了两个方面的改动（优化）:

1. B+树中间节点只保存key，不存具体记录。所有Data保存在底层的叶子节点。
2. 叶子节点通过双向链表串联在一起。

因为中间节点不保存数据，因此这些节点变得极其轻量，相同磁盘页中B+树可以保存更多的指针和键。

关系型数据库的核心是SQL查询，极其依赖“范围扫描”（Range Scan） 和 排序。所以B+树结构在这里有极大的优势。因此现在主流关系型数据都采用了B+树或者自己的变体。