我们已经学过了多种搜索结构，如下表：
以上结构适合用于数据量不是很大的情况，如果数据量非常大，一次性无法加载到内存中，使用上述结构就不是很方便。比如：使用平衡树搜索一个大文件
上面方法其实只在内存中保存了每一项数据信息中需要查找的字段以及数据在磁盘中的位置，整体的数据实际也在磁盘中。
使用平衡二叉树搜索树的缺陷：
平衡二叉树搜索树的高度是 ，这个查找次数在内存中是很快的。但是当数据都在磁盘中时，访问磁盘速度很慢，在数据量很大时， 次的磁盘访问，是一个难以接受的结果。
使用哈希表的缺陷：
哈希表的效率很高是 O(1)，但是一些极端场景下某个位置冲突很多，导致访问次数剧增，也是难以接受的。
🔴 那如何加速对数据的访问呢？
-
提高IO的速度 (SSD相比传统机械硬盘快了不少，但是还是没有得到本质性的提升)
-
降低树的高度，也就是让原本的二叉树变成多叉树来降低高度---多叉树平衡树
B 树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O。因为虽然平衡二叉树的查找效率是非常高的，但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘 I/O 读写过于频繁，进而导致查询效率低下，另外数据量过大会导致内存空间不够容纳平衡二叉树所有节点的情况，B 树很好的解决了这个问题。
Ⅱ. B-树
1970 年，R.Bayer和 E.mccreight 提出了一种适合外查找的树，它是一种平衡的多叉树，称为 B 树(后面有一个 B 树的改进版本 B+ 树，然后有些地方的 B 树写的的是 B- 树，注意不要误读成"B减树")。
一棵 m 阶 (m>2) 的 B 树，是一棵平衡的 M 路平衡搜索树，可以是空树或者满足一下性质：
-
根结点至少有两个孩子。
-
每个分支节点都包含
k-1个关键字 和k个孩子，其中m/2(向上取整) ≤子树个数≤m。 -
每一个叶子节点都包含
k-1个关键字，其中m/2-1(向上取整) ≤关键字个数≤m-1。 -
所有的叶子结点都位于同一层。
-
每个节点中的元素从小到大排列，节点当中
k-1个元素正好是k个孩子包含的元素的值域分划。
为什么说这种 B- 树速度快呢，因为它相当于是一颗满多叉树，是天然平衡的，这是由于其节点的值满的时候的分裂机制，是向右和向上生长的，就不要去调整平衡那么麻烦！
若 M 很大，一般可以大到 M=1024 的时候，只需要五层，即可存储现有的基本全部数据，这是红黑树和AVL树做不到的！
下面是一颗 M=3 的 B- 树：
B-树这么设计就是为了它的增删查改功能准备的，与我们之前的其他数据结构不太一样。
下面是 B- 树的节点结构定义：
🔺 要注意的是因为我们下面插入节点的时候是要使用插入排序的思想，为了防止越界，我们对每个数组多开一个元素：
template<class K, size_t M = 3>
struct BTreeNode
{
size_t _n; // 每个节点中有效关键字的个数
// 为了方便插入以后再分裂，多给一个空间
K _keys[M]; // 关键字数组
BTreeNode<K, M>* _subs[M + 1]; // 孩子节点数组，比关键字数组多一个
BTreeNode<K, M>* _parent; // 该节点的父亲节点指针
BTreeNode()
{
for (int i = 0; i < M; ++i)
{
_keys[i] = K();
_subs[i] = nullptr;
}
_subs[M] = nullptr;
_parent = nullptr;
_n = 0;
}
}; 下面我们来讲 B- 树的查找与插入函数，删除的话了解即可，实现只是为了让我们去了解的更加透彻。
1、查找函数 Find()
B-树的查找和二叉树其实差不多的，只不过要注意的是不同之间的 key 的 有效个数_n 是不一样的。（具体场景按下面插入函数给出的数据进行分析）
// 参数：key为待查找的元素
// 返回值：Node*代表找到的节点，int为该元素在该节点中的位置
pair<Node*, int> Find(const K& key)
{
Node* cur = _root;
Node* parent = nullptr; // 记录下cur的前一个节点
while (cur != nullptr)
{
// 遍历每个节点的各个关键字进行比较
size_t i = 0;
while (i < cur->_n)
{
if (key < cur->_keys[i])
{
// 继续向右查找
i++;
}
else if (key > cur->_keys[i])
{
// 该元素可能在i的左边的孩子节点中
break;
}
else
{
// 找到返回
return make_pair(cur, i);
}
}
// 往孩子节点跳
parent = cur;
cur = cur->_subs[i];
}
return make_pair(parent, -1)
}2、插入函数 Insert()
🐎 步骤：
-
如果树为空，直接插入新节点中，该节点为树的根节点
-
如果树非空，找待插入元素在树中的插入位置(注意：找到的插入节点位置一定在叶子节点中)
-
检测是否找到插入位置(假设树中的key唯一，即该元素已经存在时则不插入)
-
按照插入排序的思想将该元素插入到找到的节点中
-
检测该节点是否满足B-树的性质：即判断该节点中的元素个数是否小于M，如果小于说明空间没满，则满足
-
如果空间满了，则需要对该节点进行分裂：
- 申请新节点 brother
- 找到该节点的中间位置 mid
- 将该节点中间位置 mid右侧的元素以及其孩子搬移到新节点中，即 [mid+1, M-1] 范围的元素
- 将 中间位置元素_keys[mid] 以及 新节点brother 往该节点的 双亲节点parent 中插入，即继续步骤4
-
如果向上已经分裂到根节点的位置，则插入结束
以序列{36, 139, 75, 49, 145, 53, 50, 47, 101}构建B树，过程如下：
🔴 最重要的就是裂变以及插入时候，不只是关键字在移动，还要注意的是孩子节点也有可能在移动；除此之外还有双亲结点指针也要记得链接上，只是图中没有画出！
bool Insert(const K& key)
{
// 如果树为空，直接插入新节点中
if (_root == nullptr)
{
_root = new Node;
_root->_n++;
_root->_keys[0] = key;
return true;
}
// 树不为空，首先找到要插入的位置
pair<Node*, int> ret = Find(key);
if (ret.second != -1)
{
// 存在该节点则直接返回false
return false;
}
Node* cur = ret.first;
K newKey = key;
Node* child = nullptr;
while (cur != nullptr)
{
InsertKey(cur, newKey, child);
// 判断一下是否需要裂变
if (cur->_n < M)
{
// 若空间还没满则无需裂变
return true;
}
else
{
Node* brother = new Node;
size_t mid = M / 2;
// 分裂拷贝key和key的左孩子到brother中去
size_t i = mid + 1;
size_t j = 0;
for (; i < M; ++i)
{
brother->_keys[j] = cur->_keys[i];
brother->_subs[j] = cur->_subs[i];
// 注意要判断一下这个孩子节点的双亲结点是否需要链接到brother
if (brother->_subs[j])
{
brother->_subs[j]->_parent = brother;
}
++j;
// 拷走时候重置一下方便观察
cur->_keys[i] = K();
cur->_subs[i] = nullptr;
}
// 记得还有多出来的最后一个孩子要拷贝过去
brother->_subs[j] = cur->_subs[i];
if (brother->_subs[j])
{
brother->_subs[j]->_parent = brother;
}
cur->_subs[i] = nullptr;
// 将这些节点的有效个数更新一下
brother->_n = j;
cur->_n -= (j + 1);
// 先将cur中mid处的值记录下来，并将cur中的mid处设为默认值
K midKey = cur->_keys[mid];
cur->_keys[mid] = K();
// 判断一下是否存在parent
if (cur->_parent != nullptr)
{
// 存在的话则说明parent中有元素，可能会导致继续分裂
// 所以将cur变成parent继续循环判断
newKey = midKey;
cur = cur->_parent;
child = brother;
}
else
{
// 不存在的话，要先定义一个parent
Node* parent = new Node;
parent->_keys[0] = midKey;
parent->_subs[0] = cur;
parent->_subs[1] = brother;
parent->_n = 1;
// 将双亲节点链接上
brother->_parent = parent;
cur->_parent = parent;
// 最后让parent作为root
_root = parent;
break;
}
}
}
return true;
}
void InsertKey(Node* parent, const K& key, Node* child)
{
int end = parent->_n - 1;
while (end >= 0)
{
if (parent->_keys[end] > key)
{
// 注意要同时挪动key和他的右孩子
parent->_keys[end + 1] = parent->_keys[end];
parent->_subs[end + 2] = parent->_subs[end + 1];
--end;
}
else
{
break;
}
}
parent->_keys[end + 1] = key;
parent->_subs[end + 2] = child;
// 记得若child不为空则要将其双亲结点连接到parent
if (child != nullptr)
{
child->_parent = parent;
}
// 最后将有效个数更新
parent->_n++;
}中序遍历代码：
void _InOrder(Node* cur)
{
if (cur == nullptr)
return;
// 左 根 左 根 ... 右
size_t i = 0;
for (; i < cur->_n; ++i)
{
_InOrder(cur->_subs[i]); // 左子树
cout << cur->_keys[i] << " "; // 根
}
_InOrder(cur->_subs[i]); // 最后的那个右子树
}
void InOrder()
{
_InOrder(_root);
}测试代码：
void Test()
{
int a[] = { 36, 139, 75, 49, 145, 53, 50, 47, 101 };
BTree<int, 3> t;
for (auto e : a)
{
t.Insert(e);
}
t.InOrder();
}
运行结果：
36 47 49 50 53 75 101 139 1453、删除操作
大概了解即可，下面几篇文章可以看看~
4、B-树的性能分析
对于一棵节点数为 N，度为 M 的 B- 树，查找和插入需要 ~ 次比较，这个很好证明：对于度为 M 的 B- 树，每一个节点的子节点个数为 M/2 ~(M-1) 之间，因此树的高度应该在要 和 之间，在定位到该节点后，再采用二分查找的方式可以很快的定位到该元素。BTree上大部分操作所需的磁盘读取次数与B树的高度成正比。
B-树的效率是很高的，对于N = 62*1000000000个节点，如果度 M 为 1024，则 <=4 ，即在 620 亿个元素中，如果这棵树的度为 1024 ，则需要小于 4 次即可定位到该节点，然后利用二分查找可以快速定位到该元素，大大减少了读取磁盘的次数。
5、磁盘IO与预读
计算机存储设备一般分为两种：内存储器(main memory)和外存储器(external memory)。
（1）内存储器为内存，内存存取速度快，但容量小，价格昂贵，而且不能长期保存数据(在不通电情况下数据会消失)。
（2）外存储器即为磁盘读取，磁盘读取数据靠的是机械运动，每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分，寻道时间指的是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下；旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms；传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。
考虑到磁盘IO是非常高昂的操作，计算机操作系统做了一些优化，当一次IO时，不光把当前磁盘地址的数据，而是把相邻的数据也都读取到内存缓冲区内，因为局部预读性原理告诉我们，当计算机访问一个地址的数据的时候，与其相邻的数据也会很快被访问到。每一次IO读取的数据我们称之为一页(page)。具体一页有多大数据跟操作系统有关，一般为4k或8k，也就是我们读取一页内的数据时候，实际上才发生了一次IO，这个理论对于索引的数据结构设计非常有帮助。
事实1 ： 不同容量的存储器，访问速度差异悬殊。
磁盘(ms级别) << 内存(ns级别)， 100000倍 若内存访问需要1s，则一次外存访问需要一天 为了避免1次外存访问，宁愿访问内存100次…所以将最常用的数据存储在最快的存储器中
事实2 ： 从磁盘中读1B，与读写1KB的时间成本几乎一样
从以上数据中可以总结出一个道理，索引查询的数据主要受限于硬盘的I/O速度，查询I/O次数越少，速度越快，所以B树的结构才应需求而生；B树的每个节点的元素可以视为一次I/O读取，树的高度表示最多的I/O次数，在相同数量的总元素个数下，每个节点的元素个数越多，高度越低，查询所需的I/O次数越少；假设，一次硬盘一次I/O数据为8K，索引用int(4字节)类型数据建立，理论上一个节点最多可以为2000个元素，2000*2000*2000=8000000000，80亿条的数据只需3次I/O（理论值），可想而知，B树做为索引的查询效率有多高；另外也可以看出同样的总元素个数，查询效率和树的高度密切相关。
Ⅲ. B+树
1、B+树的概念
B+树是应文件系统所需而产生的B树的变形树，那么可能一定会想到，既然有了B树，又出一个B+树，那B+树必然是有很多优点的。
B+树是B树的变形，是在B树基础上优化的多路平衡搜索树，B+树的规则跟B树基本类似，但是又在B树的基础上做了以下几点改进优化：
- 分支节点的关键字与子树指针个数相同。
- 分支节点的子树指针
p[i]指向关键字值大小在 [k[i]，k[i+1]) 区间。 - 所有叶子节点增加一个链接指针链接在一起（方便遍历和区间查找）
- 所有关键字及其映射数据都在叶子节点出现（也就是说每次都要查找到叶子节点）
上图就是一颗三阶B+树，B+树的搜索与B-树基本相同，区别是B+树只有达到叶子节点才能命中(B-树可以在非叶子节点中命中)，其性能也等价与在关键字全集做一次二分查找。其中DATA指向最左叶子节点Q，且连接着下一个叶子节点的Q，以此循环.
等我们下面讲了B*树再来讲B+树的分裂方式！
2、B+树的特性
-
所有关键字都出现在叶子节点的链表中(稠密索引)，且链表中的节点都是有序的。
-
不可能在非叶子节点中命中。
-
非叶子节点相当于是叶子节点的索引(稀疏索引)，叶子节点相当于是存储数据的数据层。
-
更适合文件索引系统
3、B+树的操作
-
检索
在B+树中检索关键码key的方法与B树的检索方式相似，但若在内部节点中找到检索的关键码时，检索并不会结束，要继续找到B+树的叶子结点为止。
-
插入
与B树的插入操作相似，总是插到叶子结点上。当一个结点满时，分配一个新的结点，并将原结点中一半的数据复制到新结点，最后在父结点中增加新结点的指针。
-
删除
仅在叶节点删除关键码。若因为删除操作使得节点中关键码数少于 m/2（向下取整）时，则需要调整（向兄弟借）或者和兄弟节点合并。合并的过程和B树类似，区别是父节点中作为分界的关键码不放入合并后的节点中。
4、B-树与B+树的差别
| B+树 | B树 |
|---|---|
| 有 m 颗子树的节点中含有 m 个关键码 | 有 m 颗子树的节点中含有 m-1 个关键码 |
| 所有的叶子结点中包含了完整的索引信息，包括指向含有这些关键字记录的指针，中间节点每个元素不保存数据，只用来索引 | B树中非叶子节点的关键码与叶子结点的关键码均不重复，它们共同构成全部的索引信息 |
| 所有的非叶子节点可以看成是高层索引， 结点中仅含有其子树根结点中最大（或最小）关键字 | B树的非叶子节点包含需要查找的有效信息 |
| B+树的叶子结点都会被连成一条链表，叶子本身按索引值的大小从小到大进行排序 | 不利于范围查找(区间查找)，如果要找 0~100的索引值，那么B树需要多次从根结点开始逐个查找 |
5、为什么说B+树比B-树更适合做数据库索引？
- B+树的磁盘读写代价更低 B+树的分支节点并没有指向关键字具体信息的指针。因此其分支节点相对B树更小。如果把同一分支节点的关键字放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读取内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了。
- B+树查询效率更稳定 由于非终端节点并不是最终指向文件内容的节点，而只是叶子节点关键字的索引。索引任何关键字的查找必须走一条根节点到叶子节点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当。
- B+树便于范围查询（最重要的原因，范围查找是数据库的常态） B树再提高了IO性能的同时并没有解决掉元素遍历低下的问题，正是为了解决这个问题，B+树应用而出，B+树只需要去遍历叶子节点就可以实现整棵树的遍历。而且再数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作或者说效率太低。
⏺ 补充：B树的范围查找用的是中序遍历，而B+树用的是在链表上遍历
Ⅳ. B*树
1、B*树的概念
B*树是B+树的变形，只是在B+树的非根和非叶子节点再增加指向兄弟节点的指针，并且在分裂的机制上有所改变，这是为了让树得到更加丰满的形态而产生的。而其他的细节与B+树的类似的！
2、B+树与B*树的分裂对比
🌘 定义：B*树定义了非叶子节点关键字个数至少为 ，即每个非叶子节点的最低使用率提升到了 ，这就代表着会比B+树更加的丰满！
- B+树的分裂：
当一个结点满时，分配一个新的结点，并将原结点中 的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针。
- B*树的分裂：
- 当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；
- 如果下一个兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制 的数据到新结点（也就是说新节点是占 ），最后在父结点增加新结点的指针。
这里就不画详细的过程图了，跟B树是类似的只不过细节不同而已！
🆎 所以，B*树分配新结点的概率比B+树要低，空间使用率更高；
Ⅴ. B树系列的小总结
1、B树系列的总结
- B-树:
- 多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点;所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中
- 有序数组+平衡多叉树
- B+树:
- 在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引; B+树总是到叶子结点才命中
- 有序数组链表+平衡多叉树
- B*树:
- 在B+树基础上，为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3
- 是一颗更丰满、空间利用率更高的B+树
2、B树系列隐含的缺点
- 空间利用率不能达到最佳，若数据较多的时候，空间消耗还是很大的（虽然对磁盘来说空间不是个大问题）
- 由于插入的数据是用数组的形式存放的，那么分裂和合并节点的时候可以想要挪动数据，就会导致效率变低
- 虽然高度很低，但是在内存中，B树系列跟哈希表、平衡搜索树的效率是一个量级的
Ⅵ. B树系列的应用
1、索引
B-树最常见的应用就是用来做索引。索引通俗的说就是为了方便用户快速找到所寻之物，比如：书籍目录可以让读者快速找到相关信息，hao123网页导航网站，为了让用户能够快速的找到有价值的分类网站，本质上就是互联网页面中的索引结构。
MySQL官方对索引的定义为：索引 (index) 是帮助 MySQL 高效获取数据的数据结构，简单来说：索引就是数据结构。
当数据量很大时，为了能够方便管理数据，提高数据查询的效率，一般都会选择将数据保存到数据库，因此数据库不仅仅是帮助用户管理数据，而且数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用数据，这样就可以在这些数据结构上实现高级查找算法，该数据结构就是索引。
2、MySQL 索引简介
mysql是目前非常流行的开源关系型数据库，不仅是免费的，可靠性高，速度也比较快，而且拥有灵活的插件式存储引擎，如下：
MySQL中索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的。
♻️ 注意：索引是基于表的，而不是基于数据库的。
3、MyISAM
MyISAM 引擎是 MySQL5.5.8 版本之前默认的存储引擎，不支持事物，支持全文检索。其使用B+树作为索引结构，叶节点的data域存放的是数据记录的地址。
🈂️ 为什么采用B+树呢而不是B-树呢？
- 我们从上面可以知道B+树的分支节点全都是索引值，占用的空间更小，这样子的话可以更多的加载到缓存Cache中去，提高速度；
- 除此之外，因为叶子节点都是连接起来的，这样子的话便于范围查找，且对于没有索引的字段进行全文扫描的时候也是很方便的。
其结构如下：
上图是以 Col1 为主键，MyISAM 的示意图，可以看出 MyISAM 的索引文件仅仅保存数据记录的地址。在 MyISAM** 中，主索引和辅助索引（ Secondary key **）在结构上没有任何区别，只是主索引要求 key 是唯一的，而辅助索引的 key 可以重复。如果想在 Col2 上建立一个辅助索引，则此索引的结构如下图所示：
同样也是一棵 B+树，data 域保存数据记录的地址。因此，MyISAM 中索引检索的算法为首先按照 B+树 搜索算法搜索索引，如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。
MyISAM的索引方式也叫做 “非聚集索引” 的，这是为了方便索引树和主键树可以映射同样的数据。
但是现在的版本就不再使用 MyISAM 为默认索引引擎了，因为它不支持事务，而要知道的是我们现在生活中存在着大量的事务。比如说微信支付，这个时候要考虑收入和支出的问题，还有就是如果支付失败了，那么钱得返回去，这就是一些事务。这也是为什么 MyIASM 会被淘汰的理由。而我们下面要介绍的 InnoDB 就是支持事务的！
🔴 注意：表只有一张，而索引树是有多颗的，指向同一张表！
4、InnoDB
InnoDB 存储引擎支持事务，其设计目标主要面向在线事务处理的应用，从MySQL 数据库 5.5.8 版本开始，InnoDB 存储引擎是默认的存储引擎。InnoDB支持B+树索引、全文索引、哈希索引。但InnoDB使用B+Tree作为索引结构时，具体实现方式却与MyISAM截然不同，体现在节点的存储内容上。
第一个区别是InnoDB 的数据文件本身就是索引文件。MyISAM** 索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。而InnoDB 索引，表数据文件本身就是按 B+Tree 组织的一个索引结构，这棵树的叶节点 data 域保存了完整的数据记录。这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。第二个区别是InnoDB** 的辅助索引 data 域存储相应记录主键的地址而不是值，所有辅助索引都引用主键作为data域。
上述内容看起来有点绕，但其实不难，好好听这段解释就懂了！
以下图为例，就是以 id 为主键，其中一个叶子节点数据本身就是一个表的一部分数据，这样子的话方便我们对数据的操作。同时若是有其它索引，比如下图中的 name 为索引，那么我们不可能再去 name 的索引树里面存一份数据呀，那太大了，所以一个很妙的方法就是除了主键树以外的其他索引树的节点都是指向主键树叶子节点的地址，而通过索引树找到对应的地址再到主键树去查找对应数据的时候，这个过程叫做回表！
可以看到叶节点包含了完整的数据记录，这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以 InnoDB 要求表必须有主键（ MyISAM 可以没有），如果没有显式指定，则 MySQL 系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则 MySQL 自动为 InnoDB 表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整型。
聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
