B树的预备知识
我们平常查找比如用搜索二叉树哈希表这些数据结构，一般都是数据在内存中的，这样的话访问数据的速度就很快，这种查找也叫做内查找。二分查找或者直接顺序查找也适合内查找。
但是当数据量非常大时，比如有100G的数据，此时内存就放不下了，只能放在磁盘上了，在内存外的存储结构上查找也就是外查找。
对于外查找以我们之前所学习的知识，该用什么思路呢?
数据在磁盘中，并且是连在一起的，它们也有地址。我们可以用一个平衡搜索树存每个数据的地址，这样每次查找我们需要通过一次文件IO将地址转化成数据进行比较，然后再向下进行。这样的话查找起来主要耗时就在磁盘IO上，如果是这种结构，那么就需要高度次IO，也就是O（logN）级别，比如AVL/红黑树。或者我们也可以用哈希表，它是O（1）级别的，但是哈希表在极端场景下哈希冲突非常严重，也会导致效率低下。
而且磁盘慢主要是它的每一次查找定位很慢，一旦定位到了就很快了，这跟之后B树设计有关系。
B树就是在搜索树的基础上进行优化的：
1.压缩高度，二叉变多叉
2.一个结点要存多个关键字及映射的值。
B树的概念
如图，这是m = 3。那么它就最多有m/2个关键字，3个孩子。
不过需要注意的是，一般我们会多开一个空间，以此来方便后续关键字满了后要分裂的场景，比如
m依旧为3，但是结点如下
在实际设计中，M的值一般会设计的很大，比如1024
B树的插入
首先我们知道，一个结点中，关键字的顺序是从小到大排序的，那么当结点中的关键字没有满时，我们就需要找到这个关键字适合插入的位置。
如果结点满了，那么这个结点就需要分裂出一个兄弟结点，并将自己一半的关键字和孩子分给这个兄弟结点。然后再选一个中位数大小的关键字给父亲结点（也要注意顺序），然后将兄弟结点与父亲结点进行连接，如果父亲结点不存在，那么就先创建一个父亲结点，然后记得连接子结点。
后续插入就是以此类推，从父结点开始找，根据大小一直找到对应的叶子结点，然后再插入，如果满了就分裂。B树的新结点的插入一定是在叶子结点上的。叶子没有孩子，不影响关键字和孩子的关系，叶子结点满了，就分裂出一个兄弟，再提取中位数，向父亲结点插入这个关键字，和一个孩子（也就是兄弟结点）。
由此我们可以发现，B树是天然平衡的，因为它的生长是向右和向上生长的。
B树的简单实现
#pragma once
#include <utility>
#include <iostream>
using namespace std;
template<class K,size_t M>
struct BTreeNode
{
// 为了方便插入以后再分裂，可以多给一个空间
K _keys[M]; // 存关键字的
BTreeNode<K, M>* _subs[M + 1]; // 存孩子的指针
BTreeNode<K, M>* _parent; // 也是方便插入时找到父亲结点
size_t _n; // 记录实际存储了多少个关键字
BTreeNode()
{
for (size_t i = 0; i < M; ++i)
{
_keys[i] = K();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
};
// 这里我们简化代码，只实现K模型的而不是K-V模型的
// 外查找时数据存在磁盘里，那么肯定得是K-V模型。
template<class K,size_t M>
class BTree
{
typedef BTreeNode<K, M> Node;
public:
pair<Node*, int> Find(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
// 在一个结点中查找
size_t i = 0;
while (i < cur->_n)
{
if (key < cur->_keys[i])
{
break;
}
else if (key > cur->_keys[i])
{
++i;
}
else
{
return make_pair(cur, i);
}
}
// 走到孩子结点上
parent = cur;
cur = cur->_subs[i];
}
return make_pair(parent, -1); // 到叶子结点了，这个-1是用来判断是否走到叶子结点
}
void InsertKey(Node* node, const K& key, Node* child)
{
int end = node->_n - 1;
while (end >= 0)
{
if (key < node->_keys[end])
{
// 挪动key和它的右孩子
node->_keys[end + 1] = node->_keys[end];
node->_subs[end + 2] = node->_subs[end + 1]; // 注意key和它的右孩子的对应关系
--end;
}
else
{
break;
}
}
// 插入
node->_keys[end + 1] = key;
node->_subs[end + 2] = child;
if (child)
{
child->_parent = node;
}
node->_n++;
}
bool Insert(const K& key)
{
if (_root == nullptr) // 第一次插入
{
_root = new Node;
_root->_keys[0] = key;
_root->_n++;
return true;
}
// 先查找，如果key已经存在，那么就不用插入了。
pair<Node*, int> ret = Find(key);
if (ret.second >= 0) // 说明已存在
{
return false;
}
// 如果没有找到，find也带回了要插入的那个叶子结点
// 循环每次往cur插入 newkey和child
Node* parent = ret.first;
K newKey = key;
Node* child = nullptr;
while (1)
{
InsertKey(parent, newKey, child);
// 没有满，插入就结束
if (parent->_n < M) // 这里就对应了为什么在Node里要多开一个空间。
{
return true;
}
else
{
size_t mid = M / 2;
// 分裂一半[mid + 1, M - 1]给兄弟
Node* brother = new Node;
size_t j = 0;
size_t i = mid + 1; // 这里为什么要+1，是因为还要拿一个结点给父亲
for (; i <= M - 1; ++i)
{
// 分裂拷贝key和key的左孩子
brother->_keys[j] = parent->_keys[i];
brother->_subs[j] = parent->_subs[i];
if (parent->_subs[i])
{
parent->_subs[i]->_parent = brother;
}
++j;
// 方便观察
parent->_keys[i] = K();
parent->_subs[i] = nullptr;
}
// 注意 还有最后一个右孩子拷给兄弟
brother->_subs[j] = parent->_subs[i];
if (parent->_subs[i])
{
parent->_subs[i]->_parent = brother;
}
parent->_subs[i] = nullptr;
brother->_n = j;
parent->_n -= (brother->_n + 1); // 为什么要+1因为还有一个要给父亲
K midKey = parent->_keys[mid]; // 准备给父亲结点插入key了
parent->_keys[mid] = K();
// 说明刚刚分裂是根结点
if (parent->_parent == nullptr)
{
_root = new Node;
_root->_keys[0] = midKey;
_root->_subs[0] = parent;
_root->_subs[1] = brother; // 写到这里再回想一下，B树的规则：根结点至少有两个孩子
_root->_n = 1;
parent->_parent = _root;
brother->_parent = _root;
break;
}
else
{
// 如果不是根结点，那么就往父亲结点插入，以此循环，直到新建了一个根结点
// 或者在下一次插入的父亲结点中，在插入后未满
newKey = midKey;
child = brother;
parent = parent->_parent;
}
}
}
return true;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
size_t i = 0;
for (; i < root->_n; ++i)
{
_InOrder(root->_subs[i]);
cout << root->_keys[i] << " ";
}
_InOrder(root->_subs[i]);
}
void InOrder() // 中序遍历 将数据有序输出
{
_InOrder(_root);
}
private:
Node* _root = nullptr;
};
void TestBtree()
{
int a[] = { 53, 139, 75, 49, 145, 36, 101 };
BTree<int, 3> t;
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
}这中间还有一个中序遍历，其实也非常简单，二叉树的中序遍历是 左 根 右。而这里B树的遍历就是 左 根 左 根 .... 右，就是最后再补一个右即可。
B+树
B+树的概念
由图我们可以看到，叶子结点是链接在一起的，这样话我们也可以直接遍历叶子结点来找到我们想要的数据。
分支节点里面都只存Key，只有叶子节点里面才存Key和Val。
分支结点根叶子结点有重复的值，分支结点存的是叶子结点的索引。
父亲结点存的是孩子结点中最小的值作为索引。
所以现在可以做一个小小的总结：
1.B+树简化了B树孩子比关键字多一个的规则，B+树的关键字和孩子数量相等。
2.父亲中存的孩子结点中最小的值作为索引。
B+树的插入
B+树的插入跟B树相似，但又略有不同，这里就只说思想了。
但是我们知道，B+树的分支结点只存Key，叶子结点既存Key也存Val。因此，在第一次插入的时候，B+树就有两层！一层做根，一层做叶子。我们依旧以M=3为例
第一次插入53
一直插入直到49开始第一次分裂
这里的处理也比B树简单一些，它是直接将一半的索引给分裂出来的兄弟结点，然后直接将兄弟的最小值给父亲结点作为索引。
接下来一直插入，直到插入101进行第二次分裂
第二次分裂与第一次逻辑一样。
接下来再补充插入一些结点（150和155），来看看第三次分裂
此时我们发现分裂后，父亲结点满了，那么父亲结点也需要进行分裂
这样B+树就由最初的两层变成了三层。
这就是B+树的插入思想。
总结B+树的特性：
B*树
再来说说B*树的分裂：
自己和兄弟各自凑出1/3M，给新的兄弟结点。
总结三种树
B-树的应用
B-树在内查找和外查找中的表现
内查找
内查找也就是在内存中查找。
B树系列和哈希表和平衡搜索树（AVL树和RB树）的对比：
如果只看树的高度，和搜索效率的话，B树系列确实不错。
但是B树系列也有缺点：
1.空间利用率低，消耗大。我们可以看到很多结点都不一定会存满。
2.插入数据和删除数据时，会分裂和合并结点，那么必然就会挪动数据，带来隐形的消耗。
3.虽然B树系列高度低，但是就在内存中而言，跟哈希和平衡搜索树还是一个量级的。
总结：B树系列在内存中体现不出优势。
外查找
但是，在外查找，也就是磁盘中就不一样了。
在内存中查找3次和30次，差距并不大。
但是在磁盘中查找3次和30次差距就很大了。
因为我们知道IO操作是很消耗时间的。
因此B树系列在外查找中就能体现出优势。
索引
其中B-树的一般就是做MyISAM或InnoDB的搜索引擎的。
一般是B+树用来做磁盘数据索引的。
比如我们要创建一个学生的信息表，有学生ID，年龄等信息。
在创建的时候，我们还需要选择一个信息作为主键，也就是将来搜索时的关键字。有些数据库不准用名字作为主键，因为名字可能不唯一，比如Mysql，但是有些数据库可以。
比如这里我们拿学生ID作为主键。那么ID就是Key，Val就是这个学生所有的信息的磁盘地址（这个信息一般就是一行）。
另外分支结点也是需要存在磁盘中的，因为数据量大了的话，内存中也存不下。但是分支结点理应被缓存到cache中。
另外当我们在查询数据的时候，我们可以根据ID来找，也可以根据姓名来找。但是ID是主键，用ID来查找的效率要比按姓名来查找的效率要高很多。用主键来查找的效率是 O（logN），而用非主键的信息来查找的效率就是 O（N），因为它是通过遍历叶子结点来进行查找的。
但是如果我们又经常使用姓名去查找的话，我们可以用姓名建立一个索引。
当姓名也就是name索引创建以后，那么就会以B+树以name作为key再创建一颗树。这样的话效率就高了。
mysql的存储引擎
![[Flutter]TextButton自定义样式](https://img-blog.csdnimg.cn/direct/9be4fa5a7ede494d8ccf28542ddc61e8.png)
