首页 > 编程知识 正文

什么是b树的阶,b树和b树的区别

时间:2023-05-04 08:58:03 阅读:202065 作者:4107

一、什么是B-树?

           Mysql数据库用过了吧?

              里面的【索引】是基于什么【数据结构】?

                 索引主要是基于【Hash表】或者【B+树】

          要弄明白B+树,先要了解什么是B-树。
          B-树就是【B树】,中间的横线并不是减号。

 

二、为什么数据库【索引】要使用【树】结构存储呢?

        1) 树的查询效率高,而且可以保持有序

        2)为什么索引没有使用二叉查找树来实现呢?

               ①. 从算法逻辑上来讲,二叉查找树的查找速度和比较次数都是最小的。

                     但是,一个现实的问题:磁盘IO

               ②. 数据库索引是存储在【磁盘】上的,当数据量比较大的时候,索引的大小可能有几个G甚至更多。

               ③. 当我们利用【索引查询】时候,不能把整个索引全部加载的【内存】中

                     能做的只有逐一加载每一个【磁盘页】,这里的磁盘页对应着索引树的节点。

                     

                   如果利用二叉查找树作为索引结构,情形是什么样呢?
                       假设树的高度是4,查找的值是10

                       二叉查找树的结构:

                       

                     ①.  第1次磁盘IO:

                          

                     ②. 第2次磁盘IO:

                         

                      ③. 第3次磁盘IO:

                        

                      ④. 第4次磁盘IO:

                        

            磁盘IO的次数是4次,索引树的高度也是4
            所以最坏的情况下,磁盘IO次数等于索引树的高度

         为了减少磁盘IO的次数,需要把原本"瘦高"的树结构变得"矮胖", 这就是B-树的特征之一

         B树是一种【多路平衡查找树】,它的每一个节点最多包含K个孩子,K被称为B树的【阶】。

         K的大小取决于【磁盘页】的大小。

 

三、B-树(Balance Tree)的特征

           B-树(Balance Tree),一个m阶的B树具有如下几个特征:

              1. 根节点至少有两个子女

              2. 每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m

              3. 每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m

              4. 所有的叶子节点都位于同一层

              5. 每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

 

以一个3阶B-树为例,看看B-树的具体结构。树中的具体元素和刚才的二叉查找树是一样的

B-树的查询过程,假设要查询的数值是5

    ①. 第1次磁盘IO:

          

         在内存中定位(和9比较):

         

      ②. 第2次磁盘IO:

        

        在内存中定位(和2,6比较):

         

    ③. 第3次磁盘IO:

        

    在内存中定位(和3,5比较):

        

   通过整个流程可以看出,B-树在查询中的比较次数其实不比二叉查找树少,尤其当单一节点中的元素数量很多时。

   可是相比磁盘IO的速度,内存中的比较耗时几乎可以忽略。

   所以只要树的高度足够低,IO次数足够少,就可以提升查找性能。

相比之下节点内部元素多一些也没有关系,仅仅是多了几次内存交互,只要不超过磁盘页的大小即可。这就是B-树的优势之一。

这就是B-树的查询过程。

 

三、B-树插入新节点的过程

          B-树插入新节点的过程比较复杂,而且分成很多种情况。

          举个例子,假如我们要插入的值是4

            ①.  自顶向下查找4的节点位置,发现4应当插入到节点元素3,5之间。

                   

         ②. 节点3,5已经是两元素节点,无法再增加。父亲节点 2, 6 也是两元素节点,也无法再增加。

               根节点9是单元素节点,可以升级为两元素节点。于是拆分节点3,5与节点2,6,让根节点9升级为两元素节点4,9。节点6独立为根节点的第二个                孩子。

             

             就为了插入一个元素,让整个B-树的那么多节点都发生了连锁改变。

             正因为如此,让B-树能够始终维持【多路平衡】。这也是B-树的一大优势:【自平衡】

  四、B-树删除节点的过程

        举个例子:删除元素11

           ①. 自顶向下查找元素11的节点位置。

               

          ②. 删除11后,节点12只有一个孩子,不符合B树规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。                  (这个过程称为左旋

             

             

            

五、B-树都有哪些实际应用呢?

          1) B-树主要应用于【文件系统】以及部分【数据库索引】,比如非关系型数据库MongoDB。

          2) 而大部分关系型数据库,比如Mysql,则使用B+树作为【索引】。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。