Mysql 中的 B+树 和 B 树在进行数据增删改查后的结构调整过程是怎样的？

B+ 树的增、删、改、查数据的调整过程

在 MySQL 中，B+ 树 是一种广泛用于存储引擎（如 InnoDB）中的索引结构。B+ 树的结构使得它非常适合于处理大量数据的插入、删除和查询等操作。B+ 树是一种自平衡的树数据结构，其中所有的值都存储在叶子节点中，内部节点则只存储索引信息。

1. 查询操作（查）

查询是 B+ 树最常见的操作。B+ 树查询通过以下几个步骤完成：

• 从根节点开始查找：查询从根节点开始，逐层向下寻找，直到叶子节点。
• 通过比较键值：每个节点（非叶子节点）都包含多个键值，查询时通过与键值的比较，决定进入哪个子树，直到进入叶子节点。
• 叶子节点存储数据：叶子节点存储了实际的数据记录，查询到叶子节点后，可以直接找到对应的记录。

B+树查询的特点：

• B+树是一个有序树，叶子节点按照顺序链接在一起，因此可以进行高效的范围查询（例如 BETWEEN 或 LIKE）。
• 查询过程的复杂度是 O(log n)，因为 B+树是一棵平衡树，每次查询都能减少一半的搜索范围。

2. 插入操作（增）

在 B+树中插入数据时，过程相对复杂，可能会触发节点的分裂，甚至导致树的高度增加。插入过程的基本步骤如下：

• 查找插入位置：首先，按照与查询操作相同的方式，找到插入数据的叶子节点。

• 插入数据到叶子节点：如果该叶子节点还有空间容纳新插入的数据，就直接插入。叶子节点通常按顺序存储数据，所以新数据会插入到正确的位置。

• 叶子节点溢出：如果叶子节点满了（超过了预设的容量），就需要进行分裂。分裂过程如下：

  • 将叶子节点的中间数据值上升到父节点。
  • 将叶子节点一分为二，左侧包含较小的一半数据，右侧包含较大的一半数据。
  • 如果父节点也满了，会继续分裂父节点。
  • 如果父节点已经满了，需要递归地分裂父节点，直到找到不满的父节点或者分裂到根节点。若根节点分裂，则会增加树的高度。

• 树的高度可能增加：在插入过程中，若分裂操作一直向上传播到根节点，根节点分裂时树的高度会增加。此时，B+树的根节点会变成一个新的内部节点，树的高度会增加 1。

插入总结：

• 插入时从根节点开始，找到叶子节点插入数据。
• 如果叶子节点已满，进行分裂，可能会引起父节点的分裂，甚至根节点的分裂，最终可能导致树的高度增加。
• 插入操作的平均时间复杂度为 O(log n)。

3. 删除操作（删）

删除数据时，B+树也需要处理节点的合并和重新平衡。删除的过程如下：

• 查找要删除的数据：首先根据查询操作，找到需要删除的数据所在的叶子节点。

• 删除数据：如果要删除的数据存在于叶子节点且该叶子节点的剩余空间大于最小要求，则直接删除该数据。

• 节点合并或借位：

  • 如果删除数据后，叶子节点的键值数量少于最小要求（通常是 ⌈m/2⌉，其中 m 为节点的最大容量），则会尝试与相邻的兄弟节点合并。
  • 如果兄弟节点也无法合并，就会将父节点中相应的索引键值下移，进行“借位”操作，从而确保叶子节点保持平衡。
  • 合并或借位的操作会沿着树的路径向上进行，直到合适的位置或者根节点。此时如果根节点被合并，树的高度会减少。

• 树的高度可能减少：当根节点的子树被合并后，如果根节点的子树数目减少了，B+树的高度会减少。

删除总结：

• 删除过程类似于插入过程，首先找到叶子节点，并删除数据。
• 如果叶子节点的数据不足以满足最小要求，B+树会通过合并或借位操作重新平衡。
• 删除操作的平均时间复杂度为 O(log n)。

4. 更新操作（改）

更新操作包括删除和插入两个步骤。对于 B+树中的更新操作，通常涉及以下过程：

• 查找要更新的记录：首先查找要更新的记录。
• 删除旧数据：然后删除旧的数据（这会触发删除过程）。
• 插入新数据：最后插入更新后的数据（这会触发插入过程）。

由于 B+树的插入和删除本身就会触发节点的分裂和合并，因此更新操作的过程也是通过插入和删除来调整树的结构。

更新总结：

• 更新操作本质上是先删除旧数据，再插入新数据。
• 删除和插入过程可能引起节点的分裂和合并，因此更新操作可能导致树的重新平衡。

总结：B+树增删改查的调整过程

• 查询（查）：从根节点开始，逐层查找，直到叶子节点，时间复杂度为 O(log n)。
• 插入（增）：查找插入位置，如果叶子节点满了，进行分裂，分裂可能导致父节点分裂，甚至增加树的高度，时间复杂度为 O(log n)。
• 删除（删）：删除数据后，如果叶子节点的数据量小于最小要求，则进行合并或借位，可能导致树的高度减少，时间复杂度为 O(log n)。
• 更新（改）：更新数据等价于删除旧数据并插入新数据，包含插入和删除的调整过程。

B+树的调整过程，尤其是插入和删除操作，会引起节点的分裂和合并，通过这些机制，B+树能够保持平衡，并确保操作的效率。

B 树的增、删、改、查数据的调整过程

在 B树 中，增、删、改、查数据时的调整过程与 B+树 有相似之处，但也有一些关键的区别。B树和B+树的主要区别在于 B树的内部节点也存储数据，而 B+树的内部节点只存储索引。以下是关于 B树 的增、删、改、查操作的详细调整过程。

1. 查询操作（查）

查询操作在 B树中的基本过程如下：

• 从根节点开始查找：与 B+树类似，B树在进行查询时，从根节点开始，逐层比较，判断应该进入哪个子节点，直到最终找到目标数据或者确定数据不存在。
• 节点结构：B树的每个节点都存储键值，并且每个节点内可能有多个子节点。查询时会与节点内的键值进行比较，并选择合适的子节点继续查找。每个节点的键值都是有序的，查找效率很高。
• 查询过程：
  1. 从根节点开始。
  2. 根据查询的键值，比较该键值与当前节点内的键值，并决定向左、右子树或者中间子树递归查找。
  3. 直到找到叶子节点，叶子节点包含实际数据（数据存储在叶子节点和内部节点中）。

B树的查询操作是非常高效的，其时间复杂度是 O(log n)，这与树的高度成正比。

2. 插入操作（增）

在 B树中插入数据时，主要有以下几个步骤：

1. 查找插入位置：
   • 插入操作首先会根据查询过程查找插入数据的正确位置。找到该位置之后，数据将被插入到目标节点的适当位置。由于 B 树的节点是有序的，插入的数据会保持该节点内的键值有序。
2. 插入到节点：
   • 如果目标节点内有足够的空间容纳新数据（即节点的键数未达到最大值），则直接将数据插入该节点。
3. 节点溢出：
   • 如果插入数据后，节点的键值数量超出了该节点的最大容量（一般是 m 个键），则会触发 节点分裂。
   • 分裂过程如下：
     • 将节点内的键值分成两部分，左侧的部分保留在原节点，右侧的部分会移动到新节点。
     • 然后，中间的键值会被提升到父节点中。
   • 如果父节点也因提升的键值而超出容量，会继续进行 递归分裂，直到找到一个父节点不满的位置。如果分裂一直向上传播到根节点，根节点也会分裂，从而 增加树的高度。
4. 树的高度增加：
   • 当根节点分裂时，B树的高度会增加 1，新的根节点会包含一个新的子节点。

总结：

• 插入操作首先查找插入位置，然后插入数据。如果节点满了，进行节点分裂，可能会向上递归分裂父节点，最终可能增加树的高度。
• 插入操作的时间复杂度为 O(log n)。

3. 删除操作（删）

在 B树中删除数据时，也需要保证树的平衡性。删除的过程如下：

1. 查找要删除的数据：
   • 首先，根据查询操作找到要删除的目标数据的位置。
2. 直接删除数据：
   • 如果目标数据在叶子节点，并且删除后节点的键数依然满足最小要求（例如，不少于 ⌈m/2⌉ 个键），则直接删除该数据。
3. 节点不足情况：
   • 如果删除数据后，节点内的键数少于最小要求，则需要 合并 或 借位 来恢复平衡。
   • 借位：如果相邻的兄弟节点有足够的键值，可以借一个键值过来填补当前节点。
   • 合并：如果相邻的兄弟节点无法借位，当前节点与相邻的兄弟节点会合并。合并时，父节点中与当前节点相关的键值也会被删除，可能会导致父节点的键数不足。
4. 父节点调整：
   • 如果父节点因为删除键值而导致其键数也不足，需要对父节点进行借位或合并操作。这个调整过程会递归向上进行，直到根节点。
5. 树的高度减少：
   • 如果根节点的子节点减少到 1（即合并后只剩一个子节点），则根节点被删除，树的高度会减少 1。

总结：

• 删除操作可能会触发节点合并或借位，可能会递归影响父节点，最终减少树的高度。
• 删除操作的时间复杂度为 O(log n)。

4. 更新操作（改）

B树中的更新操作本质上是 删除旧数据并插入新数据 的组合过程。步骤如下：

1. 查找更新位置：
   • 首先，使用查询操作找到要更新的数据的当前位置。
2. 删除旧数据：
   • 然后，按照删除操作删除旧的数据。如果删除后节点不足，需要进行节点合并或借位的调整。
3. 插入新数据：
   • 最后，插入新的数据。插入操作会引发节点分裂（如果节点满了），并可能导致树的高度增加。

总结：

• 更新操作等价于删除旧数据并插入新数据，可能引发节点的分裂、合并或借位操作，最终影响树的结构。

总结：B树增、删、改、查的调整过程

• 查询（查）：从根节点开始查找，逐层向下查找直到叶子节点，时间复杂度为 O(log n)。
• 插入（增）：查找插入位置并插入数据，若节点满了，则进行分裂，分裂可能会递归到父节点，最终可能增加树的高度。时间复杂度为 O(log n)。
• 删除（删）：删除数据并进行节点合并或借位，可能会递归影响父节点，最终减少树的高度。时间复杂度为 O(log n)。
• 更新（改）：更新操作本质上是删除并插入数据，可能引发节点分裂或合并。时间复杂度为 O(log n)。

B树的自平衡机制保证了操作的效率，因此 B树非常适合高效存储和检索大规模数据。