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

2020-11-23 558

之前在讲解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;
    }
}

微信关注我们

原文链接：https://my.oschina.net/u/4472036/blog/4739957

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

如何将Sass编译成CSS

本节我们来学习 Sass 的编译，我们写好的 Sass 代码，浏览器是不能识别的，Sass 只不过是作为一个预处理工具，只有将 Sass 代码编译成 CSS 代码后，才能够使用。那么 Sass 要如何编译成 CSS 代码呢，这就是我们本节需要讲到的内容。 Sass 的编译方法有很多，例如：命令行编译模式：比较简单，可以直接在终端中输入 Sass 指令来编译，本节我们主要讲命令行编译模式的使用。 GUI工具编译：有的比较多的看一工具有 Koala、CodeKit、Scout、Compass.app 等，这些工具都需要安装。自动化编译：可以使用 Grunt 或者 Gulp 来配置 Sass 自动化编译。命令编译命令编译就是在终端中输入 sass 命令来编译 Sass 代码，这种编译方式使用起来很简单。示例：假设现在有一个Sass文件，文件名为 style.scss （Sass 文件的扩展名名 .scss），我们需要将这个文件中的代码编译成 CSS 代码，可以执行如下命令： sass style.scss style.css 命令执行成功后，会自动创建一个 style.css 文...

2020-11-23

492

本文的阅读有一定的门槛，请先了解 GC 的基本只知识。现代垃圾收集器的演进大部分都是往减少停顿方向发展。像 CMS 就是分离出一些阶段使得应用线程可以和垃圾回收线程并发，当然还有利用回收线程的并行来减少停顿的时间。基本上 STW 阶段都是利用多线程并行来减少停顿时间，而并发阶段不会有太多的回收线程工作，这是为了不和应用线程争抢 CPU，反正都并发了慢就慢点（不过还是得考虑内存分配速率）。而 G1 可以认为是打开了另一个方向的大门：只回收部分垃圾来减少停顿时间。不过为了达到只回收部分 reigon，每个 region 都需要 RememberSet 来记录各 region 之间的引用。这个内存的开销其实还是挺大的，可能会占据整堆的20%或以上。并且 G1 还有写屏障的开销，虽说用了 logging wtire barrier，但也还是有开销的。当然 CMS 也用了写屏障，不过逻辑比较简单，啥都没判断就单纯的记录。其实 G1 相对于 CMS 只有在大堆的场景下才有优势，CMS 比较伤的是 remark 阶段，如果堆太大需要扫描的东西太多。而 G1 在大堆的时候可以选择部分...

2020-11-23

498

资源下载

更多资源

Mario

马里奥是站在游戏界顶峰的超人气多面角色。马里奥靠吃蘑菇成长，特征是大鼻子、头戴帽子、身穿背带裤，还留着胡子。与他的双胞胎兄弟路易基一起，长年担任任天堂的招牌角色。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Spring

Spring框架（Spring Framework）是由Rod Johnson于2002年提出的开源Java企业级应用框架，旨在通过使用JavaBean替代传统EJB实现方式降低企业级编程开发的复杂性。该框架基于简单性、可测试性和松耦合性设计理念，提供核心容器、应用上下文、数据访问集成等模块，支持整合Hibernate、Struts等第三方框架，其适用范围不仅限于服务器端开发，绝大多数Java应用均可从中受益。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。