b+.cpp

b+ tree code implementation and insertion deletion

# #include <iostream>   
# #include <fstream>   
# #include <string>   
# #include <windows.h>   
# using namespace std;   
# // 定义B+树的阶数   
# #define M 4   
# // B+树结点定义   
# struct BPlusNode   
# {   
#  int amount;       // 该结点中已保存的键值个数   
#  long key[M];      // 键值数组   
#  long children[M]; // 子结点位置数组   
#  long father;      // 父结点位置   
#  long left;        // 同一层中的左结点位置   
#  long right;       // 同一层中的右结点位置   
#  bool isactive;    // 有效位   
#  bool isleave;     // 标志该结点是否叶结点   
# };   
# // 函数头定义   
# bool findkey (long key, long &position);   // 查找包含给定键值的结点位置   
# bool insertkey (long key, long position);  // 插入一个新键值   
# bool deletekey (long key, long position);  // 删除给定的键值   
# void printkey (long mode);                 // 按照给定模式输出B+树   
# // 全局变量   
# static long pre;             // 上一个被访问的结点   
# static long cur;             // 当前指向的结点   
# static long root;            // 根结点位置   
# static long smallest;        // 保存最小关键值的叶结点   
# static long nodenewposition; // 新插入的结点位置   
# // 主函数   
# void main()   
# {   
#  string command;   
#  long keynumber;   
#  BPlusNode node;   
#  long position = -1;   
#  int tick1,tick2;   
#  fstream iofile;   
#  // 检测索引文件是否存在，若不存在则创建一个初始化的索引文件，其中包含根结点位置，最小键值位置和一个空结点   
#  fstream infile ("BPlusTreeData.dat", ios::binary|ios::in);   
#  if (!infile)   
#  {   
#   node.amount = 1;//如果不存在，则创建根结点，且阶数M=4   
#   for (int i = 0; i < M; ++i)   
#   {   
#    node.key[i] = 0;   
#    node.children[i] = 0;   
#   }   
#   node.father = 0;   
#   node.left = 0;   
#   node.right = 0;   
#   node.isactive = true;   
#   node.isleave = true;   
#   root = 8;//root为什么＝8？   
#   smallest = 8;   
#   fstream outfile ("BPlusTreeData.dat", ios::binary|ios::out);//输出文件BPlusTreeData.dat   
#   outfile.seekp(0, ios::beg);//指针移到begin处，文件开头   
#   outfile.write((char *)&root, sizeof(long));//输出根结点   
#   outfile.write((char *)&smallest, sizeof(long));//输出最小关键字   
#   outfile.write((char *)&node, sizeof(BPlusNode));//输出头指针？   
#   outfile.close();   
#  }   
#  infile.close();   
#  // 循环获取命令行，执行给定的命令   
#  while (true)   
#  {   
#   cin >> command >> keynumber;   
#   // 插入一个新的键值，该值不能与已有关键值重复   
#   if (command == "insert")   
#   {   
#    tick1 = GetTickCount();   
#    if (findkey(keynumber, position))   
#    {   
#     cout << keynumber << " is already in this B+ tree" << endl;   
#    }   
#    else if (insertkey(keynumber, position))   
#    {   
#     tick2 = GetTickCount();   
#     cout << "Successful inserted in " << tick2 - tick1 << " millisecond" << endl;   
#    }   
#    else cout << "Action falled" << endl;   
#   }   
#   // 删除给定的键值   
#   else if (command == "delete")   
#   {   
#    if (deletekey(keynumber, position))   
#     cout << "Successful deleted" << endl;   
#   }   
#   // 按照指定模式输出B+数   
#   // 模式“1”输出整棵树结构   
#   // 模式“2”按照从小到大的顺序输出所有键值   
#   else if (command == "print")   
#   {   
#    tick1 = GetTickCount();   
#    printkey(keynumber);   
#    tick2 = GetTickCount();   
#    cout << "Printed in " << tick2 - tick1 << " millisecond" << endl;   
#   }   
#   // 退出程序   
#   else if (command == "exit")   
#    break;   
#   else   
#   {   
#    cout << "Please make sure the command is correct" << endl;   
#    continue;   
#   }   
#  }   
# }   
# // 查找包含给定键值的结点位置，若找到则返回“true”   
# // “position”保存最后访问的结点位置   
# bool findkey (long key, long &position)   
# {   
#  BPlusNode node;   
#  long point;   
#  fstream iofile ("BPlusTreeData.dat", ios::binary|ios::in|ios::out);   
#  iofile.seekp(0, ios::beg);   
#  iofile.read((char *)&root, sizeof(long));   
#  iofile.seekp(root, ios::beg);   
#  while (true)   
#  {   
#   cur = iofile.tellp();   
#   iofile.read((char *)&node, sizeof(BPlusNode));   
#   if(!node.isactive) continue;   
#      
#   // B+树只在叶结点保存记录信息   
#   // 所以查找必须执行到叶结点   
#   if(!node.isleave)      // 如果该结点不是叶结点，则根据键值决定访问哪个子结点   
#   {   
#    for (int i = 1; i < node.amount; ++i)   
#    {   
#     point = -1;   
#     if (node.key[i] > key)   
#     {   
#      point = node.children[i-1];   
#      break;   
#     }   
#    }   
#    if (point == -1) point = node.children[node.amount-1];   
#    iofile.seekp(point, ios::beg);   
#    pre = cur;   
#   }   
#   else                 // 如果该结点是叶结点，则顺序访问结点中的键值   
#   {   
#    for (int i = 1; i < node.amount; ++i)   
#    {   
#     if (node.key[i] == key)   
#     {   
#      position = cur;   
#      iofile.close();   
#      return true;   
#     }   
#    }   
#    position = cur;   
#    iofile.close();   
#    return false;   
#   }   
#  }   
# }   
# // 按照给定格式输出B+数   
# void printkey (long mode)   
# {   
#  BPlusNode node;   
#  int i = 1, k = 1;   
#  fstream iofile("BPlusTreeData.dat", ios::binary|ios::in|ios::out);   
#  /*/ for debug ///////////////////////////////////////////////////////////////////  
#  BPlusNode rootnode;  
#  iofile.read((char *)&root, sizeof(long));  
#  iofile.seekp(root, ios::beg);  
#  iofile.read((char *)&rootnode, sizeof(BPlusNode));  
#  cout << "root's children: ";  
#  for (int m = 0; m < rootnode.amount; ++m)  
#   cout << rootnode.children[m] << " ";  
#  cout << endl;  
#  ///////////////////////////////////////////////////////////////////////////////*/   
#  // 从根结点开始广度遍历，输出整棵B+树结构   
#  if (mode == 1)   
#  {   
#   iofile.seekp(0, ios::beg);   
#   iofile.read((char *)&root, sizeof(long));   
#   iofile.seekp(root, ios::beg);   
#   do   
#   {   
#    cur = iofile.tellp();   
#    cout << "level " << k << ":";   
#    do   
#    {   
#     iofile.read((char *)&node, sizeof(BPlusNode));   
#     cout << "   node " << i << ": ";   
#     for (int j = 1; j < node.amount; ++j)   
#      cout << node.key[j] << " ";   
#     if (node.right == 0)   
#     {   
#      i = 1;   
#      cout << endl;   
#      break;   
#     }   
#     iofile.seekp(node.right, ios::beg);   
#     ++i;   
#    }   
#    while(true);   
#    iofile.seekp(cur, ios::beg);   
#    iofile.read((char *)&node, sizeof(BPlusNode));   
#    if (node.children[0] == 0)   
#     break;   
#    iofile.seekp(node.children[0], ios::beg);   
#    ++k;   
#   }   
#   while (true);   
#   iofile.close();   
#  }   
#  // 从包含最小键值的叶结点开始按照从小到大的顺序输出所有键值   
#  else if (mode == 2)   
#  {   
#   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 l = 1; l < node.amount; ++l)   
#     cout << node.key[l] << " ";   
#    if (node.right == 0)   
#    {   
#     cout << endl;   
#     break;   
#    }   
#    iofile.seekp(node.right, ios::beg);   
#   }   
#   while(true);   
#   iofile.close();   
#  }   
# }   
# // 在位于“position”的结点中插入一个新键值“key”   
# // 按照B+树的规则，根据情况分裂结点   
# bool insertkey (long key, long position)   
# {   
#  fstream iofile;   
#  iofile.open("BPlusTreeData.dat", ios::binary|ios::in|ios::out);   
#  BPlusNode node;   
#  BPlusNode nodenew;   
#  BPlusNode nodetemp1, nodetemp2;   
#  long keytemp[M];   
#  long childrentemp[M+1];   
#  iofile.seekp(0, ios::end);   
#  long posEnd = iofile.tellp();   
#  //根节点分裂之后新建根节点   
#  if (position == 0)    
#  {   
#   iofile.seekp(0, ios::beg);   
#   iofile.read((char *)&root, sizeof(long));   
#   iofile.seekp(root, ios::beg);   
#   iofile.read((char *)&node, sizeof(BPlusNode));   
#   nodenew.amount = 2;   
#   nodenew.key[1] = key;   
#   nodenew.children[0] = root;   
#   nodenew.children[1] = nodenewposition;   
#   nodenew.father = 0;   
#   nodenew.left = 0;   
#   nodenew.right = 0;   
#   nodenew.isactive = true;   
#   nodenew.isleave = false;   
#   iofile.seekp(8, ios::beg);   
#   do   
#   {   
#    cur = iofile.tellp();   
#    iofile.read((char *)&nodetemp2, sizeof(BPlusNode));