1.前言
相信大家或多或少的都听过B树,本篇文章将带领大家一步一步学习B树,从了解他的概念到模拟实现他的插入过程。
本章重点:
了解B树的相关概念后,由于后续学习B树的插入过程较难,所以会一步一步的对他的插入进行分析。
B树是非常难得,请大家耐心耐心再耐心的学习。
2.为什么要用B树
在正式学习B树之前,先需要明确的是,B树是一种搜索结构,那么它和传统的搜索结构相比,有什么区别呢?
以上的数据结构只能够适用于数据量不太大,能够一次性放入内存中,进行查找的场景。那么对于数据量很大,例如有100G的数据在磁盘里面,那么这么大的数据是无法一次性放入内存的,但是你又需要再这些数据中找到你想要的数据,那么应该怎么办呢?用什么数据结构呢?---这个时候B树就闪亮登场了,B树中存储的是数据在磁盘中的地址,通过B树,就能够在磁盘中找到对应的数据,只需要读取这一个数据进内存即可了。
PS:对于那些能够直接在内存中查找的数据结构,我们称之为内查找。而对于B树这种数据结构来说,我们称之为外查找。
当然也有同学会说,那么为什么不能用AVL树、红黑树和哈希表呢?他们的性能也是很优秀的呀。
下面举一个例子来说明为什么不用AVL树,红黑树等数据结构。
例如:
如果使用的是平衡二叉搜索树的话,那么你查找到某一个数据的时间复杂度就是O(LogN),就是说你要查找这么多次,那么LogN次在内存中其实是相当快得了,但是如果是放在磁盘上的话,访问磁盘的速度是很慢的,那么LogN的次数就无法让人接受了。
在磁盘中,其实读数据是一个很快的过程,但是读的前提是找到数据,这个过程就非常的慢了。
如果使用的是哈希表的话,哈希表的访问效率是极高的,常数次就够了。但是在一些极端的情况下某些位置冲突较多,那么就容易导致访问次数增多,这也是无法让人接受的。
那么有没有一种数据结构能够加快对数据的访问呢?
1.提高IO的次数(SSD相对于传统的机械硬盘来说快了不少,但是本质上还是没有得到提升的)
2.把这棵平衡二叉搜索树进行压缩,只要把高度压缩下来,那么次数也就下来了,也能够达到要求。
3.B树的概念
在学习概念之前,先明确一点,有些地方把B树写成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。
解释:第六点的意思是:n表示当前块里面有效的关键字的个数,A0<K1指针里面的值<A1<K2指针里面的值.........;依次类推
光看B树的定义是非常抽象的, 甚至于是看不懂,但定义中的关键点是每个节点中的关键字是有序的, 并且节点的结构是: 关键字,孩子,关键字,孩子…实际上当M=2时,B树就是一颗二叉树, B树的节点中是一个数组,可存放多个数据。
4.B树的插入分析
现在使用一个案例,来解释B树的这些性质. 设M=3,即三叉树,每个节点存两个数据,和三个孩子区域的划分。采用如下结构来进行分析,也方便后续好写代码
PS:这里记住,孩子是永远都比数据要多一个的。
用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下:
第一步:
由于M=3,一个节点只能存储两个数据,所以当插入75时,需要对这棵树做分裂. 怎样分裂呢?方法如下: 1. 找到节点中的中间数据(图中为75). 2. 创建一个新节点, 将中间数据挪动到新节点. 3. 以中间数据(75)作为分割, 将中间数据左边的所有节点保持不动, 将中间数据右边的所有节点移动至另外一个新节点. 4. 将中间数据所在的新节点当父亲, 左右两个兄弟节点当儿子, 连接起来. 具体结果看下图:
第二步分裂如下:
此时分裂之后的结果是满足B树的性质6的,也满足B树的其他性质。
第三步:
插入49和145
PS:B树的插入都是在叶子节点进行的,当叶子节点不符合B树规则时才会向上形成新的节点,也就是所谓的分裂操作
发现这两次均没有违反B树的概念。
第四步:插入36
违反规则,进行调整
这一次插入36,会导致左下角的节点违反B树的规则,所以需要进行分裂. 本次分裂和上次分裂基本一致,唯一的区别就是, 中间数据,也就是49,不需要再重新形成一个新节点并将49放入,数据49可以直接被放在数据75所在的节点中. 具体的结果图如下:
第五步:插入101
这里分裂的变化和上述一样,直接给出最终结果。
经过分析上述插入过程,总结如下:
5.B树的插入模拟实现
先搭建B树的基本框架:
template <class K,size_t M>
struct BTreeNode
{K _keys[M];//本来是M-1个关键字,但是开辟了M个,可以方便后续分裂BTreeNode<K, M>* _subs[M + 1];BTreeNode<K, M>* _parent;int _num;//记录有多少个关键字BTreeNode(){for (size_t i = 0; i < M; i++){_keys[i] = K();_subs[i] = nullptr;}_subs[M] = nullptr;_parent = nullptr;_num = 0;}
};//数据是存在磁盘,K是磁盘地址
template<class K,size_t M>
class BTree
{typedef BTreeNode<K, M> Node;
public:
private:Node* _root = nullptr;
};
在插入之前要先找到,于是先实现找到的代码
pair<Node*, int> Find(const K& key)
{//找到了返回该值所在位置的节点和在节点中的下标//没找到就返回要插入的叶子节点Node* cur = _root;Node* parent = nullptr;while (cur){int i = 0;//下面的逻辑表示在一个节点中查找while (i < cur->_num){if (key < cur->_keys[i])break;//去左边的话,那么subs中下标与key中相同else if (key > cur->_keys[i])i++;//去右边的话,那么就一样else return make_pair(cur, i);}parent = cur;cur = cur->_subs[i];}return make_pair(parent, -1);
}
由于是在一个节点里面插入,所以找到之后那么返回的是一个节点,但是一个节点有存储数据的数组还有储存节点的孩子,所以还需要知道的是需要插入在数组的哪一个位置的前面 ,所以设计成了pair类型。
在插入的过程中,要先插入然后再判断是否需要分裂,所以插入的代码单独实现
//在一个节点里面插入值key和孩子
//void InsertKey(Node* node, const K& key)
//{
// //下面插入代码有问题,在插入36时,53这个兄弟节点直接没有了。
// int end = node->_num - 1;
// //插入排序,若插入的数据较小,原先的数据会往后移动
// while (end >= 0)
// {
// if (node->_keys[end] > key)
// {
// //挪动key
// node->_keys[end + 1] = node->_keys[end];
// end--;
// }
// else break;
// }
// //插入在end位置的后面,可能比所有值都小,end+1=0
// node->_keys[end + 1] = key;
// node->_num++;
//}//在一个节点里面插入值key和孩子---修改版
void InsertKey(Node* node, const K& key, Node* children)
{//修改版int end = node->_num - 1;//插入排序,若插入的数据较小,原先的数据会往后移动while (end >= 0){if (node->_keys[end] > key){//不仅要挪动key,还要挪动它的右孩子node->_keys[end + 1] = node->_keys[end];node->_subs[end + 2] = node->_subs[end + 1];end--;}else break;}//插入在end位置的后面,可能比所有值都小,end+1=0node->_keys[end + 1] = key;node->_subs[end + 2] = children;if (children)children->_parent = node;node->_num++;
}
下面主要实现分裂的过程,要插入时直接调用函数即可
bool Insert(const K& key)
{if (_root == nullptr){_root = new Node;_root->_keys[0] = key;_root->_num++;return true;}K key1 = key;pair<Node*, int> ret = Find(key1);if (ret.second >= 0){//B树里面已经有了,不能重新插入cout << "B树里面已经有这个值了,请勿重新插入" << endl;return false;}//到这里就找到了要插入的所在节点了Node* cur = ret.first;//要插入的节点K newkey = key;Node* children = nullptr;//循环每次往cur插入newkey和childwhile (1){InsertKey(cur, newkey, children);if (cur->_num < M){return true;}else{//走到这里就要进行分裂了int mid = (int)M / 2;Node* brother = new Node;int j = 0;for (int i = mid + 1; i<= M - 1; i++){//带走一个值那么就等同于要带走一个孩子--始终记得孩子是要比值多一个的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;j++;}brother->_num += j;cur->_num -= (j + 1);//+1表示还要把mid分走//拷贝完后还有最后一个右孩子,最右的孩子需要拷贝走brother->_subs[j] = cur->_subs[M];if (cur->_subs[M])cur->_subs[M]->_parent = brother;cur->_subs[M] = nullptr;//分裂后转换成往cur->parent插入mid和brotherK midKey = cur->_keys[mid];//cur等于空证明分裂的是根节点cur->_keys[mid] = K();if (cur->_parent == nullptr){_root = new Node;_root->_keys[0] = midKey;_root->_subs[0] = cur;_root->_subs[1] = brother;_root->_num = 1;cur->_parent = _root;brother->_parent = _root;break;}else {newkey = midKey;//中位数给父亲了,也重置一下children = brother;cur = cur->_parent;}}}return true;
}
对于B树的插入来说, 步骤就是上面分析过的步骤,但是代码实现是比较抽象,比较难懂的, B树的模拟实现本身就属于拓展内容, 如果你理解不了也是没关系的, 知道B树的性质和用途就好了。
6.总结
上述代码的重点是它的分裂逻辑和使用场景, 并且B树在实际生产中运行并不会很多多, 因为有更好的数据结构: B+树或是B*树来代替它. 但是学习后两者的前提是需要你知晓B树的性质, 所以学习要一步一步来,不能一步登天。