【高阶数据结构】B树

> 作者：დ旧言~
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：了解什么是B树，并能简单的模拟实现。

> 毒鸡汤：有些事情，总是不明白，所以我不会坚持。早安!

> 专栏选自：数据结构

> 望小伙伴们点赞👍收藏✨加关注哟💕💕

一、常见的搜索结构

常见搜索结构：

在实际软件开发项目中，常用的查找结构和方法，包括顺序查找、二分查找、二叉搜索树、平衡二叉树、哈希表等，这几种查找方法和数据结构，都适合于内查找（将数据加载到内存中查找）。

说明：

如果数据量极大，内存无法存放时，就需要将数据存储在磁盘当中，而CPU访问磁盘的速度要远远低于访问内存的速度，假设O(1)的时间复杂度下要执行2次访问，O(logN)的时间复杂度下要执行30次访问。如果对内存数据进行访问，因为访问内存速度相对较快，所有我们可以认为O(1)和O(logN)时间复杂度算法的性能是一致的。但是如果是对于磁盘上的数据的访问，由于磁盘数据访问的效率较低，因此O(1)和O(logN)差别会很大。

采用二叉搜索树检索磁盘数据的缺陷为：

二叉搜索树查找的时间复杂度为O(logN)，磁盘IO效率低，O(logN)的时间复杂度相对于O(1)会很大程度上降低性能。

哈希查找的时间复杂度是O(1)，为什么哈希也不适用于对磁盘数据的检索呢？这是因为哈希的有这样的缺陷：

在极端情况下，哈希表中会产生大量的哈希冲突，查找的时间复杂度会接近O(N)。
虽然很多时候当哈希冲突达到一定数量时，在哈希散列中会由挂单链表改为挂红黑树，但红黑树查找的时间复杂度依旧是O(logN)。

总结：

为了解决平衡二叉树和哈希表无法很好的应对内存数据查找的情况，B树被创造和出来，B树适用于对磁盘中大量的数据进行检索，当然B树也能够在内存在查找数据，但效果就不如哈希和平衡二叉树。
由于B树/B+树适用于检索磁盘中大量数据的性质，经常被用于作为数据库的底层检索结构。

二、B树的概念

B树是一种适合外查找的平衡多叉树，一颗m阶的B树，是一颗m路的二叉搜索树，一颗B树要么为空树，要么满足如下几个条件：

根节点至少有两个孩子节点。
分支节点（非叶子节点）应当有K-1个键值和K个孩子节点，其中 $ceil(m/2)\leqslant K\leqslant M$ 其中ceil为向上取整函数。
所有叶子节点都在同一层。
每个节点中的键值都是自小到大升序排序的，键值Key表示子树的阈值划分。
对于任意一个节点，孩子节点的数目总是比键值多一个。

简单了解如何插入数据和检索数据：

插入数据：

两个键值为50和100，根节点的第一个孩子节点键值全部小于50，第二个孩子节点的键值位于(51,100)之间，第三个孩子节点键值大于100，这就是键值Key的阈值划分功能。

检索数据：

先从根节点开始找起，对比待查找的值和键值的大小，发现其位于(50,100)范围内，这样就向下遍历查找p2子树，在p2子树的键值中找到了键值99，检索完成。

三、B树的插入过程分析

3.1 元素插入的步骤

由于B树的插入操作过于抽象，因此直接上实例，在示例中讲解B树节点插入的具体操作。假设依次将std::vector<int> v = { 53,139,75,49,145,36,50,47,101}插入到3阶B树中。为了方便插入操作，我们在申请B树节点空间的时候，阶数为M，就为键值申请M个空间，为孩子节点申请M+1个空间，这样做的目的是方便插入时数据挪动，以及后面的分裂操作。

① 插入53：

53是B树插入的第一个节点，因此直接将其插入到根节点的第一个键值位置处即可。插入53后，有一个B树根节点，这个根节点附带有两个孩子节点nullptr。这里的根节点也是叶子节点，注意B树插入新节点一定是向叶子节点插入的。

② 插入139：

139大于53，且插入后根节点（叶子结点）中键值的数目不超过M-1，因此只需将139至于53的后面，并且带入null子节点即可。

③ 插入75：

75位于53和139之间，所以第一步要现将75插入到root节点的这两个值之间。但是，插入75后root节点就有了3个键值，这样就不符合B树的结构要求，需要进行分裂。

3.2 分裂操作的步骤

过程：

取中间位置mid = M/2下标处为分界线，创建一个兄弟节点brother，将下标位于[mid+1,M)的键值及其左右孩子都拷贝到brother节点中去（设下标为键值相同的孩子节点为左孩子，比键值下标大1的孩子节点称为右孩子）。
将mid处的键值交给其父亲节点，如果没有父亲节点节创建父亲节点，父亲节点的其中两个孩子节点就包含原先发生分裂的节点以及分裂出的节点brother。

① 插入49：

首先检索节点插入的位置，发现49小于根节点root的第一个键值，因此找到n1节点，n1节点为叶子节点可以执行插入操作，49小于第一个节点53，所以应当将53向后移动一位并将49设置为n1节点的第一个键值。

② 插入145：

首先检索插入数据的叶子节点，根节点只有一个键值75，145大于75，向n2节点查找，n2为叶子节点可以执行插入操作，将145插入到139后面，插入过后键值个数少于阶数M，不用分裂。

③ 插入36：

查找36的插入位置应该中的n1节点，将35插入n1后n1有3个键值需要进行分裂，兄弟节点取走53，49向上交给n1的父亲节点，分裂出的兄弟节点要作为root节点的一个孩子节点。

④ 插入50：

直接找到n2节点，插入到键值53之前即可。

⑤ 插入47：

插入到n1节点36的后面即可。

⑤ 插入101：

先初步执行插入操作，即101插入到n3节点的第一个键值位置处，插入后n3节点的键值数量达到了阶数M，要执行分裂操作。然而分裂后将mid处键值交给父亲节点（root）管理后，root的键值数量也达到了阶数M，需要进一步分裂，更新root。

四、B树简单模拟实现

4.1 B树的节点设计

说明：

K代表K类型，一般是表示地址，当然也可以是KV模型。
M表示这是M路多叉树。
_subs表示孩子节点的集合，_keys表示关键字的集合，为了防止边界情况的判断，统一多开一个空间。
_n表示一共个有效的关键字。
_parent是父亲节点，维护父亲的原因是我们需要向上传中位数，如果不维护一个父亲节点，会比较难实现，但是增加了一个指针，同时也要十分注意去维护这个指针。

代码实现：

template<class K,size_t M> 
struct BTreeNode
{BTreeNode(){for (size_t i = 0; i < M; ++i){_keys[i] = K();  //K的默认构造_subs[i] = nullptr;}_subs[M] = nullptr;_parent = nullptr;_n = 0;}//关键字永远比孩子少一个  为了方便插入，我们多开一个空间 预防边界情况K _keys[M]; //M-1个关键字BTreeNode<K, M>* _subs[M + 1];// 孩子的集合 M个孩子BTreeNode<K, M>* _parent;//父亲节点  方便插入的时候向上回溯size_t _n; //实际存了多少节点
};
template<class K, size_t M>
class BTree
{typedef BTreeNode<K, M> Node;
public:private:Node* _root=nullptr;
};

4.2 B树的查找

说明：

返回值pair<Node*,int> 前一个返回对应的节点，后一个表示对应节点中的下标。
parent指针的意义：因为我们在插入之前必须要调用这个查找函数，并且必须插入到相应的叶子节点中去。那么我们可以顺便通过这个返回值返回我们要插入的叶子节点。这样在insert函数中接受find函数的返回值的时就可以直接拿到待插入的叶子节点。
因为拓展都是往右拓展的，所以我们必须要确保比key当前元素小，我们才能跳到下一层去找他的左孩子，并且每次都要从第一个位置开始找，如果比当前元素大的话，那么先往后找，而不是直接往该节点的右孩子找。

代码实现：

pair<Node*, int> Find(const K& key)  //查找这个节点以及对应关键字的下标
{Node* cur = _root;Node* parent = nullptr;//如果没找到， 把父亲节点带回来while (cur) //因为i每次都要重头开始算{size_t i = 0; while (i < cur->_n){if (key < cur->_keys[i]) break; //keys[i]的左孩子根他的下标是相等的else if (key > cur->_keys[i]) ++i;     //左才会往下跳  比右小i++else return make_pair(cur, i);}//但是有可能走到空都不会结束  找不到就往自己的孩子去跳parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);
}

4.3 插入key的过程

说明：

只有多次分裂的时候才会出现需要链接新增的节点，如果只有一次分裂的话，child就是nullptr，所以在反向链接的时候要注意。
在插入关键字的时候，我们按照插入排序的逻辑从后开始往前找，不断将比自己大的元素往后挪，挪动的时候要别忘了把他的右子树也跟着往后挪动。
end必须设置成int而不能是size_t，因为是从后往前找的，所以end是有可能会出现负数的。

代码实现：

//每次循环往cur插入newkey和child
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];--end;}else break; //找到了就放}node->_keys[end + 1] = key;node->_subs[end + 2] = child;if (child)  child->_parent = node; // 一定要记得反向链接维护parent指针++node->_n;
}

4.4 B树的插入整体实现

说明：

如果什么也没有，那么自己就成为新的树。
通过find函数去找B树中是否存在这个关键字，如果存在就结束，不存在，那就把返回的pair中的first（待插入的叶子节点）提取出来。
因为有可能会涉及到多次分裂，所以我们要将插入的函数写在循环里面（通过cur、newkey、child来帮助我们迭代），然后每次插入之后就去判断是否还要进行分裂。如果没满就结束，如果满了就分裂。
分裂一半的key和节点（要注意节点的反向链接）给自己的兄弟，然后清理一下数据方便我们调试观察，最后有一个右孩子还得再拷贝一次。
传中位数的时候，如果cur没有父亲，那么就直接造一个父亲出来。如果cur有父亲，就更新一下cur、newkey、child，继续往上迭代去走。将问题转化成往父亲节点插入中位数和一个brother节点。

代码实现：

bool Insert(const K& key)
{if (_root == nullptr) //如果我为空 那我就让自己成为新的根{_root = new Node;_root->_keys[0] = key;++_root->_n;  return true;}//如果不为空  开始执行插入逻辑pair<Node*, int> ret = Find(key);if (ret.second>=0) return false;//如果没有找到，find顺便带回了要插入的叶子节点Node* cur = ret.first;//每次循环往cur插入newkey和childK newKey = key;Node* child = nullptr;while (1){InsertKey(cur, newKey, child);//情况1 没满， 直接结束if (cur->_n < M) return true;Node* brother = new Node;//分裂一半[mid+1,M-1]给兄弟  找到中间那个值size_t mid = M / 2;size_t i = mid + 1;size_t j = 0;for (; i < M; ++i, ++j){//拷贝key和key的左孩子brother->_keys[j] = cur->_keys[i]; brother->_subs[j] = cur->_subs[i]; //节点也拷过去//与父亲建立连接if (cur->_subs[i])  cur->_subs[i]->_parent = brother;//清理一下方便观察cur->_keys[i] = K();cur->_subs[i] = nullptr;}// 还有最后一个右孩子拷过去brother->_subs[j] = cur->_subs[i];if (cur->_subs[i])  cur->_subs[i]->_parent = brother; //孩子如果不是空  那么父亲就得更新一下cur->_subs[i] = nullptr;brother->_n = j;cur->_n -= (brother->_n + 1);//因为还要把中位数往上放K midKey = cur->_keys[mid];cur->_keys[mid] = K();//方便观察//转化成往cur的parent去插入 cur->[mid]和 brother// 说明刚刚分裂是根节点if (cur->_parent == nullptr){_root = new Node; //最坏情况 我的父亲是空，那就造一个新的根出来_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;//链接起来cur->_parent = _root;brother->_parent = _root;break;}else //如果父亲不是空，还可以向上调整{// 转换成往parent->parent 去插入parent->[mid] 和 brothernewKey = midKey;child = brother;cur = cur->_parent;}}return true;
}

4.5 B树的中序遍历验证

说明：

他的整体逻辑是左、根、左、根、左、根……右所以我们可以将前两个过程抽出来，然后最后再单独处理右。走一个中序遍历的逻辑实现有序。

代码实现：

	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);}

4.6 整体的代码

#pragma once
#include<iostream>
using namespace std;//K表示存的地址  M表示最多有几个分支
template<class K,size_t M> 
struct BTreeNode
{BTreeNode(){for (size_t i = 0; i < M; ++i){_keys[i] = K();  //K的默认构造_subs[i] = nullptr;}_subs[M] = nullptr;_parent = nullptr;_n = 0;}//关键字永远比孩子少一个  为了方便插入，我们多开一个空间 预防边界情况K _keys[M]; //M-1个关键字BTreeNode<K, M>* _subs[M + 1];// 孩子的集合 M个孩子BTreeNode<K, M>* _parent;//父亲节点  方便插入的时候向上回溯size_t _n; //实际存了多少节点
};template<class K, size_t M>
class BTree
{typedef BTreeNode<K, M> Node;
public:pair<Node*, int> Find(const K& key)  //查找这个节点以及对应关键字的下标{Node* cur = _root;Node* parent = nullptr;//如果没找到， 把父亲节点带回来while (cur) //因为i每次都要重头开始算{size_t i = 0; while (i < cur->_n){if (key < cur->_keys[i]) break; //keys[i]的左孩子根他的下标是相等的else if (key > cur->_keys[i]) ++i;     //左才会往下跳  比右小i++else return make_pair(cur, i);}//但是有可能走到空都不会结束  找不到就往自己的孩子去跳parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);}//每次循环往cur插入newkey和childvoid 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];--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;}//如果不为空  开始执行插入逻辑pair<Node*, int> ret = Find(key);if (ret.second>=0) return false;//如果没有找到，find顺便带回了要插入的叶子节点Node* cur = ret.first;//每次循环往cur插入newkey和childK newKey = key;Node* child = nullptr;while (1){InsertKey(cur, newKey, child);//情况1 没满， 直接结束if (cur->_n < M) return true;Node* brother = new Node;//分裂一半[mid+1,M-1]给兄弟  找到中间那个值size_t mid = M / 2;size_t i = mid + 1;size_t j = 0;for (; i < M; ++i, ++j){//拷贝key和key的左孩子brother->_keys[j] = cur->_keys[i]; brother->_subs[j] = cur->_subs[i]; //节点也拷过去//与父亲建立连接if (cur->_subs[i])  cur->_subs[i]->_parent = brother;//清理一下方便观察cur->_keys[i] = K();cur->_subs[i] = nullptr;}// 还有最后一个右孩子拷过去brother->_subs[j] = cur->_subs[i];if (cur->_subs[i])  cur->_subs[i]->_parent = brother; //孩子如果不是空  那么父亲就得更新一下cur->_subs[i] = nullptr;brother->_n = j;cur->_n -= (brother->_n + 1);//因为还要把中位数往上放K midKey = cur->_keys[mid];cur->_keys[mid] = K();//方便观察//转化成往cur的parent去插入 cur->[mid]和 brother// 说明刚刚分裂是根节点if (cur->_parent == nullptr){_root = new Node; //最坏情况 我的父亲是空，那就造一个新的根出来_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_n = 1;//链接起来cur->_parent = _root;brother->_parent = _root;break;}else //如果父亲不是空，还可以向上调整{// 转换成往parent->parent 去插入parent->[mid] 和 brothernewKey = midKey;child = brother;cur = cur->_parent;}}return true;}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);}private:Node* _root=nullptr;
};void testBtree()
{BTree<int, 3> t;int a[] = { 53, 139, 75, 49, 145, 36, 101 };for (auto e : a)  t.Insert(e);t.InOrder();
}

五、B+树和B*树

5.1 B+树

B+树是在B树上优化了的多路平衡搜索二叉树，相比于B树，B+树进行了以下几点优化：

每个节点的键值数量和孩子节点数量相同。
孩子节点指针p[i]指向的子B树键值范围位于 [ k[i], k[i+1] ) 之间。
所有存储了有效键值的节点都在叶子节点上。
所有叶子节点都被连接了起来。

B+树的特性：

所有关键字都出现在叶子节点的链表中，且链表中的节点都是有序的。
不可能在分支节点中命中。
分支节点相当于是叶子节点的索引，叶子节点才是存储数据的数据层。

5.2 B*树

B*树是B+树的变形，在B+树的非根和非叶子节点再增加指向兄弟节点的指针：

B+树的分裂：

当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增
加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向
兄弟的指针。

B*树的分裂：

当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结
点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如
果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父
结点增加新结点的指针。所以，B*树分配新结点的概率比B+树要低，空间使用率更高。

六、B树的应用

6.1 索引概述

索引，就是通过某些关键信息，让用户可以快速找到某些事物，例如通过目录，我们就可以快速检索到一本书中特定的内容所在的页码。B/B+最普遍的用途，就是做索引。

MySQL数据库官方给出的索引定义是：

索引（index）是帮助MySQL高效获取数据的数据结构。

当数据量很大的时候，为了方便数据的管理、提高检索效率，通常会将数据保存至数据库。数据库不仅仅要存储数据，还要维护特定的数据结构和一些高效的搜索算法，以帮助用户快速引用到某些数据。这种实现快速查找的数据结构，就是索引。

MySQL是非常流行的开源关系型数据库，不仅免费，而且搜索效率较高，可靠性高，拥有灵活的插件式存储引擎，在MySQL中，索引是属于存储引擎范畴的概念，不同的存储引擎对索引的实现方式是不同的。索引是基于表的而不是基于数据库的。

6.2 MyISAM

在早期的MySQL数据库中，所使用的搜索引擎都是MyISAM，这种搜索引擎不支持事务，支持全文索引，其使用的数据结构是B+树。在MyISAM搜索引擎中，叶子节点中的data域存储的是数据在磁盘中的地址，而不是数据本身。学生信息管理数据库，要记录学生的学号(StuId)、年龄(age)以及姓名，B+树用于检索，中选取的主键为StuId。

在绝大部分数据库中，一般要求加入到数据库中的数据要有一个主键，并且主键是不允许出现重复的。就以所示的学生信息管理系统为例，选取学号能保证每个学生之间的学号不重复，而姓名和年龄则不可避免的出现重复，那么就应当选取学号作为主键。如果没有一个合适的参数作为主键，那么可以采用自增主键，自增主键实际就是一个常数，第一次插入的数据常数1为主键，第二次插入的数据常数2为主键，以此类推。

如果用户通过主键索引查找数据库中的相关信息，那么就会对B树进行检索，直到检索到叶子节点发现匹配项或者确认数据库中没有对应主键即可。如果使用非主键（未建立辅助索引）的参数进行检索，那么进行的操作是全表扫描查找匹配项。

对于MySQL数据库，我们处理使用主键建立主索引之外，还可以建立辅助索引，主索引不允许出现重复项，而辅助索引允许出现重复项，就是通过学生年龄age建立的学生数据库的辅助索引。

6.3 InnoDB

现在高版本的MySQL数据库，全部采用InnoDB为搜索引擎，InnoDB是面向在线事务处理的应用，支持B+树索引、哈希索引、全文索引等。但是，InnoDB使用B+树支持索引的实现方式与MyISAM却有着很大的不同。

InnoDB文件本身就是索引文件的一部分。在InnoDB的中，B+树的叶子节点要存放表的全部数据，数据库中的数据，要按照主键从小到大的顺序排列起来。InnoDB的叶子节点中要包含所有的数据记录，这种索引叫做聚集索引。由于InnoDB数据文件本身要按照主键来聚集，因此InnoDB必须有主键，而MyISAM则可以没有主键。