字符画之画b-tree

  1. b-tree节点结构
  2. b-tree结构
  3. b-tree节点插入
  4. b-tree节点删除

用字符“画”b-tree(b-树,直接读作“b树”)的基本结构。

b-tree是为了磁盘(减少磁盘IO次数)或其它存储设备而设计的一种多叉平衡查找树。

b-tree节点结构

struct BTNode
{
    struct BTNode*      parent;
    Vector<T>           key;        /**< 关键码,即节点数据 */
    Vector<BTNode*>     child;      /**< 分支,即子节点 */
}

  key为关键码节点,也即数据节点,child为子节点;

  key和child排列如下:
  key       [0]  [1]  [2]  [3]      =>   *[k0]*[k1]*[k2]*[k3]*
  child  [0]  [1]  [2]  [3]  [4]         紧凑表示:'*'代表key两则的子节点child

  b-tree阶次为m(这里为5), 则分支数(子节点) <= m,关键码 <= m-1;
  且 分支数(子节点) = 关键码数+1  恒成立。
   【分支数(子节点)-1 = 关键码数】

  约定关键码数为n,则分支数为n+1,
  内部节点的分支数n+1不能太少,即有
  树根:    2 <= n+1 <= m
  其余:⌈m/2⌉ <= n+1 <= m ,⌈⌉为取上整
  故 b-tree 也称做 (⌈m/2⌉,m)-tree 。

b-tree结构

  对于叶节点(以5阶b-tree为例):
  key       [0]  [1]  [2]  [3]     -> 最低层叶节点
  child  [0]  [1]  [2]  [3]  [4]   -> 叶节点的子节点为external nodes,
                                      即只是在vector(child)有一个BTNode指针,值为nullptr;
                                      也只有external nodes指向nullptr。

            r                      ---
           / \                      |
          /   \     internal nodes  |
         /     \                    |
        /_______\   (__为叶节点)   ---
       |||||||||||  external nodes  |

b-tree节点插入

以4阶b-tree为例,则有 2 <= 分支数 <= 4, 1 <= 关键码数 <= 3;

  • 插入节点示意图
                r      r+1(新插入关键码)
                 \     /
  key       [k]  [k]  [k] ...
  child  [c]  [c]  [c]  [c] ...
                   /     \
                 r+1     r+2(新插入子节点,作为external node)
  当节点关键码数>3时,则该节点发生上溢。
  • 使用分裂修复上溢
  取中位数分裂,s = ⌊m/2⌋ (即向下取整,m为b-tree的阶),如下图所示:
  即m为奇数时,s为key正中间位置,m为偶数时,s为key均分后左侧的最后一个位置。
  *[k0]*[k1]*[k2]* ... *[k(m-1)]*
                    |
                    V
  *[k0]*[k1]*k(s-1)] * [ks] * [k(s+1)]* ... *[k(m-1)]*
  ------------------   ----   -----------------------
  作为ks左子节点   上移至父节点         作为ks右子节点

  以4阶b-tree为例,演示分裂操作:
  将[3]上移至父节点
      *[0]*[10]*             *[0]*[3]*[10]*
          \                     /     \
           \         =>        /       \
            \                 /         \
   *[1]*[2]*[3]*[5]*     *[1]*[2]*    *[5]*
   -----------------     ---------    -----
      原node节点       分裂后的node   新节点rc
  [3]的新左右两侧节点的分支数分别为3和2(3+2=5>4),均会满足>=⌈m/2⌉=2

  [3]之后的关键码和分支节点(即*和[])将转移到rc中;
  根节点上溢时,分裂出的新根节点,且新的根节点只有2个分支;
  根据分裂特性,可知非叶节点的子节点不可指向nullptr。

b-tree节点删除

以4阶b-tree为例,则有 2 <= 分支数 <= 4, 1 <= 关键码数 <= 3;
当节点关键码数>3时,则该节点发生下溢;

  • 修复下溢
  (1)通过旋转(向左侧子节点借)修复下溢(#也是子节点,方便对比观看):
       *[0]*[5]*[10]*            *[0]*[3]*[10]*
          /    \                    /     \
         /      \      =>          /       \
        /        \                /         \
  *[1]*[2]*[3]#   *         *[1]*[2]*     #[5]*
                 ---
               下溢节点
  旋转前后,节点#均在[3]和[5]之间

  (2)通过合并修复下溢(#也是子节点,方便对比观看):
       *[0]*[5]#[10]*         *[0]*[10]*
          /    \                  |
         /      \      =>         |
        /        \                |
     *[1]*        *            *[1]*[5]*
                 ---
               下溢节点
  合并后,将删除节点#

转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 [ yehuohan@gmail.com ]

文章标题:字符画之画b-tree

本文作者:Yehuohanxing

发布时间:2018-02-02, 15:10:33

最后更新:2018-04-03, 23:26:42

原始链接:http://yehuohan.github.io/2018/02/02/笔记/字符画之画b-tree/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录