关于 B+ tree 结点瓦解的模型算法

关于 B+ tree 结点分裂的模型算法

--------------------------------------------
标题: 关于 B+ tree 结点分裂的模型算法
作者: 叶飞虎
建立: 2011.04.13
--------------------------------------------

1. 假设
   a. 结点键项类型
      typedef struct
      {
         <Type>      Key;              // 指定类型<Type>的键值
         void*       Link;             // 子链接或叶值链接
      } TItem, *PItem;

   b. 结点类型
      typedef struct
      {
         short       Count;            // 项数, Count <= dimension
         bool        IsLeaf;           // 是否为叶结点
         TItem       Items[dimension]; // 键项列表, dimension 为结点维度
      } TNode, *PNode;

   c. 已知
      TNode*         parent;           // 父结点:
      TNode*         current;          // 当前结点
      TNode*         prior;            // 前一兄弟
      TNode*         next;             // 下一兄弟
      <Type>         key;              // 键值
      void*          link;             // 子链接或叶值链接
      其中:
         1). index  为 current 在 parent 中的索引
         2). ins_no 为插入 current 中的位置
         3). current = parent->Items[index].Link;
         4). prior   = parent->Items[index - 1].Link;
         5). next    = parent->Items[index + 1].Link;
         6). (index >= 0) && (index < dimension)
         7). (ins_no >= 0) && (ins_no <= dimension)
         8). (current->Count == dimension)

2. 按条件分裂
   a. 结点分裂操作
      enum TPartOp  {poNew,            // 新建结点, 当前键值插入新结点
                     poPrior,          // 结点向前分裂, 当前键值与前一个结点合并
                     poNext};          // 结点向后分裂, 当前键值与下一个结点合并

   b. 计算条件 [...|...]  [...|ins_no|...]  [...|...]
   {
      // 初始化
      result = poNew;

      // 判断前一结点是否有空闲位置
      if ((prior != NULL) && (prior->Count < dimension))
      {
         // 判断后一结点是否能容纳前一结点的后半部键值
         if ((next != NULL) && (next->Count < dimension)
                            && (ins_no >= next->Count + (dimension - ins_no)))
            result = poNext;
         else
            result = poPrior;
      }
      else if ((next != NULL) && (next->Count < dimension))
         result = poNext;
   }

--------------------------------------------