B-树 实现 插入，遍历，查找
B-树适用于：当文件很大时，索引表（树表）本身也在外存，则查找索引时需多次访问外存，并且，访问外存的次数恰为查找路径上的结点数。为减少访问外存的次数，应尽量缩减索引表的深度。此时宜采用m叉的B-树作索引表。m的选择取决于索引项的多少和缓冲区的大小。
定义结构体与B-tree类
- 结构体BTNode：定义B-tree中每个节点
- 构造体Result：定义查找B-tree操作：BTree::SearchBTree(KeyType K)的返回值(K所在的节点，所在的关键字位置，是否查找成功 - 不成功是会之后会进行插入)
- 类BTree：定义：查找操作，插入操作，遍历操作
#include <iostream>
using namespace std;
typedef int KeyType;
#define M 3
typedef struct BTNode{
int keynum;
struct BTNode *parent;
KeyType key[M + 1];
struct BTNode *ptr[M + 1];
}BTNode;
typedef struct Result{
BTNode *pt; // 指向查找到的结点。
int i; // 1..m,结点中的关键字标号
int tag; // 1：查找成功。 0：查找失败
}Result; // B-树查找结果类型
class BTree{
public:
BTree();
~BTree();
Result SearchBTree(KeyType k);
void Insert(BTNode *p, int i, KeyType x, BTNode *ap);
void split(BTNode *q, int s, BTNode **ap);
void NewRoot(BTNode *q, KeyType x, BTNode *ap);
int InsertBTree(KeyType K, Result rs, int i);
int ShowBTNode(BTNode *p);
int TraverseBTree(BTNode *p);
BTNode * GetRoot();
private:
BTNode *m_root; // 记录根节点
};
// 构造函数
BTree::BTree()
{
m_root = NULL; // 初始化
}
BTree::~BTree()
{
delete m_root;
}
// NewRoot(m_root, x, ap); m_root：根节点，ap：分裂后的新复制的节点
void BTree::NewRoot(BTNode *q, KeyType x, BTNode *ap) // 创建一个新的根
{
m_root = new BTNode;
m_root->keynum = 1;
m_root->key[1] = x;
m_root->ptr[1] = ap;
m_root->parent = NULL;
m_root->ptr[0] = q;
if(q != NULL) // 这个地方的存在是为了一致性使用，第一次插入时会创建根，但还没有q和ap
{
q->parent = m_root;
}
if(ap != NULL)
{
ap->parent = m_root;
}
}
BTNode * BTree::GetRoot()
{
return m_root;
}
从根节点开始查找K，要么找到，要么指向最底层的非终端节点中要插入的位置
- Search(BTNode *p, KeyType K)：对p节点中的关键字进行查找
- BTree::SearchBTree(KeyType K)：从整个树中查找，会不断的遍历相应的节点。从根节点开始查找K，要么找到，要么指向最底层的非终端节点要插入的位置
int Search(BTNode *p, KeyType K) // 查找K应该在p节点中所在的位置
{
int i;
for(i = 1; i <= p->keynum; ++i)
{
if(p->key[i] <= K)
{
if(i == p->keynum) // 找到K所在的节点
{
return i;
}
else if(p->key[i + 1] > K) // 这个节点当前关键字小于K，下一个关键字大于K
{
return i;
}
}else // p->key[i] > K
{
return 0;
}
}
return i;
}
Result BTree::SearchBTree(KeyType K) // 从根节点开始查找K，要么找到，要么指向最底层的非终端节点要插入的位置
{
BTNode *p = m_root;
BTNode *q = NULL;
bool found = false;
int i = 0;
while((p != NULL) && !found)
{
i = Search(p, K); // 调用Search函数
if((i > 0) && (p->key[i] == K)) // 在这个节点中找到K
{
found = true;
}else // 继续往加一个节点查找
{
q = p; p = p->ptr[i];
}
} // 退出时，要么找见了，要么p到null 即 q指向要K插入的节点
if(found) return Result{p, i, 1};
else return Result{q, i, 0};
}
将值插入到对应的节点的对应的位置 以及 分裂操作
- BTree::Insert(BTNode *p, int i, KeyType x, BTNode *ap)：将值进行插入到其应该在的节点中正确的关键字位置
- BTree::split(BTNode *q, int s, BTNode **ap)：分裂的方法是—生成一新结点，从中间位置把结点（不包括中间位置的关键字）分裂成两部分。前半部分留在旧结点中，后半部分复制到新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。
注意两个函数中都有为了代码一致性加入的代码，详细看对应的代码注释
// Insert(p, i, x, ap); p:指向查找到的结点，i:1..m,结点中的关键字标号
// x为关键字的值
void BTree::Insert(BTNode *p, int i, KeyType x, BTNode *ap) // 将K插入到对应的节点的对应的位置
{
int j = p->keynum;
for(;j >= i + 1; --j)
{
p->key[j + 1] = p->key[j];
p->ptr[j + 1] = p->ptr[j];
}
p->key[i + 1] = x;
p->ptr[i + 1] = ap; // 这个地方的存在是为了一致性使用，因为最底层的非终端和其他非终端节点ap值不同
// 终端ap为NULL，非终端ap为分裂时新复制的节点
p->keynum++;
}
// 分裂的方法是：生成一新结点，从中间位置把结点（不包括中间位置的关键字）分裂成两部分。前半部分留在旧结点中，
// 后半部分复制到新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。
// split(q, s, &ap); q:指向查找到的结点 s:为中间节点对应的位置索引
void BTree::split(BTNode *q, int s, BTNode **ap) // ap为新复制的节点
{
int i;
*ap = new BTNode;
(*ap)->parent = q->parent;
(*ap)->keynum = M - s;
(*ap)->ptr[0] = q->ptr[s];
for(i = 1; i <= M - s; ++i)
{
(*ap)->key[i] = q->key[s + i];
(*ap)->ptr[i] = q->ptr[s + i];
if(q->ptr[s + i] != NULL) // 这个地方的存在是为了一致性使用，因为最底层的非终端节点和其他非终端节点q->ptr[s + i]不一样
{
q->ptr[s + i]->parent = (*ap);
}
}
q->keynum = s - 1;
}
定义总的插入操作
包含了：将对应的插入值放到对应的节点中对应的关键字位置 以及 对不满足条件的节点进行分裂
// 先插入到某个最底层的非终端结点上，然后再进行分裂
// 分裂的方法是：生成一新结点，从中间位置把结点（不包括中间位置的关键字）分裂成两部分。前半部分留在旧结点中，
// 后半部分复制到新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。
int BTree::InsertBTree(KeyType K, Result rs, int i) // q指向查找到的结点，i:1..m,结点中的关键字标号
{
if(rs.tag == 1) return 1; // 之前查找到了K，就不用再插入
BTNode *q = rs.pt;
KeyType x = K;
BTNode *ap = NULL; // ap为分裂时新复制的节点
bool finished = false;
while((q != NULL) && !finished)
{
Insert(q, i, x, ap); // 在q节点中i关键字位置插入值x
if(q->keynum < M) // 判断这个节点的关键字个数是否满足
{
finished = true;
}else // 不满足时分裂
{
int s = M / 2 + 1; // 找到中间节点，之后要上升到父节点
split(q, s, &ap); // ap为分裂时新复制的节点
// 准备对中间位置关键字插入父节点
x = q->key[s]; // 向父节点插入的值x
q = q->parent; // q不断指向父节点
if(q != NULL)
{
i = Search(q, x); // 查找K应该在q节点中所在的位置
}
}
}
if(!finished) // q==NULL说明此时根节点已经分裂，需要创建新的根；或者第一次插入时创建根
{
NewRoot(m_root, x, ap);
}
return 1;
}
定义如何进行展示B-tree
int BTree::ShowBTNode(BTNode *p)
{
int i = 1;
for(; i <= p->keynum; ++i)
{
cout << i << ":" << p->key[i] << "| ";
}
cout << endl;
return 1;
}
int BTree::TraverseBTree(BTNode *p)
{
int i;
if(p != NULL)
{
ShowBTNode(p); // 对这个节点关键字输出
for(i = 0; i <= p->keynum; ++i)
{
TraverseBTree(p->ptr[i]); // 递归遍历所有子节点
}
}
return 1;
}
主函数
// 不要将终端节点误认为是最底层非终端点。
int main()
{
BTree bt;
Result rs;
rs = bt.SearchBTree(45); // 从根节点开始查找K，要么找到，要么指向最底层的非终端节点要插入的位置,如果节点存在就不用插入
bt.InsertBTree(45, rs, rs.i);
rs = bt.SearchBTree(24);
bt.InsertBTree(24, rs, rs.i);
rs = bt.SearchBTree(53);
bt.InsertBTree(53, rs, rs.i);
rs = bt.SearchBTree(90);
bt.InsertBTree(90, rs, rs.i);
rs = bt.SearchBTree(3);
bt.InsertBTree(3, rs, rs.i);
rs = bt.SearchBTree(12);
bt.InsertBTree(12, rs, rs.i);
rs = bt.SearchBTree(37);
bt.InsertBTree(37, rs, rs.i);
rs = bt.SearchBTree(50);
bt.InsertBTree(50, rs, rs.i);
rs = bt.SearchBTree(61);
bt.InsertBTree(61, rs, rs.i);
rs = bt.SearchBTree(70);
bt.InsertBTree(70, rs, rs.i);
rs = bt.SearchBTree(100);
bt.InsertBTree(100, rs, rs.i);
bt.TraverseBTree(bt.GetRoot());
}
阅读代码时请注意代码注释中加入的"为了一致性使用"这些代码段，因为这些代码段设计的十分巧妙
可以自己定义遍历的形式，只需要修改对应的函数即可
运行结果为：