B 树与 B+ 树详解及数据库索引应用

1.常见的搜索结构

种类	数据格式	时间复杂度
顺序查找	无要求	O(N)
二分查找	有序	O(logN)
二叉搜索树	无要求	O(N)
二叉平衡树 (AVL 树和红黑树)	无要求	O(logN)
哈希	无要求	O(1)

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

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

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

使用哈希表的缺陷：

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

那如何加速对数据的访问呢？

提高 IO 的速度（SSD 相比传统机械硬盘快了不少，但是还是没有得到本质性的提升）
降低树的高度---多叉树平衡树

2.B 树概念

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

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

根节点至少有两个孩子
分支节点组成：每个分支节点都包含k - 1 个关键字和k 个孩子，其中 ceil(M/2) ≤ k ≤ M（ceil 是向上取整函数）；
叶子节点组成：每个叶子节点都包含k - 1 个关键字，其中 ceil(M/2) ≤ k ≤ M；
有序性：每个节点内的键值按升序排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域划分；
平衡特性：所有叶子节点在同一层（保证查找路径长度一致，IO 次数固定）。
每个结点的结构为：（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 树插入操作的核心逻辑是节点分裂，完整流程如下：

触发条件：向节点插入新键值后，节点键值数达到 M（超过最大容量 M-1），分裂出一个兄弟节点；
中间位置计算：取mid = M / 2；
分裂规则：
- 原节点保留 [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

文章配图

找到该元素应插入的位置。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

文章配图

插入过程总结：

如果树为空，直接插入新节点中，该节点为树的根节点
树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）
检测是否找到插入位置（假设树中的 key 唯一，即该元素已经存在时则不插入）
按照插入排序的思想将该元素插入到找到的节点中
检测该节点是否满足 B 树的性质：即该节点中的元素个数是否等于 M，如果小于则满足
如果插入后节点不满足 B 树的性质，需要对该节点进行分裂：
- 申请新节点
- 找到该节点的中间位置
- 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
- 将中间位置元素以及新节点往该节点的父节点中插入，将父节点作为新的插入节点，判断是否满足 B 树性质，重复过程 6、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）。

4.B+ 树简介

4.1.B+ 树性质

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

分支节点的子树指针与关键字个数相同（相当于取消了 B 树最左边那个子树）。
分支节点的子树指针 p [i] 指向关键字值大小在 [k [i], k [i+1]) 区间之间
所有叶子节点增加一个链接指针链接在一起

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 截然不同：

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

文章配图

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

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]); }

1.常见的搜索结构

种类	数据格式	时间复杂度
顺序查找	无要求	O(N)
二分查找	有序	O(logN)
二叉搜索树	无要求	O(N)
二叉平衡树 (AVL 树和红黑树)	无要求	O(logN)
哈希	无要求	O(1)

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

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

使用哈希表的缺陷：

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

那如何加速对数据的访问呢？

提高 IO 的速度（SSD 相比传统机械硬盘快了不少，但是还是没有得到本质性的提升）
降低树的高度---多叉树平衡树

2.B 树概念

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

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

根节点至少有两个孩子
分支节点组成：每个分支节点都包含k - 1 个关键字和k 个孩子，其中 ceil(M/2) ≤ k ≤ M（ceil 是向上取整函数）；
叶子节点组成：每个叶子节点都包含k - 1 个关键字，其中 ceil(M/2) ≤ k ≤ M；
有序性：每个节点内的键值按升序排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域划分；
平衡特性：所有叶子节点在同一层（保证查找路径长度一致，IO 次数固定）。
每个结点的结构为：（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 树插入操作的核心逻辑是节点分裂，完整流程如下：

触发条件：向节点插入新键值后，节点键值数达到 M（超过最大容量 M-1），分裂出一个兄弟节点；
中间位置计算：取mid = M / 2；
分裂规则：
- 原节点保留 [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

文章配图

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

文章配图

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

（2）接着插入 150，36，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

文章配图

插入过程总结：

如果树为空，直接插入新节点中，该节点为树的根节点
树非空，找待插入元素在树中的插入位置（注意：找到的插入节点位置一定在叶子节点中）
检测是否找到插入位置（假设树中的 key 唯一，即该元素已经存在时则不插入）
按照插入排序的思想将该元素插入到找到的节点中
检测该节点是否满足 B 树的性质：即该节点中的元素个数是否等于 M，如果小于则满足
如果插入后节点不满足 B 树的性质，需要对该节点进行分裂：
- 申请新节点
- 找到该节点的中间位置
- 将该节点中间位置右侧的元素以及其孩子搬移到新节点中
- 将中间位置元素以及新节点往该节点的父节点中插入，将父节点作为新的插入节点，判断是否满足 B 树性质，重复过程 6、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 树性能分析：

3.3.删除逻辑简介

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

流程：

找到要删除的键值，若为非叶子节点：用'后继键值'（右子树最小键值）替换该键值，转为删除后继键值（保证只删叶子节点）；
从叶子节点删除键值后，检查节点键值数：
- 若≥最小值：删除完成；
- 若 < 最小值：
  - 尝试向相邻节点'借键'：父节点的一个键值下移，兄弟节点的一个键值上移（保持有序）；
  - 若兄弟节点也无键可借：与兄弟节点合并（父节点的一个键值下沉到合并节点）；
若父节点合并后键值数不足，重复上述流程（直到根节点）；
若根节点合并后无键值，删除根节点（树高 - 1）。

4.B+ 树简介

4.1.B+ 树性质

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

分支节点的子树指针与关键字个数相同（相当于取消了 B 树最左边那个子树）。
分支节点的子树指针 p [i] 指向关键字值大小在 [k [i], k [i+1]) 区间之间
所有叶子节点增加一个链接指针链接在一起

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

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

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

4.2.B+ 树的分裂

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

文章配图

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

B 树：有序数组 + 平衡多叉树； B+ 树：有序数组链表 + 平衡多叉树； B*树：一棵更丰满的，空间利用率更高的 B+ 树。

5.B 树的应用

5.1.MySQL 索引简介

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

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

文章配图

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

5.2.MyISAM

文章配图

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

5.3.InnoDB

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

文章配图

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]); }

B 树与 B+ 树详解及数据库索引应用

1.常见的搜索结构

2.B 树概念

3.B 树的插入逻辑分析

3.1.B 树的插入逻辑分析

3.2.节点设计与性能分析

3.3.删除逻辑简介

4.B+ 树简介

4.1.B+ 树性质

4.2.B+ 树的分裂

5.B 树的应用

5.1.MySQL 索引简介

5.2.MyISAM

5.3.InnoDB

6.B 树插入代码实现

B 树与 B+ 树详解及数据库索引应用

1.常见的搜索结构

2.B 树概念

3.B 树的插入逻辑分析

3.1.B 树的插入逻辑分析

3.2.节点设计与性能分析

3.3.删除逻辑简介

4.B+ 树简介

4.1.B+ 树性质

4.2.B+ 树的分裂

5.B 树的应用

5.1.MySQL 索引简介

5.2.MyISAM

5.3.InnoDB

6.B 树插入代码实现

更多推荐文章

相关免费在线工具

更多推荐文章

相关免费在线工具

B 树与 B+ 树详解及数据库索引应用

1.常见的搜索结构

2.B 树概念

3.B 树的插入逻辑分析

3.1.B 树的插入逻辑分析

3.2.节点设计与性能分析

3.3.删除逻辑简介

4.B+ 树简介

4.1.B+ 树性质

4.2.B+ 树的分裂

5.B 树的应用

5.1.MySQL 索引简介

5.2.MyISAM

5.3.InnoDB

6.B 树插入代码实现

B 树与 B+ 树详解及数据库索引应用

1.常见的搜索结构

2.B 树概念

3.B 树的插入逻辑分析

3.1.B 树的插入逻辑分析

3.2.节点设计与性能分析

3.3.删除逻辑简介

4.B+ 树简介

4.1.B+ 树性质

4.2.B+ 树的分裂

5.B 树的应用

5.1.MySQL 索引简介

5.2.MyISAM

5.3.InnoDB

6.B 树插入代码实现

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具

微信扫一扫，关注极客日志

更多推荐文章

相关免费在线工具