腾讯、阿里面试题了解B+树吗？

待我称王封你为后i 2023-07-23 15:57 22阅读 0赞

# 腾讯、阿里面试题: 了解B+树吗？ #

由于`MySQL`的索引结构是B+树，所以B+树是大厂的高频面试题,想理解B+树，最好先理解B树，下面详细介绍B树、B+树

## B树 ##

*  ### B树的概念 ###
    
    B树又称为B-树，是一种平衡多路查找树，描述B树，一般需要指定其阶数 M M M,阶数指的是一个节点包含的子节点最大数量。当 M M M取2的时候，就是常见的二叉树
    
    其有如下性质：
    
     *  每个节点最多有 M − 1 M-1 M−1个关键字
     *  除根节点外，其余的节点至少有 c e i l ( M / 2 ) − 1 ceil(M/2)-1 ceil(M/2)−1个关键字（ c e i l ceil ceil向上取整函数)
     *  每个结点中的关键字都按照从小到大的顺序排列，每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于它
     *  所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同。
 *  ### B树的插入操作 ###
    
    如下描述是B树的插入算法，相对来说比较简单
    
    1.  找到关键字的插入位置，一定是叶节点位置，进行插入操作
    2.  插入后，如果当前节点的关键字数量小于等于 M − 1 M-1 M−1，则结束，否则执行步骤3
    3.  进行**分裂操作**，当前节点按中间关键字分裂成三部分，中间关键字插入到父节点中，
    
    左边部分，成为中间关键字的左节点，右边部分成为中间关键字的右节点，然后
    
    当前节点指向父节点，转到2，执行递归操作。
    
    下面是一个5阶B树的分裂过程，上面图是分裂前，下面图是分裂后
    
    ![format_png][]
    
    ![format_png 1][]
 *  ### B树的构建过程 ###
    
    下面以构建一个5阶树，介绍B树的构建过程。
    
     *  依次插入关键字3，5， 2， 6
        
        ![format_png 2][]
     *  插入4的时候，由于当前节点关键字数量等于M(5),需要进行分裂操作
        
        ![format_png 3][]
     *  依次插入关键字1，8，7，9插入`9`的时候又进行了分裂
        
        ![format_png 4][]
     *  依次插入关键字10，11，12插入`12`的时候又进行了分裂过程
        
        ![format_png 5][]
     *  插入关键字13,14,15,16,17,中间插入15的时候进行了分裂操作
        
        ![format_png 6][]
     *  最后插入18，进行了**两次分裂操作**
        
        ![format_png 7][]
        
        其实插入的过程会发现，顺序插入空间效率最差，比如\[11,12\]节点,就插入不了任何元素.
 *  #### B树的删除过程 ####
    
    B树的删除算法较为复杂，下面首先介绍算法，之后结合实例，阐述
    
    1.  查找关键字，如果不存在，结束，否则进入步骤2.
    2.  如果关键字处于叶节点，直接删除。如果关键字处于非叶子节点，则用其前继关键字(**前继关键字一定位于叶节点**)覆盖要删除的关键字，之后删除后继关键字，将当前节点指向包含后继关键字的节点。以上两种情况，均最后转入步骤3
    3.  如果当前节点关键字数量大于等于 c e i l ( M / 2 ) − 1 ceil(M/2)-1 ceil(M/2)−1,则结束，否则转入4
    4.  如果兄弟节点(不论左兄弟，还是右兄弟)，关键字数量大于 c e i l ( M / 2 ) − 1 ceil(M/2)-1 ceil(M/2)−1,则父节点中对应的关键字下移到当前节点，兄弟节点对应的关键字上移到父节点，结束。若无兄弟节点关键字数量大于 c e i l ( M / 2 ) − 1 ceil(M/2)-1 ceil(M/2)−1,则转入步骤5
    5.  **合并操作**，将父结点中关键字下移与当前结点及它的兄弟结点中的官架子合并，形成一个新的结点。**原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点**。当前节点指向父节点，重复2，进行递归操作。
    
    #### 下面是一个5阶数的删除过程实例 ####
    
    原B树如下图所示  
    ![format_png 7][]
    
     *  #### 删除关键字7 ####
        
        其前继关键字(**类似于平衡二叉树的前继节点,其实也可以为后继节点**)为6,覆盖删除后,当前节点只有一个关键字5,而其左兄弟节点有3个关键字节点大于2.所以3上移,4下移到当前节点.
    
    ![format_png 8][]
    
     *  #### 删除关键字18 ####
        
        删除关键字18,其实是一个复杂的过程,删除完之后,没有兄弟节点关键字数量大于2,所以进行合并操作左兄弟节点\[14,15\],父节点中的16,和当前节点合并成一个新节点\[14,15,16,17\],合并后父节点由于只剩13,所有又要与其父节点关键字,左兄弟节点合并,构造一个新的节点,最后结果如下
        
        ![format_png 9][]
 *  #### B树的优缺点 ####
    
    B树主要的优点是相对于二叉树,每个节点包括更多的关键字,所以其树高相对较低,查找效率很高.

## Ｂ+树 ##

*  ### B+树的概念 ###
    
     *  B+树包含两种节点，一种是非叶子节点(索引节点)，一种是叶子节点。
     *  B+树与B树，最大的不同是**B+树的非叶子节点不保存数据**，只用于索引，所有数据都保存在叶子节点
     *  非叶子节点最多有 M − 1 M-1 M−1个关键字，阶数 M M M同时限制了叶子结点最多存储 M − 1 M-1 M−1个记录。
     *  索引节点中的key都按照从小到大的顺序排列，对于内部结点中的一个key，左树中的所有key都**小于**它，右子树中的key都**大于等于**它。叶子结点中的记录也按照key的大小排列。
     *  **每个叶子节点都存有相邻叶子节点的指针，叶子节点本身依关键字的大小自小而大顺序链接**（范围查找特性）
 *  ### B+树插入 ###
    
     *  #### B+树插入算法 ####
        
        1.  通过查找，确定关键字的插入位置，插入位置一定位于叶节点，插入后，如果当前
            
            节点关键字数量小于等于 M − 1 M-1 M−1,算法结束，否则转入步骤2.
        2.  **分裂过程**，将当前节点，分为左右两个叶子节点，左叶子节点包含前 M / 2 M/2 M/2个记录，
            
            右叶子节点包含剩余记录，并且将第 M / 2 + 1 M/2+1 M/2\+1个记录的关键字上移到父节点。当前节点指针指向父节点，然后执行步骤3.(父节点一定是索引节点)
        3.  如果当前节点的关键字数量小于 M M M,则插入结束，否则，将当前索引节点以中间关键字为中心分裂成两个索引节点，左索引节点和右索引节点，并将中间关键字上移到父节点中。并且其左节点为上面提到的`左索引节点`,其右节点为`右索引节点`。将当前节点指针指向父节点，重复步骤3
     *  #### B+树插入实例 ####
        
        如下是一个5阶B+数的构造过程
        
         *  依次插入1、5、9、13
            
            ![format_png 10][]
         *  插入17的时候，发生分裂过程
            
            ![format_png 11][]
         *  依次插入2、3、4，插入4的时候，发生分裂过程
            
            ![format_png 12][]
         *  依次插入10，11，插入11的时候，发生分裂过程
            
            ![format_png 13][]
         *  插入12，14，插入14的时候，发生分裂过程
            
            ![format_png 14][]
         *  插入15，16，**插入16的时候，发生两次分裂过程，依次在叶节点，和索引节点**
            
            ![format_png 15][]
 *  ### B+树删除 ###
    
     *  #### B+树删除算法 ####
        
        1.  找到目标关键字所在的叶节点位置，进行删除，若删除后，当前节点关键字数量大于
            
            等于 c e i l ( M / 2 ) − 1 ceil(M/2)-1 ceil(M/2)−1，结束，否则转到步骤2
        2.  若兄弟节点有富余(大于 c e i l ( M / 2 ) − 1 ceil(M /2 )-1 ceil(M/2)−1)，向兄弟借一个记录，同时用借到的key替换父节点中对应的关键字，结束。否则转到步骤3
        3.  若兄弟节点没有富余,则当前节点和兄弟节点合并成一个新的节点，删除父节点的关键字，新节点指向父节点相应的位置。执行步骤4
        4.  若索引节点的关键字个数大于等于 c e i l ( M / 2 ) − 1 ceil(M/2)-1 ceil(M/2)−1，则结束，否则执行5
        5.  若兄弟结点有富余，父结点key下移，兄弟结点key上移，删除结束。否则执行第6步
        6.  当前结点和兄弟结点及父结点下移key合并成一个新的结点。将当前结点指向父结点，重复第4步
        
        **4，5，6步类似B树的删除过程**
     *  #### B+树删除算法实例 ####
        
        原来的一个5阶树
        
        ![format_png 15][]
        
         *  #### 删除10 ####
            
            左兄弟节点有富余，借一个记录5，并且替换父节点中的关键字
            
            ![format_png 16][]
         *  #### 删除11 ####
            
            删除11这个过程非常复杂，首先没有兄弟节点有富余，所以当前节点和兄弟节点合，并且删除掉父节点中对应的关键字，也就是13。之后由于父节点只有15一个关键字，需要一次索引节点的合并过程![format_png 17][]
            
            #### 每次删除的时候，记得更新索引结构，即将索引结构中的要删除的关键字，替换成其后继节点 ####
 *  ### B+树的优点 ###
    
    1、**B+树的层级更少**：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
    
    2、**B+树查询速度更稳定**：B+所有关键字数据地址都存在**叶子**节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
    
    3、**B+树天然具备排序功能**：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
    
    4、**B+树全节点遍历更快**：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。
    
    B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

### 参考文章 ###

[B树和B+树的插入、删除图文详解][B_B]  
[平衡二叉树、B树、B+树、B\*树 理解其中一种你就都明白了][B_B_B_]

[format_png]: /images/20230528/f2d3eebefde94113a47b8d0784fdb43e.png
[format_png 1]: /images/20230528/dccb44d246c8425aacefeffe5187a7a7.png
[format_png 2]: /images/20230528/8df3e6f38bfc4b0396dcda366d033832.png
[format_png 3]: /images/20230528/443a0ce3d14846bea0d5cff19026f264.png
[format_png 4]: /images/20230528/ac5b04e38893435192fb022682b73ea8.png
[format_png 5]: /images/20230528/1cc5a9d4f2ed4b07a93758e919629b1d.png
[format_png 6]: /images/20230528/3a28c61768624445aeda371b15feece9.png
[format_png 7]: /images/20230528/ba753260652d4e08b118282c6144ed2d.png
[format_png 8]: /images/20230528/e086f2399dcf4c9fb241591c283a3580.png
[format_png 9]: /images/20230528/e299fea51e8446d2805a3ab8cb1c0367.png
[format_png 10]: /images/20230528/57167e26bb064731899d38616e843409.png
[format_png 11]: /images/20230528/39ba5ef91c9842888f4463810967f05e.png
[format_png 12]: /images/20230528/db8fa35a52ab4650bbd6613ecf0fa447.png
[format_png 13]: /images/20230528/94cfb3082feb496cb7d9b8d55c1ff355.png
[format_png 14]: /images/20230528/dcd1f37d197d4ac9b71e928ae8a8d495.png
[format_png 15]: /images/20230528/e2a3d202732444f7bf6a50b64d828212.png
[format_png 16]: /images/20230528/aab2bc48d5a047eda82894955d5695ee.png
[format_png 17]: /images/20230528/0ad475a2ed3b4740b9150e20e7e3d41c.png
[B_B]: https://www.cnblogs.com/nullzx/p/8729425.html
[B_B_B_]: https://zhuanlan.zhihu.com/p/27700617