抛砖引玉篇--B树、B+树

/ --*-- 2018.7.19 –-*-- /

% 磁盘io操作的基本单位是块（block）或者页。

% 对于数据库或文件系统等应用场景，

     数据不可能全部存储在内存，

     需要从磁盘中读取数据的过程，

     而相比内存，磁盘的io操作很耗时，

     此时，

     使用磁盘io次数评价索引结构的优劣。

 

% 当存储大量数据时，如果一个节点只存储一个数据，

    节点数过多，

    将导致：

    要么树的度（节点拥有最多子树的最大值）非常大，

    要么树的高度过大。

    节点越多，io操作次数越多。

 

% 对于B树来说，每个节点的大小可以达到磁盘block的大小。

 

所以引入了多路查找树（一个节点的子树可以多于两个）。

而B树是一种平衡的多路查找树。

 

 

% B树可以减少访问节点和数据块的次数。(通常根节点放在内存中)

所以B树的数据结构很适合内外存数据交换。

 

% m叉树（包括二叉树）的目的：用于信息的检索和更新。

 

% m阶B树具有以下特点：

 @1. 根节点有k个子节点( k的范围为：[2, m] )。

 @2. 任意非根节点非叶子节点有k个子节点（ k的范围为：[m/2, m]）。

 @3. 任意节点的键值数为k-1（ [m/2, m]）。

 @4. 所有叶子节点在同一层。

 

 

 

% B-Tree的插入：

 

// 主要考虑两种情况：

// 插入节点未满时：直接插入

// 插入节点已满时：

// 情况一：父节点不是根节点：创建新节点，将原来节点均分为两个节点，

并将中间键值插入父节点。

// 情况二：父节点是根节点  ：创建新节点，将根节点均分，并用中间值创建新的根节点，作为均分的两个节点的父节点。                

% B-Tree的删除：

//主要考虑两种情况：

//当删除的键值在叶子节点时：直接删除。

//当删除键值不是在叶子节点时：

//      用最接近待删除键值的前继（或后继）叶子节点的键值交换待删除值，然后转换为从叶子节点删除键值。

//删除后调整树，

//当删除后的叶子节点键值少于m/2-1时，分以下情况调整：

//情况一：同级叶子节点有足够多的键值时（大于m/2-1），

两者重新排列键值（包括其父节点对应的键值），均分。

//情况二：同级叶子节点键值数不够时（等于m/2 -1），

          @1.当父节点不是根节点时：

             将与同级叶子节点的所有键值、父节点对应的键值三者合并，

             重新排列，此时，父节点少了一个键值，

所以，对父节点重复情况二操作，直到遇到根节点。

          @2.当父节点是根节点时：

             将与同级节点、父节点三者一起合并，作为新的根节点。

void BTreeDelete(k)

{

  BTreeNode*  node = BTreeSearch(k);

  if(node != 0)

{

  if（node == 叶子节点）

      :从node中删除k。

  else

    {

       :找到大小最接近k的后继（或前继）叶子节点。

       :在叶子节点中找到最接近k的键值s。

       :将s复制到k所在的node。

       :node = 叶子节点。

       :从node中删除s。

    }

       while（true）

       {

          if（node没有下溢：键值数小于m/2）

            return。

          else

          {

             if（node的同级节点有足够多键值：大于m/2）

               {

                   :在node和其同级节点间重新分配键值。

                 return。

               }

             else if（node的父节点 == 根节点）

             {

                  if( node的根节点只有一个键值)

                 {

                    :合并node、node的同级节点、根节点为一个新的节点。

                    return。

                 }

                 else

                 {

                        :合并node及其同级节点。

                       return。

                  }

              }                

             else

              {

                :合并node及其同级节点。

                :node = node的父节点。

              }

   

}

}

   

}

}

 

 

% 对于B树来说，唯一增加树高度的情况就是：

   在根节点已满的情况下再插入一个节点。

 

% B树存在的问题：

  @1.对于B树来说：数值大小相近的两个键值却分布在不同的节点上，

                                这将导致顺序遍历数据时，

                               需要在各节点之间来回穿梭，

                              会有大量的io操作。

 

% 根据B树的定义，其空间占满率至少为50%，实际应用为70%左右，

    所以进一步加以限制，提高B树的空间利用率。

 

 

% B*树：是对B树的一种改进。

        对于B*树来说，当插入的节点已满时，并不是立刻进行分解，

        而是与其相邻的节点平均分配键值和指针，

        直到相邻两个节点都满时，才进行分解，

        将两个节点分解成三个。

 

% B*树通过延迟分解，提高空间利用率。

除此之外，还是未能解决B树的大缺点。

 

 

 

% B+树：解决B树、B*树遍历数据效率低的问题。

  ：当需要对数据进行遍历时，在连续区间或由链表模拟的连续区间上进行

     往往是最有效的；

  ：当需要对大量数据进行搜索时，树结构往往是效率最佳的。

 

% B+树结合了链表和树两种数据结构的优点：

  ：在B树中，对数据的引用指向了树中的任意节点，

    但在B+树中，这种引用只指向叶子节点。

   

  

  ：也就是说，

    在B+树中，节点的Node结构跟B树类似，

    但是只有叶子节点的键值与数据文件相关联。

    其他节点只是起到索引作用。

   

 

 

% B+树由两部分组成：索引集和序列集。

  ：索引集部分由树结构负责，实现快速索引。

  ：序列集由链表结构负责，

    所有的叶子节点用链表结构顺序连接在一起，

    实现高效遍历访问。

 

% B+树的操作跟B树类似，但是插入删除都是在叶子节点。

 

% 对于B+树来说，由于非叶子节点只是索引作用，真正存有与文件数据相关引用的是叶子节点，

所以对B+树进行查找时，不管是否能找到目标，都会查找到最后的叶子节点才算结束。