1.B树的介绍
2.B树节点的定义及其实现
2.1B树节点的定义:
2.2B树的查找
2.2B树的插入
2.3B树的删除
3.B+树和B*树
4.总结
1970年,R.Bayer和E.mccreight提出了一种适合外查找的树,它是一种平衡的多叉树,称为B树(有些地方写
的是B-树,注意不要误读成"B减树")。一棵M阶(M>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足一下性质:
我们之前学习了一些基础的搜索结构,如下表所示:
| 种类 | 数据格式 | 时间复杂度 |
| 顺序查找 | 无要求 | O(N) |
| 二分查找 | 有序 | O(log N) |
| 二叉搜索树 | 无要求 | O(N) |
| 平衡搜索树 | 无要求 | O(logN) |
| 哈西 | 无要求 | O(1) |
| 位图 | 无要求 | O(1) |
| 布隆过滤器 | 无要求 | O(k) |
既然有了这些搜索的数据结构为什么还有引入B树这种数据结构呢?我们之前学过的平衡搜索二叉树已经足够优秀了,时间复杂度O(log N)已经非常的优秀了,10亿数据只要查找30次左右。这是因为:如果数据量非常大,一次性无法加载到内存中,使用上述结构就
不是很方便。比如:使用平衡树搜索一个大文件:
而IO的速度是很慢的。
解决方案:
下面我们来看例子:
如果我们使用二叉搜索树作为索引结构,假设树的高度为4,查找10流程如下
二叉搜索树的结构:
** 第一次磁盘IO**:
第二次磁盘IO:
**第三次IO: **
第四次IO:
我们可以发现磁盘的IO次数是由二叉搜索树的高度决定。所以才引入了B树
下面我们以三阶的B树为例:
这棵树中,咱们重点来看(2,6)节点。该节点有两个元素2和6,又有三个孩子1,(3,5),8。其中1小于元素2,(3,5)在元素2,6之间,8大于(3,5),正好符合刚刚所列的几条特征。
下面来看一下B树的查询过程:假设我们要找的是5
**第一次IO: **
在内存中和9进行比较:
第2次磁盘IO:
** 在内存中和2,6比较:**
第3次磁盘IO:
在内存中和3,5进行比较:
通过整个流程我们可以看出,B-树在查询中的比较次数其实不比二叉查找树少,尤其当单一节点中的元素数量很多时。可是相比磁盘I0的速度,内存中的比较耗时几乎可以忽略。所以只要树的高度足够低,IO次数足够少,就可以提升查找性能。相比之下节点内部元素多一些也没有关系,仅仅是多了几次内存交互,只要不超过磁盘页的大小即可。这就是B-树的优势之一
template<class K,class V,size_t M>
struct BTreeNode {
BTreeNode()
:_kvSize(0)
, _parent(nullptr)
{
for (size_t i = 0; i < M+1; i++) {//初始化
_subs[i] = nullptr;
}
}
pair<K, V>_kvs[M];//值
BTreeNode<K, V,M>* _subs[M+1];//孩子的数量注意我们在这里面多看了一个空间方便后面的分裂
BTreeNode<K, V,M>* _parent;//父亲指针
size_t _kvSize;//个数
};
注意在这里我们多看了一个空间,方便后序插入节点时的分裂。
在上面已经介绍过B树的查找在这里就只给出代码:
pair<Node*, int> Find(const K& key)
{
Node* parent = nullptr;//记录父亲节点
Node* cur = _root;//从根开始找
while (cur)
{
size_t i = 0;
while (i < cur->_kvSize) // 如果M比较大,这里应该改一改换成二分查找会快一些
{
if (cur->_kvs[i].first < key) // key大于当前位置key,往右找
++i;
else if (cur->_kvs[i].first > key) // key小于当前位置key,就往左孩子去找
break;
else
return make_pair(cur, i);//找到了并返回对应的位置
}
parent = cur;//记录父亲节点
cur = cur->_subs[i];
}
// 没有找到并将父亲节点返回
return make_pair(parent, -1);
}
比如我们要在这颗B树上插入4:
自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间。
节点3,5已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。根节点9是单元素节点,可以升级为两元素节点。于是拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个孩子。
拆分时要将孩子节点也要带走:
对应代码:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)//空树直接创建新节点
{
_root = new Node;
_root->_kvs[0] = kv;
_root->_kvSize = 1;
return true;
}
pair<Node*, int> ret = Find(kv.first);//先进行查找
// 已经有了,不能插入 (当前如果允许插入就是mutil版本)
if (ret.second >= 0)
{
return false;
}
// 往cur节点中插入一个newkv和sub
// 1、如果cur没满就结束
// 2、如果满了就分裂,分裂出兄弟以后,往父亲插入一个关键字和孩子,再满还要继续分裂
// 3、最坏的情况就是分裂到根,原来根分裂,产生出一个新的根,就结束了
// 也就是说,我们最多分裂高度次
Node* cur = ret.first;//当前节点
pair<K, V> newkv = kv;
Node* sub = nullptr;//实现后面的迭代逻辑
while (1)
{
InsertKV(cur, newkv, sub); //插入
// 1、如果cur没满就结束,判断是否要分裂
if (cur->_kvSize < M)
{
return true;
}
else // 2、满了,需要分裂
{
// 分裂出一个兄弟节点
Node* newnode = new Node;
// 1、拷贝右半区间给分裂的兄弟节点
//
int mid = M / 2;
int j = 0;
int i = mid + 1;
newkv = cur->_kvs[mid];
cur->_kvs[mid] = pair<K, V>();//清空原来的节点的值
for (; i < M; ++i)//拷贝值并拷贝孩子节点
{
newnode->_kvs[j] = cur->_kvs[i];
cur->_kvs[i] = pair<K, V>();
newnode->_subs[j] = cur->_subs[i];
cur->_subs[i] = nullptr;
if (newnode->_subs[j])//链接父亲指针
{
newnode->_subs[j]->_parent = newnode;
}
j++;
newnode->_kvSize++;//个数增加
}
// 还剩最后一个右孩子
newnode->_subs[j] = cur->_subs[i];
cur->_subs[i] = nullptr;
if (newnode->_subs[j])//是否为空
{
newnode->_subs[j]->_parent = newnode;
}
cur->_kvSize = cur->_kvSize - newnode->_kvSize - 1;//重新计算大小
// 1、如果cur没有父亲,那么cur就是根,产生新的根
// 2、如果cur有父亲,那么就要转换成往cur的父亲中插入一个key和一个孩子newnode
if (cur->_parent == nullptr)//说明当前节点没有父亲是根
{
//创建新的根,并链接关系
_root = new Node;
_root->_kvs[0] = newkv;
_root->_subs[0] = cur;
_root->_subs[1] = newnode;
cur->_parent = _root;
newnode->_parent = _root;
_root->_kvSize = 1;
return true;
}
else
{//有父亲转化为迭代逻辑
// 往父亲去插入newkv和newnode,转换成迭代逻辑
sub = newnode;
cur = cur->_parent;
}
}
}
return true;
}
void InsertKV(Node* cur, const pair<K, V>& kv, Node* sub)
{
// 将kv找到合适的位置插入进去
int i = cur->_kvSize - 1;//从最后一个位置开始
for (; i >= 0; )
{
if (cur->_kvs[i].first < kv.first)
{
break;
}
else
{
//kv[i]往后挪动,kv[i]的右孩子也挪动
cur->_kvs[i + 1] = cur->_kvs[i];
cur->_subs[i + 2] = cur->_subs[i + 1];
--i;
}
}
//插入并将孩子节点也链接上
cur->_kvs[i + 1] = kv;
cur->_subs[i + 2] = sub;
cur->_kvSize++;
if (sub)
{
sub->_parent = cur;//链接父亲节点
}
}
删除比插入复杂的多在这里就只给出思路:
B树中关键字的删除比插入更复杂,在这里,只介绍其中的一种方法:
在B树上删除关键字k的过程分两步完成:
(1)找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。
(2)若该结点为非叶结点,且被删关键字为该结点中第i个关键字key[i],则可从指针_son[i]所指的子树中
找出最小关键字Y,代替key[i]的位置,然后在叶结点中删去Y。
因此,把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。
在B-树叶结点上删除一个关键字的方法:
首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理,共有三种可能情况:
(1)如果被删关键字所在结点的原关键字个数n>=ceil(m/2),说明删去该关键字后该结点仍满足B树的定义。
这种情况最为简单,只需从该结点中直接删去关键字即可。
(2)如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1,说明删去该关键字后该结点将不满足B树的定义,需要调整。
调整过程为:
如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目大于
ceil(m/2)-1。则可将右(左)兄弟结点中最小(大)关键字上移至双亲结点。而将双亲结点中小(大)于该上
移关键字的关键字下移至被删关键字所在结点中。
如果左右兄弟结点中没有“多余”的关键字,即与该结点相邻的右(左)兄弟结点中的关键字数目均等于
ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左(或右)兄弟结点以及双亲结点中分割二者
的关键字合并成一个结点,即在删除关键字后,该结点中剩余的关键字加指针,加上双亲结点中的关键字Ki一起,
合并到Ai(是双亲结点指向该删除关键字结点的左(右)兄弟结点的指针)所指的兄弟结点中去。如果因此使双亲
结点中关键字个数小于ceil(m/2)-1,则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使
整个树减少一层。
总之,设所删关键字为非终端结点中的Ki,则可以指针Ai所指子树中的最小关键字Y代替Ki,然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。
下面举个简单的例子删除11这个节点:
首先找到11这个节点:
删除11后,节点12只有一个孩子,不符合B树规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。(这个过程称为左旋)
B+树是B-树的变形,也是一种多路搜索树,其规则如下:
既然有了B树那为什么还要有B+树了?下面我们从各自的优点出发:
B树:
B树好处:
B树的每一个结点都包含key(索引值) 和 value(对应数据),因此方位离根结点近的元素会更快速。(相对于B+树)
B树的不足:
不利于范围查找(区间查找),如果要找 0~100的索引值,那么B树需要多次从根结点开始逐个查找。
B+树的优点:
1.B+树的层级更少:相较于B树B+每个非叶子节点存储的关键字数更多,树的层级更少所以查询数据更快;
2.B+树查询速度更稳定:B+所有关键字数据地址都存在叶子节点上,所以每次查找的次数都相同所以查询速度要比B树更稳定;
3.B+树天然具备排序功能:B+树所有的叶子节点数据构成了一个有序链表,在查询大小区间的数据时候更方便,数据紧密性很高,缓存的命中率也会比B树高。
4.B+树全节点遍历更快:B+树遍历整棵树只需要遍历所有的叶子节点即可,而不需要像B树一样需要对每一层进行遍历,这有利于数据库做全表扫描。
这就是为什么要有B+树的原因。
B*树:
B*树是B+树的变形,在B+树的非根和非叶子节点再增加指向兄弟节点的指针。
1.B树定义了非叶子结点关键字个数至少为(2/3)M,即块的最低使用率为2/3(代替B+树的1/2) 。
2.B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针﹔B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针。
3.B树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了〉﹔如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;
4.所以,B树分配新结点的概率比B+树要低,空间使用率更高﹔
B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;
所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中﹔
B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中﹔
B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/qq_56999918/article/details/122973181
内容来源于网络,如有侵权,请联系作者删除!