定義：
一棵M（M>2）階的B+樹滿足以下定義：
1.B+樹中包含兩種類型的結點：內結點和葉子結點。內結點存有關鍵字和孩子結點的指針，葉子結點存有關鍵字和數據；
2.每一個關鍵字都會在葉子結點中出現，葉子結點按照關鍵字的大小排序，葉子結點中會存有指向兄弟結點的指針；
3.一棵B+樹一般存有兩個指針：一個指向根結點，一個指向存有最小關鍵字的葉子結點；
4.每個內結點至多有M個子樹；
5.每個非根內結點至少有ceiling(M/2)個子樹；
6.N個子樹對應N-1個關鍵字（ps：另外一種說法是N個子樹對應N個關鍵字，
7.一個結點內關鍵字key1、key2、...、keyN，對應著N+1個孩子結點指針child1、child2、...、childN+1，且有child1<key1<child2<key2<...<keyN<childN+1；
8.葉子結點的關鍵字個數可以單獨設置，一般和內結點關鍵字個數相同。
一圖勝千言（圖片來源：維基百科）：
實現
BPlus_node.h
[cpp]
#ifndef BPLUS_NODE
#define BPLUS_NODE
#define NULL 0
enum NODE_TYPE{INTERNAL, LEAF}; // 結點類型：內結點、葉子結點
enum SIBLING_DIRECTION{LEFT, RIGHT}; // 兄弟結點方向：左兄弟結點、右兄弟結點
typedef float KeyType; // 鍵類型
typedef int DataType; // 值類型
const int ORDER = 7; // B+樹的階（非根內結點的最小子樹個數）
const int MINNUM_KEY = ORDER-1; // 最小鍵值個數
const int MAXNUM_KEY = 2*ORDER-1; // 最大鍵值個數
const int MINNUM_CHILD = MINNUM_KEY+1; // 最小子樹個數
const int MAXNUM_CHILD = MAXNUM_KEY+1; // 最大子樹個數
const int MINNUM_LEAF = MINNUM_KEY; // 最小葉子結點鍵值個數
const int MAXNUM_LEAF = MAXNUM_KEY; // 最大葉子結點鍵值個數
// 結點基類
class CNode{
public:
CNode();
virtual ~CNode();
NODE_TYPE getType() const {return m_Type;}
void setType(NODE_TYPE type){m_Type = type;}
int getKeyNum() const {return m_KeyNum;}
void setKeyNum(int n){m_KeyNum = n;}
KeyType getKeyValue(int i) const {return m_KeyValues[i];}
void setKeyValue(int i, KeyType key){m_KeyValues[i] = key;}
int getKeyIndex(KeyType key)const; // 找到鍵值在結點中存儲的下標
// 純虛函數，定義接口
virtual void removeKey(int keyIndex, int childIndex)=0; // 從結點中移除鍵值
virtual void split(CNode* parentNode, int childIndex)=0; // 分裂結點
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)=0; // 合並結點
virtual void clear()=0; // 清空結點，同時會清空結點所包含的子樹結點
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)=0; // 從兄弟結點中借一個鍵值
virtual int getChildIndex(KeyType key, int keyIndex)const=0; // 根據鍵值獲取孩子結點指針下標
protected:
NODE_TYPE m_Type;
int m_KeyNum;
KeyType m_KeyValues[MAXNUM_KEY];
};
// 內結點
class CInternalNode : public CNode{
public:
CInternalNode();
virtual ~CInternalNode();
CNode* getChild(int i) const {return m_Childs[i];}
void setChild(int i, CNode* child){m_Childs[i] = child;}
void insert(int keyIndex, int childIndex, KeyType key, CNode* childNode);
virtual void split(CNode* parentNode, int childIndex);
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex);
virtual void removeKey(int keyIndex, int childIndex);
virtual void clear();
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d);
virtual int getChildIndex(KeyType key, int keyIndex)const;
private:
CNode* m_Childs[MAXNUM_CHILD];
};
// 葉子結點
class CLeafNode : public CNode{
public:
CLeafNode();
virtual ~CLeafNode();
CLeafNode* getLeftSibling() const {return m_LeftSibling;}
void setLeftSibling(CLeafNode* node){m_LeftSibling = node;}
CLeafNode* getRightSibling() const {return m_RightSibling;}
void setRightSibling(CLeafNode* node){m_RightSibling = node;}
DataType getData(int i) const {return m_Datas[i];}
void setData(int i, const DataType& data){m_Datas[i] = data;}
void insert(KeyType key, const DataType& data);
virtual void split(CNode* parentNode, int childIndex);
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex);
virtual void removeKey(int keyIndex, int childIndex);
virtual void clear();
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d);
virtual int getChildIndex(KeyType key, int keyIndex)const;
private:
CLeafNode* m_LeftSibling;
CLeafNode* m_RightSibling;
DataType m_Datas[MAXNUM_LEAF];
};
#endif
#ifndef BPLUS_NODE
#define BPLUS_NODE
#define NULL 0
enum NODE_TYPE{INTERNAL, LEAF}; // 結點類型：內結點、葉子結點
enum SIBLING_DIRECTION{LEFT, RIGHT}; // 兄弟結點方向：左兄弟結點、右兄弟結點
typedef float KeyType; // 鍵類型
typedef int DataType; // 值類型
const int ORDER = 7; // B+樹的階（非根內結點的最小子樹個數）
const int MINNUM_KEY = ORDER-1; // 最小鍵值個數
const int MAXNUM_KEY = 2*ORDER-1; // 最大鍵值個數
const int MINNUM_CHILD = MINNUM_KEY+1; // 最小子樹個數
const int MAXNUM_CHILD = MAXNUM_KEY+1; // 最大子樹個數
const int MINNUM_LEAF = MINNUM_KEY; // 最小葉子結點鍵值個數
const int MAXNUM_LEAF = MAXNUM_KEY; // 最大葉子結點鍵值個數
// 結點基類
class CNode{
public:
CNode();
virtual ~CNode();
NODE_TYPE getType() const {return m_Type;}
void setType(NODE_TYPE type){m_Type = type;}
int getKeyNum() const {return m_KeyNum;}
void setKeyNum(int n){m_KeyNum = n;}
KeyType getKeyValue(int i) const {return m_KeyValues[i];}
void setKeyValue(int i, KeyType key){m_KeyValues[i] = key;}
int getKeyIndex(KeyType key)const; // 找到鍵值在結點中存儲的下標
// 純虛函數，定義接口
virtual void removeKey(int keyIndex, int childIndex)=0; // 從結點中移除鍵值
virtual void split(CNode* parentNode, int childIndex)=0; // 分裂結點
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)=0; // 合並結點
virtual void clear()=0; // 清空結點，同時會清空結點所包含的子樹結點
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)=0; // 從兄弟結點中借一個鍵值
virtual int getChildIndex(KeyType key, int keyIndex)const=0; // 根據鍵值獲取孩子結點指針下標
protected:
NODE_TYPE m_Type;
int m_KeyNum;
KeyType m_KeyValues[MAXNUM_KEY];
};
// 內結點
class CInternalNode : public CNode{
public:
CInternalNode();
virtual ~CInternalNode();
CNode* getChild(int i) const {return m_Childs[i];}
void setChild(int i, CNode* child){m_Childs[i] = child;}
void insert(int keyIndex, int childIndex, KeyType key, CNode* childNode);
virtual void split(CNode* parentNode, int childIndex);
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex);
virtual void removeKey(int keyIndex, int childIndex);
virtual void clear();
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d);
virtual int getChildIndex(KeyType key, int keyIndex)const;
private:
CNode* m_Childs[MAXNUM_CHILD];
};
// 葉子結點
class CLeafNode : public CNode{
public:
CLeafNode();
virtual ~CLeafNode();
CLeafNode* getLeftSibling() const {return m_LeftSibling;}
void setLeftSibling(CLeafNode* node){m_LeftSibling = node;}
CLeafNode* getRightSibling() const {return m_RightSibling;}
void setRightSibling(CLeafNode* node){m_RightSibling = node;}
DataType getData(int i) const {return m_Datas[i];}
void setData(int i, const DataType& data){m_Datas[i] = data;}
void insert(KeyType key, const DataType& data);
virtual void split(CNode* parentNode, int childIndex);
virtual void mergeChild(CNode* parentNode, CNode* childNode, int keyIndex);
virtual void removeKey(int keyIndex, int childIndex);
virtual void clear();
virtual void borrowFrom(CNode* destNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d);
virtual int getChildIndex(KeyType key, int keyIndex)const;
private:
CLeafNode* m_LeftSibling;
CLeafNode* m_RightSibling;
DataType m_Datas[MAXNUM_LEAF];
};
#endifBPlus_node.cpp
[cpp] view plaincopyprint?#include "BPlus_node.h"
// CNode
CNode::CNode(){
setType(LEAF);
setKeyNum(0);
}
CNode::~CNode(){
setKeyNum(0);
}
int CNode::getKeyIndex(KeyType key)const
{
int left = 0;
int right = getKeyNum()-1;
int current;
while(left!=right)
{
current = (left+right)/2;
KeyType currentKey = getKeyValue(current);
if (key>currentKey)
{
left = current+1;
}
else
{
right = current;
}
}
return left;
}
// CInternalNode
CInternalNode::CInternalNode():CNode(){
setType(INTERNAL);
}
CInternalNode::~CInternalNode(){
}
void CInternalNode::clear()
{
for (int i=0; i<=m_KeyNum; ++i)
{
m_Childs[i]->clear();
delete m_Childs[i];
m_Childs[i] = NULL;
}
}
void CInternalNode::split(CNode* parentNode, int childIndex)
{
CInternalNode* newNode = new CInternalNode();//分裂後的右節點
newNode->setKeyNum(MINNUM_KEY);
int i;
for (i=0; i<MINNUM_KEY; ++i)// 拷貝關鍵字的值
{
newNode->setKeyValue(i, m_KeyValues[i+MINNUM_CHILD]);
}
for (i=0; i<MINNUM_CHILD; ++i) // 拷貝孩子節點指針
{
newNode->setChild(i, m_Childs[i+MINNUM_CHILD]);
}
setKeyNum(MINNUM_KEY); //更新左子樹的關鍵字個數
((CInternalNode*)parentNode)->insert(childIndex, childIndex+1, m_KeyValues[MINNUM_KEY], newNode);
}
void CInternalNode::insert(int keyIndex, int childIndex, KeyType key, CNode* childNode){
int i;
for (i=getKeyNum(); i>keyIndex; --i)//將父節點中的childIndex後的所有關鍵字的值和子樹指針向後移一位
{
setChild(i+1,m_Childs[i]);
setKeyValue(i,m_KeyValues[i-1]);
}
if (i==childIndex)
{
setChild(i+1, m_Childs[i]);
}
setChild(childIndex, childNode);
setKeyValue(keyIndex, key);
setKeyNum(m_KeyNum+1);
}
void CInternalNode::mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)
{
// 合並數據
insert(MINNUM_KEY, MINNUM_KEY+1, parentNode->getKeyValue(keyIndex), ((CInternalNode*)childNode)->getChild(0));
int i;
for (i=1; i<=childNode->getKeyNum(); ++i)
{
insert(MINNUM_KEY+i, MINNUM_KEY+i+1, childNode->getKeyValue(i-1), ((CInternalNode*)childNode)->getChild(i));
}
//父節點刪除index的key
parentNode->removeKey(keyIndex, keyIndex+1);
delete ((CInternalNode*)parentNode)->getChild(keyIndex+1);
}
void CInternalNode::removeKey(int keyIndex, int childIndex)
{
for (int i=0; i<getKeyNum()-keyIndex-1; ++i)
{
setKeyValue(keyIndex+i, getKeyValue(keyIndex+i+1));
setChild(childIndex+i, getChild(childIndex+i+1));
}
setKeyNum(getKeyNum()-1);
}
void CInternalNode::borrowFrom(CNode* siblingNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)
{
switch(d)
{
case LEFT: // 從左兄弟結點借
{
insert(0, 0, parentNode->getKeyValue(keyIndex), ((CInternalNode*)siblingNode)->getChild(siblingNode->getKeyNum()));
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(siblingNode->getKeyNum()-1));
siblingNode->removeKey(siblingNode->getKeyNum()-1, siblingNode->getKeyNum());
}
break;
case RIGHT: // 從右兄弟結點借
{
insert(getKeyNum(), getKeyNum()+1, parentNode->getKeyValue(keyIndex), ((CInternalNode*)siblingNode)->getChild(0));
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(0));
siblingNode->removeKey(0, 0);
}
break;
default:
break;
}
}
int CInternalNode::getChildIndex(KeyType key, int keyIndex)const
{
if (key==getKeyValue(keyIndex))
{
return keyIndex+1;
}
else
{
return keyIndex;
}
}
// CLeafNode
CLeafNode::CLeafNode():CNode(){
setType(LEAF);
setLeftSibling(NULL);
setRightSibling(NULL);
}
CLeafNode::~CLeafNode(){
}
void CLeafNode::clear()
{
for (int i=0; i<m_KeyNum; ++i)
{
// if type of m_Datas is pointer
//delete m_Datas[i];
//m_Datas[i] = NULL;
}
}
void CLeafNode::insert(KeyType key, const DataType& data)
{
int i;
for (i=m_KeyNum; i>=1 && m_KeyValues[i-1]>key; --i)
{
setKeyValue(i, m_KeyValues[i-1]);
setData(i, m_Datas[i-1]);
}
setKeyValue(i, key);
setData(i, data);
setKeyNum(m_KeyNum+1);
}
void CLeafNode::split(CNode* parentNode, int childIndex)
{
CLeafNode* newNode = new CLeafNode();//分裂後的右節點
setKeyNum(MINNUM_LEAF);
newNode->setKeyNum(MINNUM_LEAF+1);
newNode->setRightSibling(getRightSibling());
setRightSibling(newNode);
newNode->setLeftSibling(this);
int i;
for (i=0; i<MINNUM_LEAF+1; ++i)// 拷貝關鍵字的值
{
newNode->setKeyValue(i, m_KeyValues[i+MINNUM_LEAF]);
}
for (i=0; i<MINNUM_LEAF+1; ++i)// 拷貝數據
{
newNode->setData(i, m_Datas[i+MINNUM_LEAF]);
}
((CInternalNode*)parentNode)->insert(childIndex, childIndex+1, m_KeyValues[MINNUM_LEAF], newNode);
}
void CLeafNode::mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)
{
// 合並數據
for (int i=0; i<childNode->getKeyNum(); ++i)
{
insert(childNode->getKeyValue(i), ((CLeafNode*)childNode)->getData(i));
}
setRightSibling(((CLeafNode*)childNode)->getRightSibling());
//父節點刪除index的key，
parentNode->removeKey(keyIndex, keyIndex+1);
}
void CLeafNode::removeKey(int keyIndex, int childIndex)
{
for (int i=keyIndex; i<getKeyNum()-1; ++i)
{
setKeyValue(i, getKeyValue(i+1));
setData(i, getData(i+1));
}
setKeyNum(getKeyNum()-1);
}
void CLeafNode::borrowFrom(CNode* siblingNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)
{
switch(d)
{
case LEFT: // 從左兄弟結點借
{
insert(siblingNode->getKeyValue(siblingNode->getKeyNum()-1), ((CLeafNode*)siblingNode)->getData(siblingNode->getKeyNum()-1));
siblingNode->removeKey(siblingNode->getKeyNum()-1, siblingNode->getKeyNum()-1);
parentNode->setKeyValue(keyIndex, getKeyValue(0));
}
break;
case RIGHT: // 從右兄弟結點借
{
insert(siblingNode->getKeyValue(0), ((CLeafNode*)siblingNode)->getData(0));
siblingNode->removeKey(0, 0);
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(0));
}
break;
default:
break;
}
}
int CLeafNode::getChildIndex(KeyType key, int keyIndex)const
{
return keyIndex;
}
#include "BPlus_node.h"
// CNode
CNode::CNode(){
setType(LEAF);
setKeyNum(0);
}
CNode::~CNode(){
setKeyNum(0);
}
int CNode::getKeyIndex(KeyType key)const
{
int left = 0;
int right = getKeyNum()-1;
int current;
while(left!=right)
{
current = (left+right)/2;
KeyType currentKey = getKeyValue(current);
if (key>currentKey)
{
left = current+1;
}
else
{
right = current;
}
}
return left;
}
// CInternalNode
CInternalNode::CInternalNode():CNode(){
setType(INTERNAL);
}
CInternalNode::~CInternalNode(){
}
void CInternalNode::clear()
{
for (int i=0; i<=m_KeyNum; ++i)
{
m_Childs[i]->clear();
delete m_Childs[i];
m_Childs[i] = NULL;
}
}
void CInternalNode::split(CNode* parentNode, int childIndex)
{
CInternalNode* newNode = new CInternalNode();//分裂後的右節點
newNode->setKeyNum(MINNUM_KEY);
int i;
for (i=0; i<MINNUM_KEY; ++i)// 拷貝關鍵字的值
{
newNode->setKeyValue(i, m_KeyValues[i+MINNUM_CHILD]);
}
for (i=0; i<MINNUM_CHILD; ++i) // 拷貝孩子節點指針
{
newNode->setChild(i, m_Childs[i+MINNUM_CHILD]);
}
setKeyNum(MINNUM_KEY); //更新左子樹的關鍵字個數
((CInternalNode*)parentNode)->insert(childIndex, childIndex+1, m_KeyValues[MINNUM_KEY], newNode);
}
void CInternalNode::insert(int keyIndex, int childIndex, KeyType key, CNode* childNode){
int i;
for (i=getKeyNum(); i>keyIndex; --i)//將父節點中的childIndex後的所有關鍵字的值和子樹指針向後移一位
{
setChild(i+1,m_Childs[i]);
setKeyValue(i,m_KeyValues[i-1]);
}
if (i==childIndex)
{
setChild(i+1, m_Childs[i]);
}
setChild(childIndex, childNode);
setKeyValue(keyIndex, key);
setKeyNum(m_KeyNum+1);
}
void CInternalNode::mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)
{
// 合並數據
insert(MINNUM_KEY, MINNUM_KEY+1, parentNode->getKeyValue(keyIndex), ((CInternalNode*)childNode)->getChild(0));
int i;
for (i=1; i<=childNode->getKeyNum(); ++i)
{
insert(MINNUM_KEY+i, MINNUM_KEY+i+1, childNode->getKeyValue(i-1), ((CInternalNode*)childNode)->getChild(i));
}
//父節點刪除index的key
parentNode->removeKey(keyIndex, keyIndex+1);
delete ((CInternalNode*)parentNode)->getChild(keyIndex+1);
}
void CInternalNode::removeKey(int keyIndex, int childIndex)
{
for (int i=0; i<getKeyNum()-keyIndex-1; ++i)
{
setKeyValue(keyIndex+i, getKeyValue(keyIndex+i+1));
setChild(childIndex+i, getChild(childIndex+i+1));
}
setKeyNum(getKeyNum()-1);
}
void CInternalNode::borrowFrom(CNode* siblingNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)
{
switch(d)
{
case LEFT: // 從左兄弟結點借
{
insert(0, 0, parentNode->getKeyValue(keyIndex), ((CInternalNode*)siblingNode)->getChild(siblingNode->getKeyNum()));
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(siblingNode->getKeyNum()-1));
siblingNode->removeKey(siblingNode->getKeyNum()-1, siblingNode->getKeyNum());
}
break;
case RIGHT: // 從右兄弟結點借
{
insert(getKeyNum(), getKeyNum()+1, parentNode->getKeyValue(keyIndex), ((CInternalNode*)siblingNode)->getChild(0));
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(0));
siblingNode->removeKey(0, 0);
}
break;
default:
break;
}
}
int CInternalNode::getChildIndex(KeyType key, int keyIndex)const
{
if (key==getKeyValue(keyIndex))
{
return keyIndex+1;
}
else
{
return keyIndex;
}
}
// CLeafNode
CLeafNode::CLeafNode():CNode(){
setType(LEAF);
setLeftSibling(NULL);
setRightSibling(NULL);
}
CLeafNode::~CLeafNode(){
}
void CLeafNode::clear()
{
for (int i=0; i<m_KeyNum; ++i)
{
// if type of m_Datas is pointer
//delete m_Datas[i];
//m_Datas[i] = NULL;
}
}
void CLeafNode::insert(KeyType key, const DataType& data)
{
int i;
for (i=m_KeyNum; i>=1 && m_KeyValues[i-1]>key; --i)
{
setKeyValue(i, m_KeyValues[i-1]);
setData(i, m_Datas[i-1]);
}
setKeyValue(i, key);
setData(i, data);
setKeyNum(m_KeyNum+1);
}
void CLeafNode::split(CNode* parentNode, int childIndex)
{
CLeafNode* newNode = new CLeafNode();//分裂後的右節點
setKeyNum(MINNUM_LEAF);
newNode->setKeyNum(MINNUM_LEAF+1);
newNode->setRightSibling(getRightSibling());
setRightSibling(newNode);
newNode->setLeftSibling(this);
int i;
for (i=0; i<MINNUM_LEAF+1; ++i)// 拷貝關鍵字的值
{
newNode->setKeyValue(i, m_KeyValues[i+MINNUM_LEAF]);
}
for (i=0; i<MINNUM_LEAF+1; ++i)// 拷貝數據
{
newNode->setData(i, m_Datas[i+MINNUM_LEAF]);
}
((CInternalNode*)parentNode)->insert(childIndex, childIndex+1, m_KeyValues[MINNUM_LEAF], newNode);
}
void CLeafNode::mergeChild(CNode* parentNode, CNode* childNode, int keyIndex)
{
// 合並數據
for (int i=0; i<childNode->getKeyNum(); ++i)
{
insert(childNode->getKeyValue(i), ((CLeafNode*)childNode)->getData(i));
}
setRightSibling(((CLeafNode*)childNode)->getRightSibling());
//父節點刪除index的key，
parentNode->removeKey(keyIndex, keyIndex+1);
}
void CLeafNode::removeKey(int keyIndex, int childIndex)
{
for (int i=keyIndex; i<getKeyNum()-1; ++i)
{
setKeyValue(i, getKeyValue(i+1));
setData(i, getData(i+1));
}
setKeyNum(getKeyNum()-1);
}
void CLeafNode::borrowFrom(CNode* siblingNode, CNode* parentNode, int keyIndex, SIBLING_DIRECTION d)
{
switch(d)
{
case LEFT: // 從左兄弟結點借
{
insert(siblingNode->getKeyValue(siblingNode->getKeyNum()-1), ((CLeafNode*)siblingNode)->getData(siblingNode->getKeyNum()-1));
siblingNode->removeKey(siblingNode->getKeyNum()-1, siblingNode->getKeyNum()-1);
parentNode->setKeyValue(keyIndex, getKeyValue(0));
}
break;
case RIGHT: // 從右兄弟結點借
{
insert(siblingNode->getKeyValue(0), ((CLeafNode*)siblingNode)->getData(0));
siblingNode->removeKey(0, 0);
parentNode->setKeyValue(keyIndex, siblingNode->getKeyValue(0));
}
break;
default:
break;
}
}
int CLeafNode::getChildIndex(KeyType key, int keyIndex)const
{
return keyIndex;
}BPlus_tree.h
[cpp]
#ifndef BPLUS_TREE_H
#define BPLUS_TREE_H
#include "BPlus_node.h"
#include <vector>
using namespace std;
enum COMPARE_OPERATOR{LT, LE, EQ, BE, BT, BETWEEN}; // 比較操作符：<、<=、=、>=、>、<>
const int INVALID_INDEX = -1;
struct SelectResult
{
int keyIndex;
CLeafNode* targetNode;
};
class CBPlusTree{
public:
CBPlusTree();
~CBPlusTree();
bool insert(KeyType key, const DataType& data);
bool remove(KeyType key);
bool update(KeyType oldKey, KeyType newKey);
// 定值查詢，compareOperator可以是LT(<)、LE(<=)、EQ(=)、BE(>=)、BT(>)
vector<DataType> select(KeyType compareKey, int compareOpeartor);
// 范圍查詢，BETWEEN
vector<DataType> select(KeyType smallKey, KeyType largeKey);
bool search(KeyType key); // 查找是否存在
void clear(); // 清空
void print()const; // 打印樹關鍵字
void printData()const; // 打印數據
private:
void recursive_insert(CNode* parentNode, KeyType key, const DataType& data);
void recursive_remove(CNode* parentNode, KeyType key);
void printInConcavo(CNode *pNode, int count)const;
bool recursive_search(CNode *pNode, KeyType key)const;
void changeKey(CNode *pNode, KeyType oldKey, KeyType newKey);
void search(KeyType key, SelectResult& result);
void recursive_search(CNode* pNode, KeyType key, SelectResult& result);
void remove(KeyType key, DataType& dataValue);
void recursive_remove(CNode* parentNode, KeyType key, DataType& dataValue);
private:
CNode* m_Root;
CLeafNode* m_DataHead;
KeyType m_MaxKey; // B+樹中的最大鍵
};
#endif
#ifndef BPLUS_TREE_H
#define BPLUS_TREE_H
#include "BPlus_node.h"
#include <vector>
using namespace std;
enum COMPARE_OPERATOR{LT, LE, EQ, BE, BT, BETWEEN}; // 比較操作符：<、<=、=、>=、>、<>
const int INVALID_INDEX = -1;
struct SelectResult
{
int keyIndex;
CLeafNode* targetNode;
};
class CBPlusTree{
public:
CBPlusTree();
~CBPlusTree();
bool insert(KeyType key, const DataType& data);
bool remove(KeyType key);
bool update(KeyType oldKey, KeyType newKey);
// 定值查詢，compareOperator可以是LT(<)、LE(<=)、EQ(=)、BE(>=)、BT(>)
vector<DataType> select(KeyType compareKey, int compareOpeartor);
// 范圍查詢，BETWEEN
vector<DataType> select(KeyType smallKey, KeyType largeKey);
bool search(KeyType key); // 查找是否存在
void clear(); // 清空
void print()const; // 打印樹關鍵字
void printData()const; // 打印數據
private:
void recursive_insert(CNode* parentNode, KeyType key, const DataType& data);
void recursive_remove(CNode* parentNode, KeyType key);
void printInConcavo(CNode *pNode, int count)const;
bool recursive_search(CNode *pNode, KeyType key)const;
void changeKey(CNode *pNode, KeyType oldKey, KeyType newKey);
void search(KeyType key, SelectResult& result);
void recursive_search(CNode* pNode, KeyType key, SelectResult& result);
void remove(KeyType key, DataType& dataValue);
void recursive_remove(CNode* parentNode, KeyType key, DataType& dataValue);
private:
CNode* m_Root;
CLeafNode* m_DataHead;
KeyType m_MaxKey; // B+樹中的最大鍵
};
#endif
BPlus_tree.cpp
[cpp] view plaincopyprint?#include "BPlus_tree.h"
#include <iostream>
#include <algorithm>
using namespace std;
CBPlusTree::CBPlusTree(){
m_Root = NULL;
m_DataHead = NULL;
}
CBPlusTree::~CBPlusTree(){
clear();
}
bool CBPlusTree::insert(KeyType key, const DataType& data){
// 是否已經存在
if (search(key))
{
return false;
}
// 找到可以插入的葉子結點，否則創建新的葉子結點
if(m_Root==NULL)
{
m_Root = new CLeafNode();
m_DataHead = (CLeafNode*)m_Root;
m_MaxKey = key;
}
if (m_Root->getKeyNum()>=MAXNUM_KEY) // 根結點已滿，分裂
{
CInternalNode* newNode = new CInternalNode(); //創建新的根節點
newNode->setChild(0, m_Root);
m_Root->split(newNode, 0); // 葉子結點分裂
m_Root = newNode; //更新根節點指針
}
if (key>m_MaxKey) // 更新最大鍵值
{
m_MaxKey = key;
}
recursive_insert(m_Root, key, data);
return true;
}
void CBPlusTree::recursive_insert(CNode* parentNode, KeyType key, const DataType& data)
{
if (parentNode->getType()==LEAF) // 葉子結點，直接插入
{
((CLeafNode*)parentNode)->insert(key, data);
}
else
{
// 找到子結點
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
CNode* childNode = ((CInternalNode*)parentNode)->getChild(childIndex);
if (childNode->getKeyNum()>=MAXNUM_LEAF) // 子結點已滿，需進行分裂
{
childNode->split(parentNode, childIndex);
if (parentNode->getKeyValue(childIndex)<=key) // 確定目標子結點
{
childNode = ((CInternalNode*)parentNode)->getChild(childIndex+1);
}
}
recursive_insert(childNode, key, data);
}
}
void CBPlusTree::clear()
{
if (m_Root!=NULL)
{
m_Root->clear();
delete m_Root;
m_Root = NULL;
m_DataHead = NULL;
}
}
bool CBPlusTree::search(KeyType key)
{
return recursive_search(m_Root, key);
}
bool CBPlusTree::recursive_search(CNode *pNode, KeyType key)const
{
if (pNode==NULL) //檢測節點指針是否為空，或該節點是否為葉子節點
{
return false;
}
else
{
int keyIndex = pNode->getKeyIndex(key);
int childIndex = pNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (keyIndex<pNode->getKeyNum() && key==pNode->getKeyValue(keyIndex))
{
return true;
}
else
{
if (pNode->getType()==LEAF) //檢查該節點是否為葉子節點
{
return false;
}
else
{
return recursive_search(((CInternalNode*)pNode)->getChild(childIndex), key);
}
}
}
}
void CBPlusTree::print()const
{
printInConcavo(m_Root, 10);
}
void CBPlusTree::printInConcavo(CNode *pNode, int count) const{
if (pNode!=NULL)
{
int i, j;
for (i=0; i<pNode->getKeyNum(); ++i)
{
if (pNode->getType()!=LEAF)
{
printInConcavo(((CInternalNode*)pNode)->getChild(i), count-2);
}
for (j=count; j>=0; --j)
{
cout<<"-";
}
cout<<pNode->getKeyValue(i)<<endl;
}
if (pNode->getType()!=LEAF)
{
printInConcavo(((CInternalNode*)pNode)->getChild(i), count-2);
}
}
}
void CBPlusTree::printData()const
{
CLeafNode* itr = m_DataHead;
while(itr!=NULL)
{
for (int i=0; i<itr->getKeyNum(); ++i)
{
cout<<itr->getData(i)<<" ";
}
cout<<endl;
itr = itr->getRightSibling();
}
}
bool CBPlusTree::remove(KeyType key)
{
if (!search(key)) //不存在
{
return false;
}
if (m_Root->getKeyNum()==1)//特殊情況處理
{
if (m_Root->getType()==LEAF)
{
clear();
return true;
}
else
{
CNode *pChild1 = ((CInternalNode*)m_Root)->getChild(0);
CNode *pChild2 = ((CInternalNode*)m_Root)->getChild(1);
if (pChild1->getKeyNum()==MINNUM_KEY && pChild2->getKeyNum()==MINNUM_KEY)
{
pChild1->mergeChild(m_Root, pChild2, 0);
delete m_Root;
m_Root = pChild1;
}
}
}
recursive_remove(m_Root, key);
return true;
}
// parentNode中包含的鍵值數>MINNUM_KEY
void CBPlusTree::recursive_remove(CNode* parentNode, KeyType key)
{
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (parentNode->getType()==LEAF)// 找到目標葉子節點
{
if (key==m_MaxKey&&keyIndex>0)
{
m_MaxKey = parentNode->getKeyValue(keyIndex-1);
}
parentNode->removeKey(keyIndex, childIndex); // 直接刪除
// 如果鍵值在內部結點中存在，也要相應的替換內部結點
if (childIndex==0 && m_Root->getType()!=LEAF && parentNode!=m_DataHead)
{
changeKey(m_Root, key, parentNode->getKeyValue(0));
}
}
else // 內結點
{
CNode *pChildNode = ((CInternalNode*)parentNode)->getChild(childIndex); //包含key的子樹根節點
if (pChildNode->getKeyNum()==MINNUM_KEY) // 包含關鍵字達到下限值，進行相關操作
{
CNode *pLeft = childIndex>0 ? ((CInternalNode*)parentNode)->getChild(childIndex-1) : NULL; //左兄弟節點
CNode *pRight = childIndex<parentNode->getKeyNum() ? ((CInternalNode*)parentNode)->getChild(childIndex+1) : NULL;//右兄弟節點
// 先考慮從兄弟結點中借
if (pLeft && pLeft->getKeyNum()>MINNUM_KEY)// 左兄弟結點可借
{
pChildNode->borrowFrom(pLeft, parentNode, childIndex-1, LEFT);
}
else if (pRight && pRight->getKeyNum()>MINNUM_KEY)//右兄弟結點可借
{
pChildNode->borrowFrom(pRight, parentNode, childIndex, RIGHT);
}
//左右兄弟節點都不可借，考慮合並
else if (pLeft) //與左兄弟合並
{
pLeft->mergeChild(parentNode, pChildNode, childIndex-1);
pChildNode = pLeft;
}
else if (pRight) //與右兄弟合並
{
pChildNode->mergeChild(parentNode, pRight, childIndex);
}
}
recursive_remove(pChildNode, key);
}
}
void CBPlusTree::changeKey(CNode *pNode, KeyType oldKey, KeyType newKey)
{
if (pNode!=NULL && pNode->getType()!=LEAF)
{
int keyIndex = pNode->getKeyIndex(oldKey);
if (keyIndex<pNode->getKeyNum() && oldKey==pNode->getKeyValue(keyIndex)) // 找到
{
pNode->setKeyValue(keyIndex, newKey);
}
else // 繼續找
{
changeKey(((CInternalNode*)pNode)->getChild(keyIndex), oldKey, newKey);
}
}
}
bool CBPlusTree::update(KeyType oldKey, KeyType newKey)
{
if (search(newKey)) // 檢查更新後的鍵是否已經存在
{
return false;
}
else
{
int dataValue;
remove(oldKey, dataValue);
if (dataValue==INVALID_INDEX)
{
return false;
}
else
{
return insert(newKey, dataValue);
}
}
}
void CBPlusTree::remove(KeyType key, DataType& dataValue)
{
if (!search(key)) //不存在
{
dataValue = INVALID_INDEX;
return;
}
if (m_Root->getKeyNum()==1)//特殊情況處理
{
if (m_Root->getType()==LEAF)
{
dataValue = ((CLeafNode*)m_Root)->getData(0);
clear();
return;
}
else
{
CNode *pChild1 = ((CInternalNode*)m_Root)->getChild(0);
CNode *pChild2 = ((CInternalNode*)m_Root)->getChild(1);
if (pChild1->getKeyNum()==MINNUM_KEY && pChild2->getKeyNum()==MINNUM_KEY)
{
pChild1->mergeChild(m_Root, pChild2, 0);
delete m_Root;
m_Root = pChild1;
}
}
}
recursive_remove(m_Root, key, dataValue);
}
void CBPlusTree::recursive_remove(CNode* parentNode, KeyType key, DataType& dataValue)
{
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (parentNode->getType()==LEAF)// 找到目標葉子節點
{
if (key==m_MaxKey&&keyIndex>0)
{
m_MaxKey = parentNode->getKeyValue(keyIndex-1);
}
dataValue = ((CLeafNode*)parentNode)->getData(keyIndex);
parentNode->removeKey(keyIndex, childIndex); // 直接刪除
// 如果鍵值在內部結點中存在，也要相應的替換內部結點
if (childIndex==0 && m_Root->getType()!=LEAF && parentNode!=m_DataHead)
{
changeKey(m_Root, key, parentNode->getKeyValue(0));
}
}
else // 內結點
{
CNode *pChildNode = ((CInternalNode*)parentNode)->getChild(childIndex); //包含key的子樹根節點
if (pChildNode->getKeyNum()==MINNUM_KEY) // 包含關鍵字達到下限值，進行相關操作
{
CNode *pLeft = childIndex>0 ? ((CInternalNode*)parentNode)->getChild(childIndex-1) : NULL; //左兄弟節點
CNode *pRight = childIndex<parentNode->getKeyNum() ? ((CInternalNode*)parentNode)->getChild(childIndex+1) : NULL;//右兄弟節點
// 先考慮從兄弟結點中借
if (pLeft && pLeft->getKeyNum()>MINNUM_KEY)// 左兄弟結點可借
{
pChildNode->borrowFrom(pLeft, parentNode, childIndex-1, LEFT);
}
else if (pRight && pRight->getKeyNum()>MINNUM_KEY)//右兄弟結點可借
{
pChildNode->borrowFrom(pRight, parentNode, childIndex, RIGHT);
}
//左右兄弟節點都不可借，考慮合並
else if (pLeft) //與左兄弟合並
{
pLeft->mergeChild(parentNode, pChildNode, childIndex-1);
pChildNode = pLeft;
}
else if (pRight) //與右兄弟合並
{
pChildNode->mergeChild(parentNode, pRight, childIndex);
}
}
recursive_remove(pChildNode, key, dataValue);
}
}
vector<DataType> CBPlusTree::select(KeyType compareKey, int compareOpeartor)
{
vector<DataType> results;
if (m_Root!=NULL)
{
if (compareKey>m_MaxKey) // 比較鍵值大於B+樹中最大的鍵值
{
if (compareOpeartor==LE || compareOpeartor==LT)
{
for(CLeafNode* itr = m_DataHead; itr!=NULL; itr= itr->getRightSibling())
{
for (int i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
}
}
}
else if (compareKey<m_DataHead->getKeyValue(0)) // 比較鍵值小於B+樹中最小的鍵值
{
if (compareOpeartor==BE || compareOpeartor==BT)
{
for(CLeafNode* itr = m_DataHead; itr!=NULL; itr= itr->getRightSibling())
{
for (int i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
}
}
}
else // 比較鍵值在B+樹中
{
SelectResult result;
search(compareKey, result);
switch(compareOpeartor)
{
case LT:
case LE:
{
CLeafNode* itr = m_DataHead;
int i;
while (itr!=result.targetNode)
{
for (i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
}
for (i=0; i<result.keyIndex; ++i)
{
results.push_back(itr->getData(i));
}
if (itr->getKeyValue(i)<compareKey ||
(compareOpeartor==LE && compareKey==itr->getKeyValue(i)))
{
results.push_back(itr->getData(i));
}
}
break;
case EQ:
{
if (result.targetNode->getKeyValue(result.keyIndex)==compareKey)
{
results.push_back(result.targetNode->getData(result.keyIndex));
}
}
break;
case BE:
case BT:
{
CLeafNode* itr = result.targetNode;
if (compareKey<itr->getKeyValue(result.keyIndex) ||
(compareOpeartor==BE && compareKey==itr->getKeyValue(result.keyIndex))
)
{
results.push_back(itr->getData(result.keyIndex));
}
int i;
for (i=result.keyIndex+1; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
while (itr!=NULL)
{
for (i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
}
}
break;
default: // 范圍查詢
break;
}
}
}
sort<vector<DataType>::iterator>(results.begin(), results.end());
return results;
}
vector<DataType> CBPlusTree::select(KeyType smallKey, KeyType largeKey)
{
vector<DataType> results;
if (smallKey<=largeKey)
{
SelectResult start, end;
search(smallKey, start);
search(largeKey, end);
CLeafNode* itr = start.targetNode;
int i = start.keyIndex;
if (itr->getKeyValue(i)<smallKey)
{
++i;
}
if (end.targetNode->getKeyValue(end.keyIndex)>largeKey)
{
--end.keyIndex;
}
while (itr!=end.targetNode)
{
for (; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
i = 0;
}
for (; i<=end.keyIndex; ++i)
{
results.push_back(itr->getData(i));
}
}
sort<vector<DataType>::iterator>(results.begin(), results.end());
return results;
}
void CBPlusTree::search(KeyType key, SelectResult& result)
{
recursive_search(m_Root, key, result);
}
void CBPlusTree::recursive_search(CNode* pNode, KeyType key, SelectResult& result)
{
int keyIndex = pNode->getKeyIndex(key);
int childIndex = pNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (pNode->getType()==LEAF)
{
result.keyIndex = keyIndex;
result.targetNode = (CLeafNode*)pNode;
return;
}
else
{
return recursive_search(((CInternalNode*)pNode)->getChild(childIndex), key, result);
}
}
#include "BPlus_tree.h"
#include <iostream>
#include <algorithm>
using namespace std;
CBPlusTree::CBPlusTree(){
m_Root = NULL;
m_DataHead = NULL;
}
CBPlusTree::~CBPlusTree(){
clear();
}
bool CBPlusTree::insert(KeyType key, const DataType& data){
// 是否已經存在
if (search(key))
{
return false;
}
// 找到可以插入的葉子結點，否則創建新的葉子結點
if(m_Root==NULL)
{
m_Root = new CLeafNode();
m_DataHead = (CLeafNode*)m_Root;
m_MaxKey = key;
}
if (m_Root->getKeyNum()>=MAXNUM_KEY) // 根結點已滿，分裂
{
CInternalNode* newNode = new CInternalNode(); //創建新的根節點
newNode->setChild(0, m_Root);
m_Root->split(newNode, 0); // 葉子結點分裂
m_Root = newNode; //更新根節點指針
}
if (key>m_MaxKey) // 更新最大鍵值
{
m_MaxKey = key;
}
recursive_insert(m_Root, key, data);
return true;
}
void CBPlusTree::recursive_insert(CNode* parentNode, KeyType key, const DataType& data)
{
if (parentNode->getType()==LEAF) // 葉子結點，直接插入
{
((CLeafNode*)parentNode)->insert(key, data);
}
else
{
// 找到子結點
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
CNode* childNode = ((CInternalNode*)parentNode)->getChild(childIndex);
if (childNode->getKeyNum()>=MAXNUM_LEAF) // 子結點已滿，需進行分裂
{
childNode->split(parentNode, childIndex);
if (parentNode->getKeyValue(childIndex)<=key) // 確定目標子結點
{
childNode = ((CInternalNode*)parentNode)->getChild(childIndex+1);
}
}
recursive_insert(childNode, key, data);
}
}
void CBPlusTree::clear()
{
if (m_Root!=NULL)
{
m_Root->clear();
delete m_Root;
m_Root = NULL;
m_DataHead = NULL;
}
}
bool CBPlusTree::search(KeyType key)
{
return recursive_search(m_Root, key);
}
bool CBPlusTree::recursive_search(CNode *pNode, KeyType key)const
{
if (pNode==NULL) //檢測節點指針是否為空，或該節點是否為葉子節點
{
return false;
}
else
{
int keyIndex = pNode->getKeyIndex(key);
int childIndex = pNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (keyIndex<pNode->getKeyNum() && key==pNode->getKeyValue(keyIndex))
{
return true;
}
else
{
if (pNode->getType()==LEAF) //檢查該節點是否為葉子節點
{
return false;
}
else
{
return recursive_search(((CInternalNode*)pNode)->getChild(childIndex), key);
}
}
}
}
void CBPlusTree::print()const
{
printInConcavo(m_Root, 10);
}
void CBPlusTree::printInConcavo(CNode *pNode, int count) const{
if (pNode!=NULL)
{
int i, j;
for (i=0; i<pNode->getKeyNum(); ++i)
{
if (pNode->getType()!=LEAF)
{
printInConcavo(((CInternalNode*)pNode)->getChild(i), count-2);
}
for (j=count; j>=0; --j)
{
cout<<"-";
}
cout<<pNode->getKeyValue(i)<<endl;
}
if (pNode->getType()!=LEAF)
{
printInConcavo(((CInternalNode*)pNode)->getChild(i), count-2);
}
}
}
void CBPlusTree::printData()const
{
CLeafNode* itr = m_DataHead;
while(itr!=NULL)
{
for (int i=0; i<itr->getKeyNum(); ++i)
{
cout<<itr->getData(i)<<" ";
}
cout<<endl;
itr = itr->getRightSibling();
}
}
bool CBPlusTree::remove(KeyType key)
{
if (!search(key)) //不存在
{
return false;
}
if (m_Root->getKeyNum()==1)//特殊情況處理
{
if (m_Root->getType()==LEAF)
{
clear();
return true;
}
else
{
CNode *pChild1 = ((CInternalNode*)m_Root)->getChild(0);
CNode *pChild2 = ((CInternalNode*)m_Root)->getChild(1);
if (pChild1->getKeyNum()==MINNUM_KEY && pChild2->getKeyNum()==MINNUM_KEY)
{
pChild1->mergeChild(m_Root, pChild2, 0);
delete m_Root;
m_Root = pChild1;
}
}
}
recursive_remove(m_Root, key);
return true;
}
// parentNode中包含的鍵值數>MINNUM_KEY
void CBPlusTree::recursive_remove(CNode* parentNode, KeyType key)
{
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (parentNode->getType()==LEAF)// 找到目標葉子節點
{
if (key==m_MaxKey&&keyIndex>0)
{
m_MaxKey = parentNode->getKeyValue(keyIndex-1);
}
parentNode->removeKey(keyIndex, childIndex); // 直接刪除
// 如果鍵值在內部結點中存在，也要相應的替換內部結點
if (childIndex==0 && m_Root->getType()!=LEAF && parentNode!=m_DataHead)
{
changeKey(m_Root, key, parentNode->getKeyValue(0));
}
}
else // 內結點
{
CNode *pChildNode = ((CInternalNode*)parentNode)->getChild(childIndex); //包含key的子樹根節點
if (pChildNode->getKeyNum()==MINNUM_KEY) // 包含關鍵字達到下限值，進行相關操作
{
CNode *pLeft = childIndex>0 ? ((CInternalNode*)parentNode)->getChild(childIndex-1) : NULL; //左兄弟節點
CNode *pRight = childIndex<parentNode->getKeyNum() ? ((CInternalNode*)parentNode)->getChild(childIndex+1) : NULL;//右兄弟節點
// 先考慮從兄弟結點中借
if (pLeft && pLeft->getKeyNum()>MINNUM_KEY)// 左兄弟結點可借
{
pChildNode->borrowFrom(pLeft, parentNode, childIndex-1, LEFT);
}
else if (pRight && pRight->getKeyNum()>MINNUM_KEY)//右兄弟結點可借
{
pChildNode->borrowFrom(pRight, parentNode, childIndex, RIGHT);
}
//左右兄弟節點都不可借，考慮合並
else if (pLeft) //與左兄弟合並
{
pLeft->mergeChild(parentNode, pChildNode, childIndex-1);
pChildNode = pLeft;
}
else if (pRight) //與右兄弟合並
{
pChildNode->mergeChild(parentNode, pRight, childIndex);
}
}
recursive_remove(pChildNode, key);
}
}
void CBPlusTree::changeKey(CNode *pNode, KeyType oldKey, KeyType newKey)
{
if (pNode!=NULL && pNode->getType()!=LEAF)
{
int keyIndex = pNode->getKeyIndex(oldKey);
if (keyIndex<pNode->getKeyNum() && oldKey==pNode->getKeyValue(keyIndex)) // 找到
{
pNode->setKeyValue(keyIndex, newKey);
}
else // 繼續找
{
changeKey(((CInternalNode*)pNode)->getChild(keyIndex), oldKey, newKey);
}
}
}
bool CBPlusTree::update(KeyType oldKey, KeyType newKey)
{
if (search(newKey)) // 檢查更新後的鍵是否已經存在
{
return false;
}
else
{
int dataValue;
remove(oldKey, dataValue);
if (dataValue==INVALID_INDEX)
{
return false;
}
else
{
return insert(newKey, dataValue);
}
}
}
void CBPlusTree::remove(KeyType key, DataType& dataValue)
{
if (!search(key)) //不存在
{
dataValue = INVALID_INDEX;
return;
}
if (m_Root->getKeyNum()==1)//特殊情況處理
{
if (m_Root->getType()==LEAF)
{
dataValue = ((CLeafNode*)m_Root)->getData(0);
clear();
return;
}
else
{
CNode *pChild1 = ((CInternalNode*)m_Root)->getChild(0);
CNode *pChild2 = ((CInternalNode*)m_Root)->getChild(1);
if (pChild1->getKeyNum()==MINNUM_KEY && pChild2->getKeyNum()==MINNUM_KEY)
{
pChild1->mergeChild(m_Root, pChild2, 0);
delete m_Root;
m_Root = pChild1;
}
}
}
recursive_remove(m_Root, key, dataValue);
}
void CBPlusTree::recursive_remove(CNode* parentNode, KeyType key, DataType& dataValue)
{
int keyIndex = parentNode->getKeyIndex(key);
int childIndex= parentNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (parentNode->getType()==LEAF)// 找到目標葉子節點
{
if (key==m_MaxKey&&keyIndex>0)
{
m_MaxKey = parentNode->getKeyValue(keyIndex-1);
}
dataValue = ((CLeafNode*)parentNode)->getData(keyIndex);
parentNode->removeKey(keyIndex, childIndex); // 直接刪除
// 如果鍵值在內部結點中存在，也要相應的替換內部結點
if (childIndex==0 && m_Root->getType()!=LEAF && parentNode!=m_DataHead)
{
changeKey(m_Root, key, parentNode->getKeyValue(0));
}
}
else // 內結點
{
CNode *pChildNode = ((CInternalNode*)parentNode)->getChild(childIndex); //包含key的子樹根節點
if (pChildNode->getKeyNum()==MINNUM_KEY) // 包含關鍵字達到下限值，進行相關操作
{
CNode *pLeft = childIndex>0 ? ((CInternalNode*)parentNode)->getChild(childIndex-1) : NULL; //左兄弟節點
CNode *pRight = childIndex<parentNode->getKeyNum() ? ((CInternalNode*)parentNode)->getChild(childIndex+1) : NULL;//右兄弟節點
// 先考慮從兄弟結點中借
if (pLeft && pLeft->getKeyNum()>MINNUM_KEY)// 左兄弟結點可借
{
pChildNode->borrowFrom(pLeft, parentNode, childIndex-1, LEFT);
}
else if (pRight && pRight->getKeyNum()>MINNUM_KEY)//右兄弟結點可借
{
pChildNode->borrowFrom(pRight, parentNode, childIndex, RIGHT);
}
//左右兄弟節點都不可借，考慮合並
else if (pLeft) //與左兄弟合並
{
pLeft->mergeChild(parentNode, pChildNode, childIndex-1);
pChildNode = pLeft;
}
else if (pRight) //與右兄弟合並
{
pChildNode->mergeChild(parentNode, pRight, childIndex);
}
}
recursive_remove(pChildNode, key, dataValue);
}
}
vector<DataType> CBPlusTree::select(KeyType compareKey, int compareOpeartor)
{
vector<DataType> results;
if (m_Root!=NULL)
{
if (compareKey>m_MaxKey) // 比較鍵值大於B+樹中最大的鍵值
{
if (compareOpeartor==LE || compareOpeartor==LT)
{
for(CLeafNode* itr = m_DataHead; itr!=NULL; itr= itr->getRightSibling())
{
for (int i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
}
}
}
else if (compareKey<m_DataHead->getKeyValue(0)) // 比較鍵值小於B+樹中最小的鍵值
{
if (compareOpeartor==BE || compareOpeartor==BT)
{
for(CLeafNode* itr = m_DataHead; itr!=NULL; itr= itr->getRightSibling())
{
for (int i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
}
}
}
else // 比較鍵值在B+樹中
{
SelectResult result;
search(compareKey, result);
switch(compareOpeartor)
{
case LT:
case LE:
{
CLeafNode* itr = m_DataHead;
int i;
while (itr!=result.targetNode)
{
for (i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
}
for (i=0; i<result.keyIndex; ++i)
{
results.push_back(itr->getData(i));
}
if (itr->getKeyValue(i)<compareKey ||
(compareOpeartor==LE && compareKey==itr->getKeyValue(i)))
{
results.push_back(itr->getData(i));
}
}
break;
case EQ:
{
if (result.targetNode->getKeyValue(result.keyIndex)==compareKey)
{
results.push_back(result.targetNode->getData(result.keyIndex));
}
}
break;
case BE:
case BT:
{
CLeafNode* itr = result.targetNode;
if (compareKey<itr->getKeyValue(result.keyIndex) ||
(compareOpeartor==BE && compareKey==itr->getKeyValue(result.keyIndex))
)
{
results.push_back(itr->getData(result.keyIndex));
}
int i;
for (i=result.keyIndex+1; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
while (itr!=NULL)
{
for (i=0; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
}
}
break;
default: // 范圍查詢
break;
}
}
}
sort<vector<DataType>::iterator>(results.begin(), results.end());
return results;
}
vector<DataType> CBPlusTree::select(KeyType smallKey, KeyType largeKey)
{
vector<DataType> results;
if (smallKey<=largeKey)
{
SelectResult start, end;
search(smallKey, start);
search(largeKey, end);
CLeafNode* itr = start.targetNode;
int i = start.keyIndex;
if (itr->getKeyValue(i)<smallKey)
{
++i;
}
if (end.targetNode->getKeyValue(end.keyIndex)>largeKey)
{
--end.keyIndex;
}
while (itr!=end.targetNode)
{
for (; i<itr->getKeyNum(); ++i)
{
results.push_back(itr->getData(i));
}
itr = itr->getRightSibling();
i = 0;
}
for (; i<=end.keyIndex; ++i)
{
results.push_back(itr->getData(i));
}
}
sort<vector<DataType>::iterator>(results.begin(), results.end());
return results;
}
void CBPlusTree::search(KeyType key, SelectResult& result)
{
recursive_search(m_Root, key, result);
}
void CBPlusTree::recursive_search(CNode* pNode, KeyType key, SelectResult& result)
{
int keyIndex = pNode->getKeyIndex(key);
int childIndex = pNode->getChildIndex(key, keyIndex); // 孩子結點指針索引
if (pNode->getType()==LEAF)
{
result.keyIndex = keyIndex;
result.targetNode = (CLeafNode*)pNode;
return;
}
else
{
return recursive_search(((CInternalNode*)pNode)->getChild(childIndex), key, result);
}
}
望大家不吝指教！
