B树、B+树详解

1.常见的搜索结构

以上结构适合用于数据量相对不是很大，能够一次性存放在内存中，进行数据查找的场景。如果
数据量很大，比如有100G数据，无法一次放进内存中，那就只能放在磁盘上了，如果放在磁盘
上，有需要搜索某些数据，那么如果处理呢？那么我们可以考虑将存放关键字及其映射的数据的
地址放到一个内存中的搜索树的节点中，那么要访问数据时，先取这个地址去磁盘访问数据。

使用平衡二叉树搜索树的缺陷：

 - 平衡二叉树搜索树的高度是logN，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，
访问磁盘速度很慢，在数据量很大时，logN次的磁盘访问，是一个难以接受的结果。

使用哈希表的缺陷：

 - 哈希表的效率很高是O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难
以接受的。

那如何加速对数据的访问呢？
1. 提高IO的速度（SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升）
2. 降低树的高度---多叉树平衡树

2.B树概念

B树是一种平衡的多叉树，核心目标是最小化磁盘 IO 次数，是数据库、文件系统索引的核心数据结构。

一棵M阶（M>=3）的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足以下性质：

1.根节点至少有两个孩子

2.分支节点组成：每个分支节点都包含k - 1个关键字和k个孩子，其中 ceil(M/2) ≤ k ≤ M（ceil是向上取整函数）；

3.叶子节点组成：每个叶子节点都包含k - 1个关键字，其中 ceil(M/2) ≤ k ≤ M；

4.有序性：每个节点内的键值按升序排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分；

5.平衡特性：所有叶子节点在同一层（保证查找路径长度一致，IO 次数固定）。

6. 每个结点的结构为：（n，A0，K1，A1，K2，A2，… ，Kn，An）其中，Ki（1≤ i ≤n）为关键
字，且Ki < Ki+1(1≤ i ≤n-1)。Ai（0≤ i ≤n）为指向子树根结点的指针。且 Ai 所指子树所有结点中的
关键字均小于Ki+1。n为结点中关键字的个数，满足ceil(M/2) - 1 ≤ k ≤ M - 1；

B树的节点组成如下：

键值数组：k₁ k₂ ... kₙ （n≤M-1） 子节点指针：p₀ p₁ ... pₙ （n+1≤M） 父节点指针：parent（可选，用于插入/删除）

键值数组：存储索引关键字（如数据库主键值、磁盘地址）；
子节点指针：指向子树的磁盘地址；
父节点指针：用于插入 / 删除时的向上分裂 / 合并操作。

3.B树的插入逻辑分析

3.1.B树的插入逻辑分析

假设M = 3，即三叉树，每个节点中存储两个数据，三个子节点，后续简单实现期间，节点的结构如下：

B 树插入操作的核心逻辑是节点分裂，完整流程如下：

1.触发条件：向节点插入新键值后，节点键值数达到M（超过最大容量M-1），分裂出一个兄弟节点；

2.中间位置计算：取mid = M / 2；

3.分裂规则：

 - 原节点保留[0, mid-1]范围的键值，以及[0, mid]范围的子节点；

 - 新建兄弟节点，将原节点[mid+1, M-1]范围的键值、[mid+1, M]的子节点移入；

 - 原节点的第mid个键值（中间键值）提升至父节点，作为父节点区分原节点与兄弟节点的分界键；兄弟节点作为父节点的新子节点，插入到中间键值的右侧；

上面三叉树之所以多创建一个键值和子节点，就是为了可以先插入在再分裂，避免分裂后再插入的复杂逻辑。

用序列{75，49，139，150，36，40，53，55，25，52，60}构建B树的过程如下：

（1）依次插入75、49、129

1.找到该元素应插入的位置。2.按照插入排序的思想将元素插入到合适位置。3.检查该节点是否满足B树的性质，满足则插入结束，不满足则对节点进行分裂。

此时该节点已满，触发分裂：1.找到节点的中间位置。2.给出一个新建点，将中间位置之后的数据搬到新节点。3.中间位置键值提升到父节点。4.将节点连接好。

B 树的插入严格遵循 “先查找，后插入” 的逻辑，从根节点开始，根据键值的有序关系向下遍历，直到确定插入位置。

（2）接着插入150，36，40

触发分裂，这里父节点移动的逻辑是：新提升上来的键值40，从序列末尾依次向前比较，当原键值较大时，原键值向后移动一个位置，同时右子节点也向右移动，新键值继续向前比较，直到比原键值大或到第一个位置，插入并且该插入位置的右子节点指向新分裂出发节点

void InsertKey(Node* node, const K& key, Node* child) { // 从后往前，依次判断应插入位置 int end = node->_n - 1; while (end >= 0 && key < node->_keys[end]) { node->_keys[end + 1] = node->_keys[end]; node->_subs[end + 2] = node->_subs[end + 1]; --end; } node->_keys[end + 1] = key; node->_subs[end + 2] = child; if (child) child->_parent = node; node->_n++; }

（3）插入53，55

叶子节点分裂得到如下结果

此时的根节点继续分裂

（4）插入25，52，60

插入过程总结：

1. 如果树为空，直接插入新节点中，该节点为树的根节点

2. 树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）

3. 检测是否找到插入位置（假设树中的key唯一，即该元素已经存在时则不插入）

4. 按照插入排序的思想将该元素插入到找到的节点中

5. 检测该节点是否满足B树的性质：即该节点中的元素个数是否等于M，如果小于则满足

6. 如果插入后节点不满足B树的性质，需要对该节点进行分裂：

 - 申请新节点

 - 找到该节点的中间位置

 - 将该节点中间位置右侧的元素以及其孩子搬移到新节点中

 - 将中间位置元素以及新节点往该节点的父节点中插入，将父节点作为新的插入节点，判断是否满足B树性质，重复过程6、7。

7. 如果向上已经分裂到根节点的位置，插入结束。

3.2.节点设计与性能分析

template<class K, size_t M> struct BTreeNode { // 为了方便先插入再分裂，多给一个空间 K _keys[M]; BTreeNode<K, M>* _subs[M+1]; BTreeNode<K, M>* _parent; size_t _n; // 记录有多少个关键字 BTreeNode() :_parent(nullptr) , _n(0) { for (int i = 0; i < M - 1; ++i) { _keys[i] = K(); _subs[i] = nullptr; } _subs[M - 1] = nullptr; } };

B树性能分析：

对于度为 M 的 B 树，因每个节点的子节点数介于⌈M/2⌉（即 M/2 向上取整）和 M 之间，树的高度范围为log_M N ~ log_{⌈M/2⌉} N，对应查找 / 插入操作的节点定位比较次数为log_{M-1} N ~ log_{M/2} N（节点内键值数为子节点数 - 1）；定位到目标节点后，可通过二分查找快速找到元素。B 树效率极高：以 620 亿个节点（N=62×10⁹）、度 M=1024 为例，log_{M/2} N ≤ 4，即仅需不到 4 次节点定位即可找到目标节点，大幅减少磁盘 IO 次数（磁盘 IO 的核心开销在于节点加载，而非节点内二分）。

3.3.删除逻辑简介

删除的核心规则：节点键值数低于最小值时，要么向兄弟节点 “借键”，要么与兄弟节点合并。节点空则合并 / 借键。

流程：

1.找到要删除的键值，若为非叶子节点：用 “后继键值”（右子树最小键值）替换该键值，转为删除后继键值（保证只删叶子节点）；

2.从叶子节点删除键值后，检查节点键值数：

 - 若≥最小值：删除完成；

 - 若 < 最小值：

         - 尝试向相邻节点 “借键”：父节点的一个键值下移，兄弟节点的一个键值上移（保持有序）；
         - 若兄弟节点也无键可借：与兄弟节点合并（父节点的一个键值下沉到合并节点）；

3.若父节点合并后键值数不足，重复上述流程（直到根节点）；

4.若根节点合并后无键值，删除根节点（树高 - 1）。

4.B+树简介

4.1.B+树性质

B + 树是 B 树的变形，是在 B 树基础上优化的多路平衡搜索树，B + 树的规则跟 B 树基本类似，但是又在 B 树的基础上做了以下几点改进优化：

1.分支节点的子树指针与关键字个数相同（相当于取消了B树最左边那个子树）。

2. 分支节点的子树指针 p [i] 指向关键字值大小在 [k [i], k [i+1]) 区间之间

3. 所有叶子节点增加一个链接指针链接在一起

4. 非叶子节点只存索引 key，不存数据；所有关键字及其映射的数据都存在叶子节点（聚簇索引叶子存整行数据，二级索引叶子存主键值）。

5. 分支节点跟叶子节点有重复的值，分支节点存的是叶子节点索引中的最小值。

6. 所有关键字都出现在叶子节点中，且链表中的节点是有序的。

4.2.B+树的分裂

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，中间关键字往上提，最后在父结点中增加新结点的指针；

B*树的分裂：
当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结
点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如
果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父
结点增加新结点的指针。
所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

通过以上介绍，大致将B树，B+树，B*树总结如下：

B树：有序数组+平衡多叉树；

B+树：有序数组链表+平衡多叉树；

B*树：一棵更丰满的，空间利用率更高的B+树。

5.B树的应用

5.1.MySQL索引简介

B树最常见的应用就是用来做索引。MySQL官方对索引的定义为：索引（index）是帮助MySQL高效获取数据的数据结构。

当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数
据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数
据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，
该数据结构就是索引。

MySQL是一个非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥
有灵活的插件式存储引擎，如下：

MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。 注意：索引是基于表的，而不是基于数据库的。

5.2.MyISAM

MyISAM引擎是MySQL5.5.8版本之前默认的存储引擎，不支持事物，支持全文检索，使用B+树
作为索引结构，叶节点的data域存放的是数据记录的地址，其结构如下：

在MyISAM中，主索引和辅助索引在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

5.3.InnoDB

InnoDB存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL数据库5.5.8版
本开始，InnoDB存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但
InnoDB使用B+树作为索引结构时，具体实现方式却与MyISAM截然不同：

1.InnoDB的数据文件本身就是索引文件。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB索引，表数据文件本身就是按B+树组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

上图是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录，
这种索引叫做聚簇索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有
主键（MyISAM可以没有），如果没有，则选择一个唯一非空索引，如果还没有，则使用自增ID（一个隐藏字段）作为聚簇索引。

2.InnoDB的辅助索引data域存储相应记录主键的值而不是地址，所有辅助索引都引用主键作为data域。

聚簇索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索可能需要检索两遍索引：首先检索辅助索引获得主键，如果使用辅助索引需要获得除主键外的其它字段值，则需要回表（使用主键值作为聚簇索引重新检索）。然

6.B树插入代码实现

// 找到应插入位置 pair<Node*, int> Find(const K& key) { Node* cur = _root, *parent = nullptr; while (cur) { int i = 0; while (i < cur->_n) { if (key < cur->_keys[i]) break; else if (key == cur->_keys[i]) return make_pair(cur, i); else ++i; } parent = cur; cur = cur->_subs[i]; } return make_pair(parent, -1); } // 插入键值 void InsertKey(Node* node, const K& key, Node* child) { // 从后往前，依次判断应插入位置 int end = node->_n - 1; while (end >= 0 && key < node->_keys[end]) { node->_keys[end + 1] = node->_keys[end]; node->_subs[end + 2] = node->_subs[end + 1]; --end; } node->_keys[end + 1] = key; node->_subs[end + 2] = child; if (child) child->_parent = node; node->_n++; } bool Insert(const K& key) { if (_root == nullptr) { _root = new Node; _root->_keys[0] = key; _root->_n++; return true; } // 判断key是否已存在 pair<Node*, int> ret = Find(key); if (ret.second >= 0) return false; // key不存在，find带回来要插入的那个节点 // 循环每次往parent插入 newkey和child Node* parent = ret.first; Node* child = nullptr; K newKey = key; while (1) { InsertKey(parent, newKey, child); //没有满，插入就结束了 if (parent->_n < M) { return true; } // 满了就要分裂出兄弟节点，并将中间值插入父节点 else { size_t mid = M / 2; Node* brother = new Node; size_t j = 0; size_t i = mid + 1; for (; i < M; ++i) { // 拷贝键值和左孩子到兄弟节点 brother->_keys[j] = parent->_keys[i]; brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) parent->_subs[i]->_parent = brother; ++j; //清除原节点 parent->_keys[i] = K(); parent->_subs[i] = nullptr; } // 还有最后一个右孩子 brother->_subs[j] = parent->_subs[i]; if (parent->_subs[i]) parent->_subs[i]->_parent = brother; parent->_subs[i] = nullptr; brother->_n = j; parent->_n -= j + 1; K midKey = parent->_keys[mid]; parent->_keys[mid] = K(); if (parent->_parent == nullptr) // 说明刚才分裂的是根节点 { _root = new Node; _root->_keys[0] = midKey; _root->_subs[0] = parent; _root->_subs[1] = brother; _root->_n = 1; parent->_parent = _root; brother->_parent = _root; break; } else { newKey = midKey; child = brother; parent = parent->_parent; } } } return true; }

// 中序遍历 void _InOrder(Node* cur) { if (cur == nullptr) return; // 左子 根 左子 根 ... 右 size_t i = 0; for (; i < cur->_n; ++i) { _InOrder(cur->_subs[i]); cout << cur->_keys[i] << " "; } // 最后的右子树 _InOrder(cur->_subs[i]); }