SG-Database一种轻量、易扩展的关系式数据库系统 高效、灵活的关系式内存数据库

#include "BPlusTree.h" #include "stdio.h" #include "stdlib.h" CNode::CNode() { m_Type = NODE_TYPE_LEAF; m_Count = 0; m_pFather = nullptr; } CNode::~CNode() { DeleteChildren(); } // 获取一个最近的兄弟结点 CNode* CNode::GetBrother(int& flag) { CNode* pFather = GetFather(); //获取其父结点指针 if (nullptr == pFather) { return nullptr; } CNode* pBrother = nullptr; for (int i = 1; i <= pFather->GetCount() + 1; i++) //GetCount()表示获取数据或关键字数，要比指针数小1。 { // 找到本结点的位置 if (pFather->GetPointer(i) == this) { if (i == (pFather->GetCount() + 1)) //表示其为父结点的最右边孩子。 { pBrother = pFather->GetPointer(i - 1); // 本身是最后一个指针，只能找前一个指针 flag = FLAG_LEFT; } else { pBrother = pFather->GetPointer(i + 1); // 优先找后一个指针 flag = FLAG_RIGHT; } } } return pBrother; } // 递归删除子结点 void CNode::DeleteChildren() // 疑问：这里的指针下标是否需要从0开始 { for (int i = 1; i <= GetCount(); i++) //GetCount()为返回结点中关键字即数据的个数 { CNode * pNode = GetPointer(i); if (nullptr != pNode) // 叶子结点没有指针 { pNode->DeleteChildren(); } delete pNode; } } //将内部节点的关键字和指针分别初始化为0和空 CInternalNode::CInternalNode() { m_Type = NODE_TYPE_INTERNAL; int i = 0; for (i = 0; i < MAXNUM_KEY; i++) { m_Keys[i] = INVALID; } for (i = 0; i < MAXNUM_POINTER; i++) { m_Pointers[i] = nullptr; } } CInternalNode::~CInternalNode() { for (int i = 0; i < MAXNUM_POINTER; i++) { m_Pointers[i] = nullptr; } } // 在中间结点中插入键。 /*疑问：中间结点需要插入值吗？在插入值时，通常都是先找到在叶子结点中的位置，然后再插入。 中间结点通常当叶子结点需要分裂时将分裂后的两个孩子结点插入其中*/ bool CInternalNode::Insert(DATA_TYPE value, CNode* pNode) { int i; // 如果中间结点已满，直接返回失败 if (GetCount() >= MAXNUM_KEY) { return false; } int j = 0; // 当前位置及其后面的键依次后移，空出当前位置 for (j = m_Count; j > i; j--) { m_Keys[j] = m_Keys[j - 1]; } // 当前位置及其后面的指针依次后移 for (j = m_Count + 1; j > i + 1; j--) { m_Pointers[j] = m_Pointers[j - 1]; } // 把键和指针存入当前位置 m_Keys[i] = value; m_Pointers[i + 1] = pNode; // 注意是第i+1个指针而不是第i个指针 pNode->SetFather(this); // 非常重要 该函数的意思是插入关键字value及其所指向子树 m_Count++; // 返回成功 return true; } // 在中间结点中删除键，以及该键后的指针 bool CInternalNode::Delete(DATA_TYPE key) { int i,j,k; for (i = 0; (key >= m_Keys[i]) && (i < m_Count); i++) { } for (j = i - 1; j < m_Count - 1; j++) { m_Keys[j] = m_Keys[j + 1]; } m_Keys[j] = INVALID; for (k = i; k < m_Count; k++) { m_Pointers[k] = m_Pointers[k + 1]; } m_Pointers[k] = nullptr; m_Count--; return true; } /* 分裂中间结点 分裂中间结点和分裂叶子结点完全不同，因为中间结点不仅有2V键，还有2V+1指针，如果单纯地一分为2，指针将无法分 配。 因此根据http://www.seanster.com/BplusTree/BplusTree.html ，分裂中 间结点的算法是： 根据要插入的键key判断： (1)如果key小于第V个键，则把第V个键提出来,其左右的键分别分到两个结点中 (2) 如果key大于第V+1个键，则把第V+1个键提出来,其左右的键分别分到两个结点中 (3)如果key介于第V和V+1个键之间，则把key作为 要提出的键，原来的键各分一半到两个结点中 提出来的RetKey作用是便于后续插入到祖先结点 */ DATA_TYPE CInternalNode::Split(CInternalNode* pNode, DATA_TYPE key) //key是新插入的值，pNode是分裂结点 { int i = 0, j = 0; // 如果要插入的键值在第V和V+1个键值中间，需要翻转一下，因此先处理此情况 if ((key > this->GetElement(ORDER_V)) && (key < this->GetElement(ORDER_V + 1))) { // 把第V+1 -- 2V个键移到指定的结点中 for (i = ORDER_V + 1; i <= MAXNUM_KEY; i++) { j++; pNode->SetElement(j, this->GetElement(i)); this->SetElement(i, INVALID); } // 把第V+2 -- 2V+1个指针移到指定的结点中 j = 0; for (i = ORDER_V + 2; i <= MAXNUM_POINTER; i++) { j++; this->GetPointer(i)->SetFather(pNode); // 重新设置子结点的父亲 pNode->SetPointer(j, this->GetPointer(i)); this->SetPointer(i, nullptr); } // 设置好Count个数 this->SetCount(ORDER_V); pNode->SetCount(ORDER_V); // 把原键值返回 return key; } // 以下处理key小于第V个键值或key大于第V+1个键值的情况 // 判断是提取第V还是V+1个键 int position = 0; if (key < this->GetElement(ORDER_V)) { position = ORDER_V; } else { position = ORDER_V + 1; } // 把第position个键提出来，作为新的键值返回 DATA_TYPE RetKey = this->GetElement(position); // 把第position+1 -- 2V个键移到指定的结点中 j = 0; for (i = position + 1; i <= MAXNUM_KEY; i++) { j++; pNode->SetElement(j, this->GetElement(i)); this->SetElement(i, INVALID); } // 把第position+1 -- 2V+1个指针移到指定的结点中(注意指针比键多一个) j = 0; for (i = position + 1; i <= MAXNUM_POINTER; i++) { j++; this->GetPointer(i)->SetFather(pNode); // 重新设置子结点的父亲 pNode->SetPointer(j, this->GetPointer(i)); this->SetPointer(i, nullptr); } // 清除提取出的位置 this->SetElement(position, INVALID); // 设置好Count个数 this->SetCount(position - 1); pNode->SetCount(MAXNUM_KEY - position); return RetKey; } //结合结点，把指定中间结点的数据全部剪切到本中间结点 bool CInternalNode::Combine(CNode* pNode) { // 参数检查 if (this->GetCount() + pNode->GetCount() + 1> MAXNUM_DATA) // 预留一个新键的位置 { return false; } // 取待合并结点的第一个孩子的第一个元素作为新键值 DATA_TYPE NewKey = pNode->GetPointer(1)->GetElement(1); //疑问：感觉应该改为KEY_TYPE NewKey = pNode->GetElement(1); m_Keys[m_Count] = NewKey; m_Count++; m_Pointers[m_Count] = pNode->GetPointer(1); //疑问：感觉应该为m_Pointers[m_Count+1] = pNode->GetPointer(1); for (int i = 1; i <= pNode->GetCount(); i++) { m_Keys[m_Count] = pNode->GetElement(i); m_Count++; m_Pointers[m_Count] = pNode->GetPointer(i+1); } return true; } // 从另一结点移一个元素到本结点 bool CInternalNode::MoveOneElement(CNode* pNode) { // 参数检查 if (this->GetCount() >= MAXNUM_DATA) { return false; } int i,j; // 兄弟结点在本结点左边 if (pNode->GetElement(1) < this->GetElement(1)) { // 先腾出位置 for (i = m_Count; i > 0; i--) { m_Keys[i] = m_Keys[i -1]; } for (j = m_Count + 1; j > 0; j--) { m_Pointers[j] = m_Pointers[j -1]; } // 赋值 // 第一个键值不是兄弟结点的最后一个键�