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，即三叉树，每个节点中存储两个数据，三个子节点，后续简单实现期间，节点的结构如下：
