B类树

“To choose time is to save time.”

1. 前提概念

1.1 数据域

B类树的结点中有两个区域，一个是数据域，一个是指针域。

什么是数据域呢？

简单的说，B类树中每个结点存储数据的地方，我们就称之为数据域。
而数据域中存储的数据通常是一个个的键值对，键值对就分为键(key)和值(value)，这里通常称键为关键字，也通常会将关键字直接指代整个键值对。
站在数据库索引的角度，关键字就是用于建立索引的字段值，而对应的值就是该关键字所对应的目的数据，可以是主键信息，也可以是指向实际数据的地址，甚至是完整的一行数据。

那什么是指针域呢？

我们知道二叉树在代码的实现中，通常会有两个指针，既左孩子指针和右孩子指针。而这两个指针所在的区域，我们就称之为指针域
因为B类树并不是一棵二叉树，它是一棵多叉树。也就说明了，一棵B类树，可能有多个指针，每个的结点的所有的指针所在的区域就是我们说的指针域啦。概念都是一样的。

2. B树

B树，即B-树。需要强调的是它们两者都是同一种树，并非两种不一样的树。因为B树的英文名称为B-tree，-实际是杠的意思，但是也就不知怎么的B-tree就被翻译成为B-(减)树。

B树，又名B-树。它是一棵多路平衡多路查找树。

2.1 定义

一棵m阶B树的定义：

节点需要满足
1. 根节点至少有两个孩子节点
2. 树中每个节点最多有m个孩子节点(m>=2)
3. 除了根节点和叶子节点外，其他所有节点至少要有ceil(m/2)个孩子
4. 所有的叶子节点都位于同一层(平衡特性)
关键字需要满足：
- 假设每个非叶子节点中包含n个关键字信息，关键字以k表示，指针以p表示
  1. Ki(i = 1,…,n)某个非叶子节点的关键字，关键字需要满足升序序列排序，k(i-1) < k(i)
  2. 每个非叶子节点中的关键字个数n需要满足ceil(m/2) - 1 <= n <= m -1
  3. 非叶子节点的指针p[1]...p[m]中
  - 第一个指针，p[1]指向的孩子节点的所有关键字必然小于当前节点k[1]关键字
  - 最后一个指针，p[m]指向的孩子节点的所有关键字肯定大于当前节点k[m-1]关键字
  - 其他p[i]指向孩子节点的所有关键字必然在当前节点(k[i-1],k[i])的开区间范围内

简单通俗地来解释一下：

m就是几阶的含义，m取决节点的容量和相关配置。3阶B树的每个结点分叉树最多为3，最多3个孩子节点
ceil函数是向上取整的意思，非四舍五入，例如ceil(1.5) = 2,ceil(1.2) = 2
关键字定义(2)的意思可以通俗地理解为，每个非叶子结点的关键字个数肯定小于该节点能拥有的孩子节点数，最多就存储m-1个关键字，最少也要存储ceil(m/2)-1个。
关键字定义(3)的意思是某节点最左孩子节点的所有关键字肯定小于当前节点最左关键字的值，就像下图中的3,5肯定小于8
最右孩子节点的所有关键字肯定大于当前节点的最右关键字；例如下图中的13肯定大于12和8
而中间孩子节点的所有关键字肯定满足与一个当前节点的关键字的开区间范围(k[i-1],k[i])，例如下图的p2孩子节点的关键字9肯定位于(8,12)关键字之间。

三阶B树

总之，我们大致的知道，B树并不是一棵二叉搜索树，而是一颗具有平衡性质的多路查找树。同时B树的定义比较复杂，具有指针域和关键字域的概念，一个结点可以存储多个数据元素，上一段是对结点定义约束，下一段是对结点内部所存储的关键字的约束。

2.2 特性

关键字集合分布在整个树中
任何一个关键字出现且只出现在一个节点中
搜索有可能在非叶子节点约束
B树的查找性能基本等价于平衡二叉树的二分查找(不考虑IO的情况下)
可以实现自平衡，让所有叶子节点都在同一个层级

2.3 B树的高

现在有一个问题，关键字总数为n的m阶B树的高是多少？

B树的高

既底数是ceil(m/2)，最后的对数结果 + 1就是这颗B树的高

3. B+树

B+树是一种树型数据结构，通常用于数据库和操作系统的文件系统中。B+树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+树元素自底向上插入，这与二叉树恰好相反。

3.1 定义

B+树是B树的变种，其定义基本与B树相同，除了：

非叶子节点的子树指针与关键字个数相同，不像B树的关键字树要少于指针数
非叶子节点的子树指针p[i]所指向的孩子节点的所有关键字处于当前节点关键字[k[i],k[i+1])左闭右开的范围区间内
所有的非叶子节点的关键字，都会继承至其中孩子节点中，是其孩子节点元素的最大值或者最小值
非叶子节点仅用来索引，数据都保存在叶子节点中
所有叶子节点的数据均有两个链指针分别指向上一个数据和下一个数据，构成双向链表。

3阶B+树

B树和B+树的区别

B+树，不同于B树的是，所有数据都存储在叶子结点中，非叶子结点不存储任何数据，仅仅是一个索引值。所以B+树查找的时间复杂度非常稳定，都是从根遍历到叶子结点，不会在非叶子结点上中断。

3.2 B+树最小特性

因为B+树的定义中，所有的非叶子结点的关键字，都会继承至其中孩子结点中，是其孩子结点元素的最大值或最小值，所以就造成了一个特性，根结点的最小值，可能是整棵树的最小值。根结点的最大值可能是整棵树的最大值。

B+树最小值

B+树最大值

3.3 为什么B+树会替代B树？

总之呢，在数据库索引，文件系统等许多场景中，B+树逐渐替代B树，这是为什么呢？

1.B+树的磁盘读写代价更低

因为B+树的中间结点存储的都是索引数据，仅仅是一个地址，并非直接的数据，所以同一个结点中（同一个磁盘页大小），B+树可容纳的关键字数会比B树更多（因为一个简单的地址几乎肯定小于一个直接的数据）。所以同样的数据量下，B+树会比B树更加“矮胖”，树高更小，所以查询时需要的IO次数就更少。

2.B+树的查询效率更加稳定

因为B+树的所有元素都存储在叶子结点中，而叶子结点都属于同一层级，每一个B+树查询都是从根结点遍历到叶子结点的过程，所以不管查询什么，时间复杂度相比B树查询都更加的稳定和近似。

3.B+树更有利对数据的扫描

B树中虽然解决了查询的效率，但是如果需要查询一串相邻的数值，有可能需要回溯来回扫描或是从根结点多次中序遍历。而B+树的所有元素都存储叶子结点，每个叶子结点都有指向下一个结点的指针，直接线性遍历即可。同样B+树也更加的利于做范围查询。

参考文章

初入数据结构中的B类树（B Tree , B+ Tree）

3.4 为什么在数据库领域使用B类树来替代平衡二叉树成为索引？

B类树的一个结点可以存储多个数据，可以有多个分支，所以可以大大的降低正棵树的高度，减少磁盘IO操作
B类树的一个结点可以存储多个数据的特点，恰好也符合了磁盘的物理构造特性，通过将一个结点最多存储对应一个物理盘块的数据，让同结点数据进行线性遍历时，不需要跨盘块进行查询，同样也减少了磁盘查询时间。

"B类树总结(B Tree, B+ Tree)"