Mysql--技术文档--B树-数据结构的认知

阿丹解读：

        B+树（B+ tree）和B树（B-tree）都是常见的自平衡搜索树数据结构，用于在存储和检索大量数据时提供高效的操作。

基本概念-B+树/B树

B树（B-tree）和B+树（B+ tree）是常见的自平衡搜索树数据结构，用于在存储和检索大量数据时提供高效的操作。它们具有一些共同的基本概念：

1. 节点（Node）：B树和B+树的数据存储在节点中。节点可以包含多个关键字和对应的指针。在B树中，叶子节点和内部节点的结构相同，都存储数据和关键字。而在B+树中，叶子节点只存储关键字和指向数据的指针，而内部节点存储关键字和指向子节点的指针。

2. 关键字（Key）：关键字是B树和B+树中用于对数据进行排序和搜索的值。关键字按照升序排列，并被存储在节点中。

3. 指针（Pointer）：指针用于连接节点，形成树的结构。在B树和B+树中，指针可以指向子节点、父节点或兄弟节点，实现树的平衡。

4. 根节点（Root Node）：根节点是B树和B+树的顶层节点。它是树的起点，通过根节点可以访问到整个树的结构。

5. 叶节点（Leaf Node）：叶节点是树的最底层节点。在B树中，叶节点存储数据和关键字。而在B+树中，叶节点只存储关键字和指向数据的指针。叶节点之间通过指针进行连接，形成一个有序的双向链表。

6. 内部节点（Internal Node）：内部节点是B树和B+树中非叶节点。它们用于指向子节点，并存储关键字。

B树和B+树作为自平衡的搜索树，具有增删改查的操作，每次操作后都会进行平衡以保持树的高度接近最小值。这样可以确保查询效率的稳定性，并提供高效的范围查询和区间搜索能力。

以上是B树和B+树的基本概念，它们在实际应用中有着广泛的应用，尤其在数据库和文件系统中用于管理和查找大量数据。

B树

B树（B-tree）是一种自平衡的搜索树数据结构，被广泛应用于数据库和文件系统等领域。它具有高效的查找、插入和删除操作，适合在磁盘上存储和检索大量数据。

B树的工作原理如下：

1. 根节点：B树的顶层节点称为根节点。根节点可以有多个子节点，且关键字的数量和子节点的数量相等。

2. 关键字有序存储：在B树中，节点内的关键字按照升序排列，并且关键字的数量决定了节点的最大容量。

3. 节点分裂：当往一个节点插入关键字时，如果节点已满，将会进行分裂。分裂会将关键字分为两部分，并生成两个新节点。

4. 子节点指针：除了关键字，节点还会存储指向子节点的指针。子节点指针的数量比关键字的数量多一个。

通过上述原理，B树可以实现快速的查找、插入和删除操作。

B树的性能优点包括：

1. 减少磁盘访问：B树的节点尺寸一般较大，可以容纳更多的关键字。这样可以减少磁盘IO的次数，提高数据读写的效率。

2. 平衡性：B树会在插入和删除操作后进行节点的自平衡，使树的高度保持相对较小。这样可以保持查询效率的稳定性。

3. 范围查询：由于B树中的关键字有序存储，范围查询和区间搜索变得高效。可以通过节点的查找和遍历实现范围查询。

4. 适应多层存储：B树的设计使其适用于多层存储系统，如内存和磁盘。节点的容量可以根据不同层级的存储进行调整，适应不同的场景。

需要注意的是，B树的具体性能表现会受到节点容量、节点分裂策略和具体实现等因素的影响。在实际应用中，可以根据具体的需求和场景选择合适的B树参数和配置，以获得更好的性能和效果。

B树的复杂度

	平均	最差
空间复杂度	O(n)	O(n)
搜索	O(log n)	O(log n)
插入	O(log n)	O(log n)
删除	O(log n)	O(log n)

B树工作流程

提供一个网址可手动看见树的工作流程

B-Tree Visualization

流程图

 详解工作流程

查找

流程描述：

1. 从根节点开始，在当前节点中查找是否存在目标关键字。如果存在，查找成功并返回相应的数据。

2. 如果目标关键字小于当前节点的最小关键字，则转到该节点的最左子节点进行下一步查找。

3. 如果目标关键字大于当前节点的最大关键字，则转到该节点的最右子节点进行下一步查找。

4. 如果目标关键字在当前节点关键字的范围内（大于等于最小关键字且小于等于最大关键字），则根据关键字的大小选择合适的子节点，并进入下一层继续查找。

5. 重复以上步骤，直到在某个叶子节点中找到目标关键字，或者在某个节点中无法找到目标关键字。

图示流程：

插入

插入代码需要根据具体情况来进行拆分

单层容量满需要分裂

当插入元素后发现元素已经超过了阶数，则需要向上拆分

在B树中，当插入元素导致某层节点的容量已满时，需要进行节点的分裂操作。分裂操作会将该节点的关键字分为两部分，并生成两个新节点。拆分的规则如下：

1. 拆分关键字：假设插入前节点中的关键字按升序排列，在容量已满的节点中，将关键字分为两部分。前一部分的关键字留在原节点，后一部分的关键字移至新节点。通常，中间位置的关键字作为拆分点，可以平均分配关键字给两个新节点。

2. 更新指针：拆分节点后，需要更新相关的指针。对于内部节点，拆分后，新节点的关键字会大于原节点中的所有关键字，将新节点的指针链接到原节点的右侧。对于叶子节点，拆分后，新节点将成为原节点的右兄弟节点，并与原节点进行指针连接。

3. 提升拆分点：当拆分点是根节点中的关键字时，拆分后的两个新节点会成为新的根节点，原根节点的指针指向这两个新节点。

通过上述规则，B树在容量已满时进行节点的分裂，以维持树的平衡性。拆分后，树的高度可能增加，但通过平衡操作可以保持树的高度接近最小值。

多层容量满需要分裂

当多层层次的节点容量满时，B树在插入操作时的流程如下：

1. 从根节点开始，在当前节点中查找插入位置。如果要插入的关键字已经存在，可能会更新相应的数据，否则，将关键字插入到当前节点。

2. 如果当前节点已满，进行节点的分裂操作。拆分的规则如前面所述，将关键字分为两部分，并生成两个新节点。对于内部节点，拆分后，新节点的关键字会大于原节点中的所有关键字，将新节点插入到原节点父节点的相应位置。对于叶子节点，拆分后，新节点将成为原节点的右兄弟节点，并进行指针的连接。

3. 分裂操作可能会导致上层节点容量变满，需要再次进行分裂。如果分裂的节点是根节点，将生成新的根节点，并将原根节点作为新根节点的子节点。

4. 重复以上步骤，不断向上进行节点的分裂操作，直到遇到非满节点或者根节点。

5. 如果根节点满了，进行根节点的分裂，并生成新的根节点。根节点分裂会导致B树的高度增加，但也保持了树的平衡。

重点：从顶向下进行分裂！！！

整体插入流程图

 删除

删除有两个相关的基本操作：合并和填充

合并操作：是值将两个子节点合并为一个子节点；

填充操作：指删除元素后，当一个节点中元素个数小于最小元素个数时，需要向此节点中填充元素。在填充操作的时候需要调用合并操作。

合并操作流程：

1. 找到需要合并的两个相邻子节点。

2. 选择一个关键字从父节点中下来填充合并后的子节点。这个关键字可以是两个相邻子节点之间的父节点关键字，或者是子节点中的一个关键字。

3. 将两个子节点中的关键字和指针合并到一个新的子节点中。合并后的子节点将成为原两个子节点的父节点连接的子节点。

4. 更新父节点的关键字和指针，将被合并的子节点移除，并将合并后的子节点添加到父节点中。

5. 如果父节点关键字数量小于最小关键字数量，可能需要继续进行合并操作，直到满足平衡条件。

通过合并操作，B树可以保持平衡性，并保证树的高度接近最小值。当删除一个关键字导致节点关键字数量不满足要求时，合并操作可以将多个子节点合并为一个节点，减少节点数量以提高空间利用率。

图示：

 删除操作流程：

B树的删除工作流程如下：

1. 从根节点开始，在当前节点中查找要删除的关键字。如果关键字存在于当前节点，则执行删除操作。

2. 如果要删除的关键字在当前节点中不存在，根据关键字的大小选择合适的子节点，并进入下一层继续查找与删除操作。

3. 如果要删除的关键字在叶子节点中找到，直接删除该关键字。

4. 如果要删除的关键字在内部节点中找到，则可以选择使用前驱或后继关键字代替要删除的关键字。一般情况下，选择后继关键字进行替换。

5. 如果替换后的关键字所在的节点关键字数量小于最小关键字数量，则可能需要进行合并和填充操作，以保持树的平衡。

6. 合并操作：如果替换后的关键字所在的节点的兄弟节点关键字数量大于最小关键字数量，可以选择从兄弟节点中借一个关键字过来，或者进行合并操作。

7. 填充操作：如果替换后的关键字所在的节点的兄弟节点关键字数量也小于等于最小关键字数量，则可能需要进行填充操作。填充操作可能需要借一个关键字过来，或者通过合并操作将当前节点与兄弟节点合并。

8. 重复以上步骤，直到在某个叶子节点中找到要删除的关键字，或者确定不存在要删除的关键字。

通过上述流程，B树可以实现删除操作，并保持树的平衡和性能。删除操作可能会触发合并和填充操作，以优化节点的利用率和树的结构。需要注意的是，B树的删除操作可以涉及多次的合并和填充操作，以保持树的平衡。

重点概念与流程：

合并操作：

在B树中，合并操作是指将两个子节点合并为一个子节点的操作。当一个节点中的关键字数量小于最小关键字数量时，可以执行合并操作。

合并操作的工作流程如下：

1. 找到需要合并的两个相邻子节点。

2. 选择一个关键字从父节点中下来填充合并后的子节点。这个关键字可以是两个相邻子节点之间的父节点关键字，或者是子节点中的一个关键字。

3. 将两个子节点中的关键字和指针合并到一个新的子节点中。合并后的子节点将成为原两个子节点的父节点连接的子节点。

4. 更新父节点的关键字和指针，将被合并的子节点移除，并将合并后的子节点添加到父节点中。

5. 如果父节点关键字数量小于最小关键字数量，可能需要继续进行合并操作，直到满足平衡条件。

通过合并操作，B树可以保持平衡性，并保证树的高度接近最小值。当删除一个关键字导致节点关键字数量不满足要求时，合并操作可以将多个子节点合并为一个节点，减少节点数量以提高空间利用率。

合并策略：

在B树中，合并操作的合并策略通常有以下几种：

1. 左兄弟合并：首先尝试将当前节点与其左兄弟节点进行合并。合并后，当前节点的关键字会被移动到左兄弟节点，并与左兄弟节点的关键字合并。这种合并策略会保持原有节点的顺序性。

2. 右兄弟合并：如果左兄弟合并失败或左兄弟节点不存在，可以尝试将当前节点与其右兄弟节点进行合并。合并后，当前节点的关键字会被移动到右兄弟节点，并与右兄弟节点的关键字合并。这种合并策略同样会保持原有节点的顺序性。

3. 中间位置合并：如果左兄弟合并和右兄弟合并都失败或兄弟节点不存在，可以考虑合并两个相邻的子节点中的中间位置的关键字。该关键字可以是父节点关键字中的一个，或者是两个子节点中的某个关键字。此合并策略可能会调整节点的顺序性，因为中间关键字可能会被移动到新的合并节点中。

通过以上合并策略，可以选择合适的方式将两个子节点合并为一个节点。合并操作会减少B树中的节点数量以提高空间利用率，同时还有助于保持树的平衡性。

B树的默认合并策略通常会优先选择左兄弟合并或右兄弟合并

填充操作：

填充操作的流程如下：

1. 在进行填充操作之前，需要先确定当前节点关键字数量小于最小关键字数量，并确定要进行填充的节点。

2. 首先查找当前节点的兄弟节点，找出关键字数量大于最小关键字数量的兄弟节点。

3. 如果存在兄弟节点，可以选择从兄弟节点中借一个关键字过来填充当前节点。这可以通过从兄弟节点中移动一个关键字和相应的指针到当前节点来实现。

4. 更新父节点的关键字和指针，以及兄弟节点的关键字和指针，完成填充操作。

5. 如果不存在关键字数量大于最小关键字数量的兄弟节点，则可能需要进行合并操作。合并操作可以将当前节点与兄弟节点合并为一个节点。

6. 合并操作可能涉及到移动关键字和指针，同时更新父节点的关键字和指针。

7. 重复以上步骤，直到满足平衡条件或达到根节点。

填充策略：

B树中的填充操作的策略通常有以下几种：

1. 借用关键字：如果存在关键字数量大于最小关键字数量的兄弟节点，可以选择从兄弟节点中借用一个关键字过来填充当前节点。

2. 合并节点：如果没有关键字数量大于最小关键字数量的兄弟节点，可以选择合并当前节点和兄弟节点为一个节点。

B树的默认填充策略通常是优先选择借用关键字的方式进行填充操作。