字节面试数据结构与算法：B+树的删除和插入，不够详细你打我
之前在讲解mysql底层算法架构的时候，我提到了一个点：树，这个大学的时候让我们只有恨没有爱的课程中的一员，但是，最近的一段时间里，算法和数据结构成为面试过程汇总弄个地考虑重点，之前的时候图解过红黑树，也以mysql为例，将B+树的相关原理进行了讲解，想要重新回顾一下的朋友，可以去公众号：Java架构师联盟查看 今天我们来看一下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 首先查找9应插入的叶节点(最左下角的那一个)插入发现没有破坏B+树的性质,完毕 第二种情况：向B+树中插入20 1、首先查找20应插入的叶节点(第二个叶子节点）,插入，但是这个时候改变了结构 2、发现第二个叶子节点已经破坏了B+树的性质,则把之分解成[20 21],[3744]两个,并把21往父节点移 3、发现父节点也破坏了B+树的性质,则把之再分解成[15 21].[4459]两个,并把21往其父节点移 第三种情况：向B+树中插入100 1、首先查找100应插入的叶节点(最后一个节点),插入，同样是影响了结构 2、修改其所有父辈节点的键值为10O(只有插入比当前树的最大数大的数时要做此步) 3、重复上述的方法开始拆分节点，直到完成 代码演示 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+树中删除97 首先找到97所在叶节点(最后一个节点),删除之，但是相比删除91多了一步操作，需要修改该节点的父辈的键字为91（ps：只有删除树中最大数时要做此步） 第三种情况：向B+树中删除51 首先找到51所在节点(第三个节点),删除之 破坏了B+树的性质,从该节点的兄弟节点(左边或右边)借节点44，并修改相应键值,判断没有破坏B+树,完毕 第四种情况：向B+树中删除59 首先找到59所在叶节点(第三个节点),删除之 破坏B+树性质,尝试借节点,无效（因为左兄弟节点被借也会破坏B+树性质）合并第二第三叶节点并调整键值 第五种情况：向B+树中删除63 首先找到63所在叶节点(第四个节点),删除之 合并第四五叶节点并调整键值 但是在删除后可以发现一个问题，在第二层的第二个节点不满足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; } }
