一、常见的搜索结构

下面是一些常见的搜索结构：

以下是您要求的查找方法及其相关的种类、数据格式和时间复杂度，以表格形式列举：

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

• 顺序查找：适用于任何数据结构，但时间复杂度较高。
• 二分查找：只适用于已排序的数据，因此需要事先将数据排序。
• 二叉搜索树：每个节点的左子树比右子树小，适用于动态数据，但最坏情况下可能退化为链表，时间复杂度变为O(N)。
• 二叉平衡树（如AVL树、红黑树等）：通过平衡操作保证树的高度为O(log₂ N)，因此查找时间复杂度较低，适用于动态数据。
• 哈希查找：通过哈希表实现查找，通常可以达到O(1)的时间复杂度，但存在哈希冲突的情况。

---

总的来说，以上结构适合用于数据量相对较小，能够一次性存放在内存中，进行数据查找的场景。

若数据量很大，比如上百G无法一次放进内存中的数据，只能放在磁盘上；

对于磁盘上需要搜索的数据：可以考虑将存放【关键字及其映射】的数据地址放到一个内存中的搜索树的节点中，当要访问数据时，取这个地址去磁盘访问相应数据

---

由于：

在这种情况下，使用平衡二叉树或是哈希表都有一定的缺陷：

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

• 平衡二叉树搜索树的高度是logN，在内存中很快。但当数据在磁盘中时，访问磁盘速度很慢，当数据量很大时，logN次的磁盘访问，是一个大的开销。

使用哈希表的缺陷：

• 哈希表的效率是O(1)，但在极端场景下某个位置冲突很多，导致访问次数剧增，也是大的开销

---

那么如何提高对磁盘中数据的访问速度？

1. IO速率优化：使用SSD等特殊磁盘（虽说速度提示，但本质没有变化）
2. 搜索结果优化：降低树的高度，采用多叉搜索平衡树（一个节点存放多个关键字与映射）

这个结构就是下文探讨的B树；

---

二、B树

2.1 B树概念

B树是一种适合外查找的树，m阶(m>2)的B树，是平衡的M路平衡搜索树，可以是空树

其满足以下性质：

1. 根节点至少有两个孩子
2. 每个分支节点都包含 k-1个关键字 和 k个孩子 ，其中 ceil(m/2) ≤ k ≤ m （ceil是向上取整）
3. 每个叶子节点都包含 k-1个关键字 ，其中 ceil(m/2) ≤ k ≤ m
4. 所有的叶子节点都在同一层
5. 每个节点中的关键字从小到大排列，节点当中【k-1个元素正好是k个孩子包含的元素的值域划
   分】
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≤n≤m-1）

下图是一个简易B树的示意图：

对于B树来说，其整体的结构的实现都是遵循其插入的规律来的（与AVL树与红黑树不同，这两个是根据已有的稳定结构，去实现相应的插入逻辑）

下面举一个实例，我们通过其插入的过程图理解这一过程，我们插入一组数据：{53,139,75,49,145,35,52 48, 100, 110}

• 插入前三个数时，情况如下：
  

• 当插入第四个值时，关键字数量超过了最大值，会进行节点分裂：

• 再插入两个值到同一子节点，会再次进行分裂：

• 再次插入一些值，此时根节点的关键字达到最大值：

• 再次插入两个值，使其中一个子节点需要分裂，当子节点将关键字向上传递后，此时根节点关键字超出最大值，也需要分裂：

根据上图，我们理解了B树的插入过程，且容易看出，B树是天然平衡的，因为比起其他搜索结构，B树是向右扩充，向上生长的；

---

2.2 开销

不妨分析一下其面对相应场景时的开销：

对于一个M=1000，高为4的B树：

---

三、代码实现

根据上面插入的思路，我们可以用代码进行实现：

3.1 B树节点的设计

我们通过模板+结构体定义B树的一个节点，包括以下成员变量：

1. K _keys[M]：存储关键字
2. BTreeNode<K, M>* _sub[M + 1]： 存储指向子节点的指针数组
3. BTreeNode<K, M>* _parent：指向父节点的指针
4. size_t _size：当前节点包含的关键字数量

// 模板类定义：B树节点（BTreeNode）
// K: 关键字类型
// M: 每个节点最多包含的关键字数（默认 M=3）template <class K, int M = 3>
struct BTreeNode {// 存储关键字的数组K _keys[M];  // 存储指向子节点的指针数组，M+1 是因为子节点数比关键字数多 1BTreeNode<K, M>* _sub[M + 1];  // 指向父节点的指针，根节点的父节点为 nullptrBTreeNode<K, M>* _parent;       // 当前节点包含的关键字数量（有效关键字个数）size_t _size;// 构造函数，初始化节点的成员变量BTreeNode() : _parent(nullptr), _size(0) {// 初始化所有子节点指针为 nullptrfor (int i = 0; i <= M; ++i) {_sub[i] = nullptr;}}
};

---

3.2 B树设计

我们这里主要实现B树的插入操作，下面是B树类的构成，包含：

1. 节点结构 BTreeNode：B树的每个节点有若干关键字、子节点指针和一个指向父节点的指针。
2. B树类 BTree：管理整个树的结构，包括根节点、插入、查找等操作。

template<class K, int M = 3>
class BTree
{
public:using Node = BTreeNode<K, M>;// 构造函数：初始化空树BTree() : _root(nullptr) {}// 析构函数：释放树的内存~BTree() {clear(_root);}// 成员函数// 查找指定节点std::pair<Node*, int> Find(const K& key); // 插入void InsertKey(Node* cur, const K& key, Node* sub)bool Insert(const K& key);private:Node* _root = nullptr;
};

---

3.3 插入操作实现

我们实现的插入操作主要包括三个步骤：

1. 查找插入位置：通过 Find 函数找到插入位置。
2. 插入关键字到节点：通过 InsertKey 函数将关键字插入到适当位置。
3. 节点分裂：如果节点满了（即 cur->_size >= M），则需要分裂节点，分裂过程是递归的，直到根节点为止。

1. 查找插入位置（Find 函数）

Find 函数用于查找关键字在 B 树中的位置。如果找到匹配的关键字，返回该节点和关键字的位置。如果没有找到，返回父节点和插入位置的负值。

std::pair<Node*, int> Find(const K& key)
{Node* cur = _root;         // 当前节点，从根节点开始查找Node* parent = nullptr;    // 父节点while (cur){size_t i = 0;while (i < cur->_size) {if (key < cur->_keys[i]) {     // 找到合适的插入位置break;}else if (key > cur->_keys[i]) { // 如果关键字大于当前节点的关键字，继续查找下一个i++;}else { // 找到相同的关键字，返回当前节点及其位置return std::make_pair(cur, i);}}parent = cur;cur = cur->_sub[i]; // 查找对应的子节点}return std::make_pair(parent, -1); // 返回父节点和 -1，表示未找到，需插入
}

在查找过程中，我们遍历节点的关键字，寻找该关键字的位置。如果找到相同的关键字，则直接返回。否则，递归查找相应的子节点。

2. 插入关键字到节点（InsertKey 函数）

InsertKey 函数用于将一个新关键字插入到当前节点 cur 中的正确位置。如果当前节点有空余空间，直接插入。

void InsertKey(Node* cur, const K& key, Node* sub)
{int end = cur->_size - 1;// 将大于新插入关键字的元素向后移动一位while (end >= 0){if (key < cur->_keys[end]) {cur->_keys[end + 1] = cur->_keys[end];cur->_sub[end + 2] = cur->_sub[end + 1];}else {break;}end--;}cur->_keys[end + 1] = key;   // 插入新关键字cur->_sub[end + 2] = sub;    // 插入子节点指针if (sub) sub->_parent = cur; // 如果插入的不是叶子节点，更新子节点的父指针cur->_size++;                // 更新当前节点的大小
}

这个函数实现了将关键字插入到节点中的一个排序数组。插入时，从后往前找到合适的位置，并将比插入关键字大的元素向后移动。然后插入关键字，并且更新子节点指针。

3. 处理节点分裂（Insert 函数）

如果插入导致节点的大小超过了树的最大节点大小 M，则需要分裂节点并更新父节点。分裂过程是递归的，当根节点也需要分裂时，树的高度会增加。

bool Insert(const K& key)
{// 如果根节点为空，创建根节点并插入关键字if (_root == nullptr) {_root = new Node;_root->_size = 1;_root->_keys[0] = key;return true;}// 查找插入位置auto ret = Find(key);if (ret.second >= 0) { // 如果元素已存在std::cout << "元素已存在: " << key << std::endl;return false;}Node* cur = ret.first;Node* brother = nullptr;K k = key;// 递归插入while (true){InsertKey(cur, k, brother); // 向节点插入关键字// 如果当前节点没有满，则直接返回if (cur->_size < M) return true;// 如果节点满了，进行分裂int mid = M / 2;brother = new Node;  // 创建兄弟节点// 将当前节点右半部分的元素和子树指针移到兄弟节点for (int i = mid + 1; i < M; ++i) {brother->_keys[brother->_size] = cur->_keys[i];brother->_sub[brother->_size] = cur->_sub[i];if (cur->_sub[i]) cur->_sub[i]->_parent = brother;brother->_size++;}// 设置兄弟节点的子树指针brother->_sub[brother->_size] = cur->_sub[cur->_size];if (cur->_sub[cur->_size]) cur->_sub[cur->_size]->_parent = brother;// 更新当前节点的大小cur->_size = mid;// 如果当前节点没有父节点，说明树的高度增加if (cur->_parent == nullptr) {_root = new Node; // 创建新的根节点_root->_keys[0] = cur->_keys[mid]; // 将中间关键字升到新根节点_root->_sub[0] = cur;_root->_sub[1] = brother;_root->_size = 1;cur->_parent = brother->_parent = _root; // 更新父节点指针break;}else { // 否则，将中间关键字提升到父节点，并继续分裂k = cur->_keys[mid];cur = cur->_parent;}}return true;
}

主要步骤：

1. 查找插入位置：首先通过 Find 函数查找插入位置，如果关键字已经存在，返回 false。
2. 插入关键字：通过 InsertKey 向当前节点插入新关键字。如果当前节点未满，直接返回。
3. 处理节点分裂：
   • 如果当前节点满了，需要分裂。
   • 分裂时，选择中间关键字作为新的父节点。
   • 将当前节点的右半部分（包括子节点）转移到新创建的兄弟节点中。
   • 递归更新父节点，如果父节点也满了，继续分裂。
   • 如果根节点也满了，创建新的根节点。

4. 结论

整个插入操作通过递归方式处理节点分裂，保证了 B 树的平衡。插入过程中会不断调整节点，分裂节点直到根节点，确保树的结构符合 B 树的定义，即每个节点的关键字数始终满足 ⌈M/2⌉ - 1 <= _size <= M - 1。

3.4 验证

对于一个平衡树，我们可以通过中序遍历的方式，将所有节点值打印出来，如果结果有序，则树结构无误

中序遍历包含以下步骤，下面是中序遍历代码：

• 遍历当前节点的每个关键字对应的左子树（_sub[i]）。
• 输出当前节点的关键字。
• 最后，遍历当前节点的右子树（_sub[_size]）。

  void printInOrder() {inOrder(_root);}void inOrder(Node* root){if (root == nullptr) return;for (int i = 0; i < root->_size; ++i) {inOrder(root->_sub[i]);std::cout << root->_keys[i] << " ";}inOrder(root->_sub[root->_size]);}

随后插入测试数据进行测试：

int main()
{BTree<int, 3> tree;tree.Insert(10);tree.Insert(20);tree.Insert(5);tree.Insert(6);tree.Insert(15);tree.Insert(30);tree.Insert(25);tree.Insert(35);std::cout << "B-tree in-order traversal:" << std::endl;tree.printInOrder();return 0;
}

结果验证：

---

四、B+树与B*树

4.1 B+树

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

1. 分支节点的子树指针与关键字个数相同
2. 分支节点的子树指针p[i]指向关键字值大小在（k[i]，k[i+1]）区间之间
3. 所有叶子节点增加一个链接指针链接在一起
4. 所有关键字及其映射数据都在叶子节点中；

B树的特性：

1. 所有数据都存储在叶子节点：B树中的所有关键字（或数据）都保存在最底层的叶子节点里，且这些叶子节点按顺序排列，形成一个有序的链表。

2. 分支节点不是数据存储的地方：在B树的中间层（分支节点）并不会存储实际的数据，只是用来指引到正确的叶子节点。也就是说，你在分支节点上找不到数据。

3. 分支节点是叶子节点的“索引”：分支节点的作用类似于目录或索引，它们帮助你快速找到数据所在的叶子节点，真正存储数据的地方是叶子节点。

即：B+树的叶子节点才是存储数据的地方，分支节点只起到“导航”的作用，帮助快速定位数据。

---

1. B+树的分裂

用文字描述B+树的分裂过程即：

当一个节点满了时，会创建一个新的节点，把原节点的一半数据移动到新节点。然后，在父节点中加入指向新节点的链接。B+树的分裂只会影响到当前节点和父节点，不会影响到其他兄弟节点，所以不需要为兄弟节点添加指针。

下面我们演示一下B+树的插入与分裂过程：

首先对于上图，我们得到几点信息：

1. B+树插入第一个元素时，就会创建两个节点
2. 一次分裂的过程可以简述为：
   • 创建新节点（兄弟节点），将中位数向后的元素给兄弟节点，将中位数向上传递
   • 将父节点的关键字指向新的兄弟节点的头部

随后再次进行插入关键字，直到再次存在节点满

此时会引发连续分裂，子节点将中位数向上传递时，父节点也满了，父节点再次进行分裂；

---

2. 总结

1. B+树的孩子与关键字的数量相等
2. 所有数据都存储在叶子节点上，方便遍历查找所有值

---

4.2 B*树

B*树是B+树的变形，给B+树的【非根 & 非叶子节点】增加【指向兄弟节点的指针】。

---

1. 分裂

用文字描述B*树的分裂即：

1. 当一个结点满时，如果它旁边的兄弟结点未满，则将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（兄弟结点的关键字范围改变）；
2. 如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针

下面用示例图简单展示B*树的分裂过程：

首先将一个节点插入满，此时该节点会将自己一半的关键字传给兄弟节点

此时再次插入两个关键字，此时两个节点均为满，再次进行分裂，此时会创建新的节点，左右两节点分别将自己的1/3（不一定），传给新节点

---

通过上面的图，可以很明显的得出一个结论：

• B*树分配新结点的概率比B+树要低，空间使用率更高；

---

4.3 总结

通过对三种树的了解，做一个总结：

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

---

五、B树的实际应用

5.1 B树 与 MYSQL

根据B树自身性质，其最常见的应用就是作索引（快速定位要查找的内容的位置），MYSQL底层用的就是B树，MYSQL官方对索引有解释：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构

需要注意的是：

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

---

5.2 MYSQL的存储引擎

1. MYISAM

1. MyISAM是MySQL5.5.8版本前的默认引擎，不支持事物，支持全文检索。
2. 使用B+树作索引结构，叶节点的data域存放的是【数据记录的地址】

上图可以很明显的看出：

MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复

我们利用创建索引语句中创建的索引就是辅助索引 CREATE INDEX idx_email ON users(email);

如果以第二列作辅助索引，则其存储结构如下：

因此，MyISAM中索引检索的算法为先按照B+Tree搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，随后以data域的值为地址，读取相应数据记录。MyISAM的索引方式也叫做 “非聚集索引”；

2. InnoDB

InnoDB存储引擎支持事务，其设计目的主要面向在线事务的处理应用，从MySQLv5.5.8开始，InnoDB存储引擎是默认的存储引擎。

InnoDB支持B+树索引、全文索引、哈希索引。尽管InnoDB使用B+Tree作为索引结构，其具体实现方式却与MyISAM大不相同。

1. InnoDB的数据文件本身就是索引文件（类似我们上文讲解的B+树）。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址

InnoDB索引，表的数据文件本身就是按B+树 组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。（即聚集索引）

可以推测出，对于InnoDB为存储引擎的数据库表，为什么每一个表都必须要有一个唯一的主键，建表时的主键实际上就是B+树的一个索引（关键字），所以每个表的逐渐都要求，不能重复值，必须唯一
（如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数
据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型）

同理对于辅助索引的dat·a域，其存储相应记录主键的值不是地址；所有辅助索引都引用主键作为data域。

---

5.3 总结

• InnoDB 存储引擎要求每个表必须有一个 唯一的主键，并且主键索引是 B+树结构，保证数据行的唯一性、顺序存储和高效查询。
• MyISAM 存储引擎并不强制要求每个表必须有主键。MyISAM 表可以没有主键，而且其索引结构与 InnoDB 略有不同，通常为 非聚集索引。
• 聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录