b+.cpp

b+ tree code implementation and insertion deletion

#   }   
#   while(nodetemp2.isactive && iofile.tellp() < posEnd);   
#   if (nodetemp2.isactive)   
#   {   
#    nodenewposition = iofile.tellp();   
#    iofile.write((char *)&nodenew, sizeof(BPlusNode));   
#   }   
#   else   
#   {   
#    iofile.seekp(cur, ios::beg);   
#    nodenewposition = cur;   
#    iofile.write((char *)&nodenew, sizeof(BPlusNode));   
#   }   
#   root = nodenewposition;   
#   iofile.seekp(0, ios::beg);   
#   iofile.write((char *)&root, sizeof(long));   
#   for (int i = 0; i <= 1; ++i)   
#   {   
#    iofile.seekp(nodenew.children[i], ios::beg);   
#    iofile.read((char *)&nodetemp1, sizeof(BPlusNode));   
#    nodetemp1.father = nodenewposition;   
#    iofile.seekp(nodenew.children[i], ios::beg);   
#    iofile.write((char *)&nodetemp1, sizeof(BPlusNode));   
#   }   
#   iofile.close();   
#   return true;   
#  }   
#  // 没有分裂到根结点   
#  else   
#  {   
#   int insertposition = 0;   
#   iofile.seekp(position, ios::beg);   
#   iofile.read((char *)&node, sizeof(BPlusNode));   
#   if (node.amount < M)         // 结点中还有空位保存新插入的键值，不需要分裂   
#   {   
#    // 按照从小到大的顺序重新排列原有键值和新插入的键值   
#    bool issort1 = false;   
#    for (int i = 1; i < node.amount; ++i)   
#    {   
#     if (node.key[i] > key)   
#     {   
#      for (int j = node.amount - i, k = 0; j > 0; --j, ++k)   
#      {   
#       node.key[node.amount-k] = node.key[node.amount-k-1];   
#      }   
#      node.key[i] = key;   
#      insertposition = i;   
#      issort1 = true;   
#      break;   
#     }   
#    }   
#    if (!issort1)   
#    {   
#     node.key[node.amount] = key;   
#     insertposition = node.amount;   
#    }   
#    node.amount++;   
#    if (!node.isleave)   
#    {   
#     for (int p = node.amount-1; p > insertposition; --p)   
#     {   
#      node.children[p] = node.children[p-1];   
#     }   
#     node.children[insertposition] = nodenewposition;   
#    }   
#    iofile.seekp(position, ios::beg);   
#    iofile.write((char *)&node, sizeof(BPlusNode));   
#    iofile.close();   
#    return true;   
#   }   
#   else         // 结点中没有空位保存新插入的键值，必须分裂成两个结点   
#   {   
#    long nextinsertkey = 0;   
#    // 按照从小到大的顺序重新排列原有键值和新插入的键值   
#    // 并且按照键值的顺序重新排列保存子结点位置的数组   
#    bool issort2 = false;   
#    for (int m = 1, n = 0, o = 0; m < M; ++m, ++o)   
#    {   
#     if (node.key[m] < key || issort2)   
#     {   
#      keytemp[m-1+n] = node.key[m];   
#      childrentemp[o+n] = node.children[o];   
#     }   
#     else   
#     {   
#      keytemp[m-1] = key;   
#      childrentemp[o] = node.children[o];   
#      childrentemp[o+1] = nodenewposition;   
#      n = 1;   
#      --m;   
#      issort2 = true;   
#     }   
#    }   
#    if (!issort2)   
#    {   
#     keytemp[M-1] = key;   
#     childrentemp[M-1] = node.children[M-1];   
#     childrentemp[M] = nodenewposition;   
#    }   
#    /*/ for debug //////////////////////////////////////////////////////  
#    cout << "keytemp: ";  
#    for (int a = 0; a < M; ++a)  
#     cout << keytemp[a] << " ";  
#    cout << endl;  
#    /////////////////////////////////////////////////////////////////*/   
#    node.amount = M/2+1;   
#    if (!node.isleave)      // 按照内部结点的方式创建新结点   
#    {   
#     nodenew.amount = M/2;   
#     for (int i = 0, j = 1; i <= M; ++i)   
#     {   
#      if (i < M/2)   
#      {   
#       node.key[i+1] = keytemp[i];   
#       node.children[i] = childrentemp[i];   
#      }   
#      else if (i == M/2)   
#      {   
#       nextinsertkey = keytemp[i];   
#       node.children[i] = childrentemp[i];   
#      }   
#      else if (i < M)   
#      {   
#       nodenew.key[j] = keytemp[i];   
#       nodenew.children[j-1] = childrentemp[i];   
#       node.key[i] = 0;   
#       ++j;   
#      }   
#      else if (i == M)   
#      {   
#       nodenew.children[j-1] = childrentemp[i];   
#      }   
#     }   
#     nodenew.isleave = false;   
#    }   
#    else      // 按照叶结点的方式创建新结点   
#    {   
#     nodenew.amount = M/2+1;   
#     for (int i = 0, j = 1; i < M; ++i)   
#     {   
#      if (i < M/2)   
#      {   
#       node.key[i+1] = keytemp[i];   
#      }   
#      else   
#      {   
#       nodenew.key[j] = keytemp[i];   
#       if (i < M-1)   
#        node.key[i+1] = 0;   
#       ++j;   
#      }   
#     }   
#     nextinsertkey = nodenew.key[1];   
#     nodenew.isleave = true;   
#     for (int n = 0; n < M; ++n)   
#      nodenew.children[n] = 0;   
#    }   
#    nodenew.key[0] = 0;   
#    nodenew.father = node.father;   
#    nodenew.left = position;   
#    nodenew.right = node.right;   
#    nodenew.isactive = true;   
#    // 查找新结点的插入位置   
#    // 若索引文件中存在一个曾经被删除的结点，则用新结点覆盖掉这个结点   
#    // 若不存在这样的结点，则将新结点添加到索引文件尾部   
#    iofile.seekp(8, ios::beg);   
#    do   
#    {   
#     cur = iofile.tellp();   
#     iofile.read((char *)&nodetemp2, sizeof(BPlusNode));   
#    }   
#    while(nodetemp2.isactive && iofile.tellp() < posEnd);   
#    if (nodetemp2.isactive)   
#    {   
#     nodenewposition = iofile.tellp();   
#     iofile.write((char *)&nodenew, sizeof(BPlusNode));   
#    }   
#    else   
#    {   
#     iofile.seekp(cur, ios::beg);   
#     nodenewposition = cur;   
#     iofile.write((char *)&nodenew, sizeof(BPlusNode));   
#    }   
#    node.right = nodenewposition;   
#    iofile.seekp(position, ios::beg);   
#    iofile.write((char *)&node, sizeof(BPlusNode));   
#    iofile.close();   
#    if (insertkey(nextinsertkey, nodenew.father))      // 递归调用插入算法将分裂后需要插入到父结点的键值插入到父结点中   
#     return true;   
#    else return false;   
#   }   
#  }   
# }   
# // 删除给定的键值   
# // 该算法不符合B+树的删除规则   
# // 只是简单地将除被删除键值外的其它键值重新插入一遍   
# bool deletekey (long key, long position)   
# {   
#  fstream iofile;   
#  iofile.open("BPlusTreeData.dat", ios::binary|ios::in|ios::out);   
#  BPlusNode node;   
#  long *keynumbertemp = new long[];   
#  long number = 0;   
#  long posEnd;   
#  iofile.seekp(0, ios::end);   
#  posEnd = iofile.tellp();   
#  iofile.seekp(4, ios::beg);   
#  iofile.read((char *)&smallest, sizeof(long));   
#  iofile.seekp(smallest, ios::beg);   
#  do   
#  {   
#   iofile.read((char *)&node, sizeof(BPlusNode));   
#   for (int i = 1; i < node.amount; ++i)   
#   {   
#    keynumbertemp[number] = node.key[i];   
#    ++number;   
#   }   
#   if (node.right == 0)   
#   {   
#    --number;   
#    break;   
#   }   
#   iofile.seekp(node.right, ios::beg);   
#  }   
#  while(true);   
#  /*/ for debug /////////////////////////////////////////////////////  
#  cout << "smallest: " << smallest << endl;  
#  for (int x = 0; x <= number; ++x)  
#  {  
#   cout << keynumbertemp[x] << " " << endl;  
#  }  
#  /////////////////////////////////////////////////////////////////*/   
#  node.amount = 1;   
#  for (int j = 0; j < M; ++j)   
#  {   
#   node.key[j] = 0;   
#   node.children[j] = 0;   
#  }   
#  node.father = 0;   
#  node.left = 0;   
#  node.right = 0;   
#  node.isactive = true;   
#  node.isleave = true;   
#  root = 8;   
#  smallest = 8;   
#  iofile.seekp(0, ios::beg);   
#  iofile.write((char *)&root, sizeof(long));   
#  iofile.write((char *)&smallest, sizeof(long));   
#  iofile.write((char *)&node, sizeof(BPlusNode));   
#  for (;iofile.tellp() < posEnd;)   
#  {   
#   iofile.read((char *)&node, sizeof(BPlusNode));   
#   node.isactive = false;   
#   iofile.seekp(-long(sizeof(BPlusNode)), ios::cur);   
#   iofile.write((char *)&node, sizeof(BPlusNode));   
#  }   
#  iofile.close();   
#  for (int k = 0; k <= number; ++k)   
#  {   
#   if (keynumbertemp[k] == key)   
#    continue;   
#   findkey(keynumbertemp[k], position);   
#   insertkey(keynumbertemp[k], position);   
#  }   
#  return true;   
# }</windows.h></string></fstream></iostream>