文章目录
- 一、常见的搜索结构
- 二、B树
- 2.1 B树概念
- 2.2 开销
- 三、代码实现
- 3.1 B树节点的设计
- 3.2 B树设计
- 3.3 插入操作实现
- 1. 查找插入位置（`Find` 函数）
- 2. 插入关键字到节点（`InsertKey` 函数）
- 3. 处理节点分裂（`Insert` 函数）
- 主要步骤：
- 4. 结论
- 3.4 验证
- 四、B+树与B*树
- 4.1 B+树
- 1. B+树的分裂
- 2. 总结
- 4.2 B*树
- 1. 分裂
- 4.3 总结
- 五、B树的实际应用
- 5.1 B树 与 MYSQL
- 5.2 MYSQL的存储引擎
- 1. MYISAM
- 2. InnoDB
- 5.3 总结
一、常见的搜索结构
下面是一些常见的搜索结构：
以下是您要求的查找方法及其相关的种类、数据格式和时间复杂度，以表格形式列举：
| 查找方法 | 数据格式 | 时间复杂度 |
|---|---|---|
| 顺序查找 | 无要求 | 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)，但在极端场景下某个位置冲突很多，导致访问次数剧增，也是大的开销
那么如何提高对磁盘中数据的访问速度？
- IO速率优化：使用SSD等特殊磁盘（虽说速度提示，但本质没有变化）
- 搜索结果优化：降低树的高度，采用多叉搜索平衡树（一个节点存放多个关键字与映射）
这个结构就是下文探讨的B树；
二、B树
2.1 B树概念
B树是一种适合外查找的树，m阶(m>2)的B树，是平衡的M路平衡搜索树，可以是空树
其满足以下性质：
- 根节点至少有两个孩子
- 每个分支节点都包含 k-1个关键字 和 k个孩子 ，其中
ceil(m/2) ≤ k ≤ m（ceil是向上取整） - 每个叶子节点都包含 k-1个关键字 ，其中
ceil(m/2) ≤ k ≤ m - 所有的叶子节点都在同一层
- 每个节点中的关键字从小到大排列，节点当中【k-1个元素正好是k个孩子包含的元素的值域划
分】 - 每个结点的结构为：（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树的一个节点，包括以下成员变量：
- K _keys[M]：存储关键字
- BTreeNode<K, M>* _sub[M + 1]： 存储指向子节点的指针数组
- BTreeNode<K, M>* _parent：指向父节点的指针
- size_t _size：当前节点包含的关键字数量
// 模板类定义：B树节点（BTreeNode）
// K: 关键字类型
// M: 每个节点最多包含的关键字数（默认 M=3）
template <class K, int M = 3>
struct BTreeNode {
// 存储关键字的数组
K _keys[M];
// 存储指向子节点的指针数组，M+1 是因为子节点数比关键字数多 1
BTreeNode<K, M>* _sub[M + 1];
// 指向父节点的指针，根节点的父节点为 nullptr
BTreeNode<K, M>* _parent;
// 当前节点包含的关键字数量（有效关键字个数）
size_t _size;
// 构造函数，初始化节点的成员变量
BTreeNode() : _parent(nullptr), _size(0) {
// 初始化所有子节点指针为 nullptr
for (int i = 0; i <= M; ++i) {
_sub[i] = nullptr;
}
}
};
3.2 B树设计
我们这里主要实现B树的插入操作，下面是B树类的构成，包含：
- 节点结构 BTreeNode：B树的每个节点有若干关键字、子节点指针和一个指向父节点的指针。
- 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 插入操作实现
我们实现的插入操作主要包括三个步骤：
- 查找插入位置：通过
Find函数找到插入位置。 - 插入关键字到节点：通过
InsertKey函数将关键字插入到适当位置。 - 节点分裂：如果节点满了（即
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;
}
主要步骤：
- 查找插入位置：首先通过
Find函数查找插入位置，如果关键字已经存在，返回false。 - 插入关键字：通过
InsertKey向当前节点插入新关键字。如果当前节点未满，直接返回。 - 处理节点分裂：
- 如果当前节点满了，需要分裂。
- 分裂时，选择中间关键字作为新的父节点。
- 将当前节点的右半部分（包括子节点）转移到新创建的兄弟节点中。
- 递归更新父节点，如果父节点也满了，继续分裂。
- 如果根节点也满了，创建新的根节点。
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树的基础上做了以下几点改进优化：
- 分支节点的子树指针与关键字个数相同
- 分支节点的子树指针p[i]指向关键字值大小在（k[i]，k[i+1]）区间之间
- 所有叶子节点增加一个链接指针链接在一起
- 所有关键字及其映射数据都在叶子节点中；
B树的特性：
-
所有数据都存储在叶子节点：B树中的所有关键字（或数据）都保存在最底层的叶子节点里，且这些叶子节点按顺序排列，形成一个有序的链表。
-
分支节点不是数据存储的地方：在B树的中间层（分支节点）并不会存储实际的数据，只是用来指引到正确的叶子节点。也就是说，你在分支节点上找不到数据。
-
分支节点是叶子节点的“索引”：分支节点的作用类似于目录或索引，它们帮助你快速找到数据所在的叶子节点，真正存储数据的地方是叶子节点。
即：B+树的叶子节点才是存储数据的地方，分支节点只起到“导航”的作用，帮助快速定位数据。
1. B+树的分裂
用文字描述B+树的分裂过程即：
当一个节点满了时，会创建一个新的节点，把原节点的一半数据移动到新节点。然后，在父节点中加入指向新节点的链接。B+树的分裂只会影响到当前节点和父节点，不会影响到其他兄弟节点，所以不需要为兄弟节点添加指针。
下面我们演示一下B+树的插入与分裂过程：
首先对于上图，我们得到几点信息：
- B+树插入第一个元素时，就会创建两个节点
- 一次分裂的过程可以简述为：
- 创建新节点（兄弟节点），将中位数向后的元素给兄弟节点，将中位数向上传递
- 将父节点的关键字指向新的兄弟节点的头部
随后再次进行插入关键字，直到再次存在节点满
此时会引发连续分裂，子节点将中位数向上传递时，父节点也满了，父节点再次进行分裂；
2. 总结
- B+树的孩子与关键字的数量相等
- 所有数据都存储在叶子节点上，方便遍历查找所有值
4.2 B*树
B*树是B+树的变形，给B+树的【非根 & 非叶子节点】增加【指向兄弟节点的指针】。
1. 分裂
用文字描述B*树的分裂即：
- 当一个结点满时，如果它旁边的兄弟结点未满，则将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（兄弟结点的关键字范围改变）；
- 如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针
下面用示例图简单展示B*树的分裂过程：
首先将一个节点插入满，此时该节点会将自己一半的关键字传给兄弟节点
此时再次插入两个关键字，此时两个节点均为满，再次进行分裂，此时会创建新的节点，左右两节点分别将自己的1/3（不一定），传给新节点
通过上面的图，可以很明显的得出一个结论：
- B*树分配新结点的概率比B+树要低，空间使用率更高；
4.3 总结
通过对三种树的了解，做一个总结：
B树：有序数组+平衡多叉树；
B+树：有序数组链表+平衡多叉树；
B*树：一棵更丰满的，空间利用率更高的B+树。
五、B树的实际应用
5.1 B树 与 MYSQL
根据B树自身性质，其最常见的应用就是作索引（快速定位要查找的内容的位置），MYSQL底层用的就是B树，MYSQL官方对索引有解释：索引(index)是帮助MySQL高效获取数据的数据结构，简单来说：索引就是数据结构
需要注意的是：
- MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的
- 索引是基于表的，而不是基于数据库的
5.2 MYSQL的存储引擎
1. MYISAM
MyISAM是MySQL5.5.8版本前的默认引擎，不支持事物，支持全文检索。- 使用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大不相同。
InnoDB的数据文件本身就是索引文件（类似我们上文讲解的B+树）。MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址
InnoDB索引，表的数据文件本身就是按B+树 组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。（即聚集索引）
可以推测出，对于InnoDB为存储引擎的数据库表，为什么每一个表都必须要有一个唯一的主键，建表时的主键实际上就是B+树的一个索引（关键字），所以每个表的逐渐都要求，不能重复值，必须唯一
（如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数
据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型）
同理对于辅助索引的dat·a域，其存储相应记录主键的值不是地址；所有辅助索引都引用主键作为data域。
5.3 总结
- InnoDB 存储引擎要求每个表必须有一个 唯一的主键，并且主键索引是 B+树结构，保证数据行的唯一性、顺序存储和高效查询。
- MyISAM 存储引擎并不强制要求每个表必须有主键。MyISAM 表可以没有主键，而且其索引结构与 InnoDB 略有不同，通常为 非聚集索引。
- 聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录
