vlambda博客
学习文章列表

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我

之前在讲解mysql底层算法架构的时候,我提到了一个点:树,这个大学的时候让我们只有恨没有爱的课程中的一员,但是,最近的一段时间里,算法和数据结构成为面试过程汇总弄个地考虑重点,之前的时候图解过红黑树,也以mysql为例,将B+树的相关原理进行了讲解,想要重新回顾一下的朋友,下方可以去查看一下

红黑树:快进收藏吃灰!字节跳动大佬用最通俗方法讲明白了红黑树算法

B+树:字节跳动内部授课课件:附图讲解MySQL底层索引结构算法实现

今天我们来看一下B+树的应用,图解哦,开始之前先来回归一下一些基础的东西

使用场景

文件系统和数据库系统中常用的B/B+ 树,他通过对每个节点存储个数的扩展,使得对连续的数据能够进行较快的定位和访问,能够有效减少查找时间,提高存储的空间局部性从而减少IO操作。他广泛用于文件系统及数据库中,如:

Windows:HPFS 文件系统

Mac:HFS,HFS+ 文件系统

Linux:ResiserFS,XFS,Ext3FS,JFS 文件系统

数据库:ORACLE,MYSQL,SQLSERVER 等中

B+树特点

(1)根结点只有1个,分支数量范围[2,m]。

(2)除根以外的非叶子结点,每个结点包含分支数范围[[m/2],m],其中[m/2]表示取大于m/2的最小整数。

(3)所有非叶子节点的关键字数目等于它的分支数量。

(4)所有叶子节点都在同一层,且关键字数目范围是[[m/2],m],其中[m/2]表示取大于m/2的最小整数。

(5)所有非叶子节点的关键字可以看成是索引部分,这些索引等于其子树(根结点)中的最大(或最小)关键字。例如一个非叶子节点包含以下信息: (n,AO,KO,A1,K1..."n,An),其中Ki为关键字,Ai为指向子树根结点的指针,n表示关键字个数。即Ai所指字数中的关键字均小于或等于Ki,而Ai+1所指的关键字均大于Ki (i=1,2,......, n) 。

(6)叶子节点包含全部关键字的信息(非叶子节点只包含索引),且叶子结点中的所有关键字依照大小顺序链接(所以一个B+树通常有两个头指针,一个是指向根节点的root,另一个是指向最小关键字的sqt)。

不知道这些东西能不能理解啊,理解不了的话可能你大学需要回炉重造了,哈哈哈哈

接下来,开始正事吧,我以一个B+树进行串联讲解,先创建一棵树


主要是B+树的应用

插入数据

第一种情况:向B+树中插入数据9

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


首先查找9应插入的叶节点(最左下角的那一个)插入发现没有破坏B+树的性质,完毕

第二种情况:向B+树中插入20

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


1、首先查找20应插入的叶节点(第二个叶子节点),插入,但是这个时候改变了结构

2、发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21],[3744]两个,并把21往父节点移

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


3、发现父节点也破坏了B+树的性质,则把之再分解成[15 21].[4459]两个,并把21往其父节点移

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


第三种情况:向B+树中插入100

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


1、首先查找100应插入的叶节点(最后一个节点),插入,同样是影响了结构

2、修改其所有父辈节点的键值为10O(只有插入比当前树的最大数大的数时要做此步)

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


3、重复上述的方法开始拆分节点,直到完成

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


代码演示

PtrBpNode BpAllocateNode(BoolType IsLeaf){
int i;
PtrBpNode NewNode = (PtrBpNode)malloc(sizeof(BpNode));

NewNode->Num = 0;
if(True == IsLeaf){
NewNode->IsLeaf = True;
}
else{
NewNode->IsLeaf = False;
}
NewNode->Key = (PtrElementType)malloc(sizeof(ElementType) * (MinDegree * 2 - 1));
NewNode->Child =(PtrBpNode*)malloc(sizeof(PtrBpNode) * MinDegree * 2);
for(i = 0; i < MinDegree * 2; i++){
NewNode->Child[i] = NULL;
}
NewNode->Next = NULL;

return NewNode;
}

void BpInsert(PtrBp T, ElementType Val){
PtrBpNode NewNode;

if(MinDegree * 2 - 1 == T->Root->Num){
NewNode = BpAllocateNode(False);
NewNode->Child[0] = T->Root;
T->Root = NewNode;
BpSpilitNode(NewNode, 0);
}

BpInsertNonFull(T->Root, Val);
}

void BpInsertNonFull(PtrBpNode CurrentNode, ElementType Val){
int Index = GetIndex(CurrentNode->Key, CurrentNode->Num, Val);

if(True == CurrentNode->IsLeaf){
ShiftKey(CurrentNode->Key, True, Index, CurrentNode->Num - 1);
CurrentNode->Key[Index] = Val;
(CurrentNode->Num)++;
}
else{
if(MinDegree * 2 - 1 == CurrentNode->Child[Index]->Num){
BpSpilitNode(CurrentNode, Index);
//Caution
if(CurrentNode->Key[Index] < Val){
Index++;
}
}

BpInsertNonFull(CurrentNode->Child[Index], Val);
}
}

void BpSpilitNode(PtrBpNode SpilitNodeP, int ChildIndex){
int i;
PtrBpNode NewNode, SubNode = SpilitNodeP->Child[ChildIndex];

if(True == SubNode->IsLeaf){
NewNode = BpAllocateNode(True);
for(i = 0; i < MinDegree - 1; i++){
NewNode->Key[i] = SubNode->Key[i + MinDegree];
}
NewNode->Num = MinDegree - 1;
SubNode->Num = MinDegree;
NewNode->Next = SubNode->Next;
SubNode->Next = NewNode;
}
else{
NewNode = BpAllocateNode(False);
for(i = 0; i < MinDegree - 1; i++){
NewNode->Key[i] = SubNode->Key[i + MinDegree];
}
for(i = 0; i < MinDegree; i++){
NewNode->Child[i] = SubNode->Child[i + MinDegree];
}
NewNode->Num = SubNode->Num = MinDegree - 1;
}

ShiftKey(SpilitNodeP->Key, True, ChildIndex, SpilitNodeP->Num - 1);
ShiftChild(SpilitNodeP->Child, True, ChildIndex + 1, SpilitNodeP->Num);
SpilitNodeP->Key[ChildIndex] = SubNode->Key[MinDegree - 1];
SpilitNodeP->Child[ChildIndex + 1] = NewNode;
(SpilitNodeP->Num)++;
}

删除

第一种情况:向B+树中删除91

首先找到91所在叶节点(最后一个节点),删除之,和插入一样,他并没有改变数据结构,所以可以直接进行插入和删除

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


第二种情况:向B+树中删除97

首先找到97所在叶节点(最后一个节点),删除之,但是相比删除91多了一步操作,需要修改该节点的父辈的键字为91(ps:只有删除树中最大数时要做此步)

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


第三种情况:向B+树中删除51

首先找到51所在节点(第三个节点),删除之

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44,并修改相应键值,判断没有破坏B+树,完毕

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


第四种情况:向B+树中删除59

首先找到59所在叶节点(第三个节点),删除之

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


破坏B+树性质,尝试借节点,无效(因为左兄弟节点被借也会破坏B+树性质)合并第二第三叶节点并调整键值

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


第五种情况:向B+树中删除63

首先找到63所在叶节点(第四个节点),删除之

字节面试数据结构与算法:B+树的删除和插入,不够详细你打我


合并第四五叶节点并调整键值


但是在删除后可以发现一个问题,在第二层的第二个节点不满足B+树性质,所以需要从第二层的第一个节点借59,并调整键值


代码演示

void BpDelete(PtrBp T, PtrBpNode CurrentNode, ElementType Val){
int Index = GetIndex(CurrentNode->Key, CurrentNode->Num, Val);
PtrBpNode Precursor, SubNode, Successor;

if(Index < CurrentNode->Num && Val == CurrentNode->Key[Index]){

if(True == CurrentNode->IsLeaf){
ShiftKey(CurrentNode->Key, False, Index + 1, CurrentNode->Num - 1);
(CurrentNode->Num)--;
return;
}
else{
Precursor = CurrentNode->Child[Index];
Successor = CurrentNode->Child[Index + 1];

if(Precursor->Num >= MinDegree){
if(True == SubNode->IsLeaf){
CurrentNode->Key[Index] = Precursor->Key[SubNode->Num - 2];
}
else{
CurrentNode->Key[Index] = Precursor->Key[SubNode->Num - 1];
}

BpDelete(T, Precursor, Precursor->Key[SubNode->Num - 1]);
}
else if(Successor->Num >= MinDegree){
CurrentNode->Key[Index] = Successor->Key[0];
if(True == SubNode->IsLeaf){
SubNode->Key[SubNode->Num - 1] = CurrentNode->Key[Index];
}

BpDelete(T, Successor, Successor->Key[0]);
}
else{
BpMerge(T, CurrentNode, Index, Index + 1);

BpDelete(T, Precursor, Val);
}
}

}
else{

if(True == CurrentNode->IsLeaf){
return;
}
else{
if(Index > 0){
Precursor = CurrentNode->Child[Index - 1];
}
SubNode = CurrentNode->Child[Index];
if(Index < CurrentNode->Num){
Successor = CurrentNode->Child[Index + 1];
}


if(SubNode->Num >= MinDegree){
BpDelete(T, SubNode, Val);
}
else{
if(Index > 0 && Precursor->Num >= MinDegree){
ShiftKey(SubNode->Key, True, 0, SubNode->Num - 1);
SubNode->Key[0] = CurrentNode->Key[Index - 1];

if(True == SubNode->IsLeaf){
CurrentNode->Key[Index - 1] = Precursor->Key[Precursor->Num - 2];
}
else{
CurrentNode->Key[Index - 1] = Precursor->Key[Precursor->Num - 1];
ShiftChild(SubNode->Child, True, 0, SubNode->Num);
SubNode->Child[0] = Precursor->Child[Precursor->Num];
}
(SubNode->Num)++;
(Precursor->Num)--;

BpDelete(T, SubNode, Val);
}
else if(Index < CurrentNode->Num && Successor->Num >= MinDegree){
if(True == SubNode->IsLeaf){
SubNode->Key[SubNode->Num] = Successor->Key[0];
}
else{
SubNode->Key[SubNode->Num] = CurrentNode->Key[Index];
}
CurrentNode->Key[Index] = Successor->Key[0];
SubNode->Child[SubNode->Num + 1] = Successor->Child[0];
(SubNode->Num)++;

ShiftKey(Successor->Key, False, 1, Successor->Num - 1);
ShiftChild(Successor->Child, False, 1, Successor->Num);
(Successor->Num)--;

BpDelete(T, SubNode, Val);
}
else{
if(Index > 0){
BpMerge(T, CurrentNode, Index - 1, Index);
BpDelete(T, Precursor, Val);
}
else{
BpMerge(T, CurrentNode, Index, Index + 1);
BpDelete(T, SubNode, Val);
}
}
}
}

}
}

void BpMerge(PtrBp T, PtrBpNode CurrentNode, int LeftIndex, int RightIndex){
int i;
PtrBpNode LeftNode = CurrentNode->Child[LeftIndex];
PtrBpNode RightNode = CurrentNode->Child[RightIndex];

if(True == LeftNode->IsLeaf){
for(i = 0; i < MinDegree - 1; i++){
LeftNode->Key[i + MinDegree - 1] = RightNode->Key[i];
}
LeftNode->Num = MinDegree * 2 - 2;
LeftNode->Next = RightNode->Next;
}
else{
for(i = 0; i < MinDegree - 1; i++){
LeftNode->Key[i + MinDegree] = RightNode->Key[i];
}
for(i = 0; i < MinDegree; i++){
LeftNode->Key[i + MinDegree] = RightNode->Key[i];
}
LeftNode->Key[MinDegree - 1] = CurrentNode->Key[LeftIndex];
LeftNode->Num = MinDegree * 2 - 1;
}

ShiftKey(CurrentNode->Key, False, LeftIndex + 1, CurrentNode->Num - 1);
ShiftChild(CurrentNode->Child, False, RightIndex + 1, CurrentNode->Num);
(CurrentNode->Num)--;

if(CurrentNode == T->Root && 0 == CurrentNode->Num){
T->Root = LeftNode;
}
}