B+树的节点插入操作详细分析

# 第一章：B 树简介

B 树是一种自平衡的树型数据结构，广泛应用于文件系统、数据库索引等场景，其特点是能够保持数据有序并支持快速的搜索、插入、删除操作。B 树通过节点的分裂和合并来维护平衡，具有较高的插入与检索效率。

## 1.1 B 树的定义与特点

B 树是一种多路搜索树，具有以下特点：
- 每个节点最多有 M 个子节点；
- 除根节点和叶子节点外，其他节点至少有 ceil(M/2) 个子节点；
- 所有叶子节点位于同一层，且不存储数据；
- 节点中的数据项按照大小顺序排列。

## 1.2 B 树的应用场景

B 树常用于大型数据库和文件系统中，能够有效支持范围查询、顺序访问和大数据量存储；例如，在数据库索引中，B 树可以快速定位到指定的数据；在文件系统中，B 树可以加快文件的查找速度。

## 1.3 B 树的节点结构

B 树的节点结构包括节点内部的数据项和指向子节点的指针，通常表示为：

struct BTreeNode {
    int n; // 当前节点的存储的关键字个数
    int keys[M-1]; // 关键字列表，按升序排列
    struct BTreeNode *ptrs[M]; // 子节点指针列表
    bool leaf; // 是否为叶子节点
};

### 2. 第二章：B 树的节点插入操作概述
2.1 节点插入的意义与作用
2.2 插入操作的基本思路
2.3 插入操作的影响与考量
### 2.1 节点分裂策略

在B树的节点插入操作中，当节点已满时需要进行节点分裂操作，以保持B树的平衡性。节点分裂策略通常遵循以下步骤：

1. 确定分裂位置：将节点中的数据按顺序排列，找到中间位置的数据作为分裂点，将节点分成两部分。
2. 分裂出新节点：将分裂点两侧的数据分别放入两个新的节点中，并将分裂点上移至父节点中。
3. 更新父节点：若父节点已满，则递归进行分裂操作；否则将分裂后的两个子节点加入到父节点中，并更