本篇博文旨在介绍一种适合外查找的树---B树，以及B树的延伸B+树；比较了B树和B+树的各自优缺点；说明了B树B+树的应用场景；以及实现了B树的代码
B树
B树的概念和性质
B树是一种适合外查询的树，它是一种多叉平衡树
除此之外，它还满足如下的性质：
（1）根节点有至少两个孩子
（2）非根节点的孩子数量在【M/2,M】之间
（3）每个节点的key值的数量在【(M/2) - 1,M-1】之间，关键字并按照升序排序
（4）所有的叶子节点均在同一层
（5）key[i],key[i+1]，这两个关键值之间的孩子的值在key[i]到key[i+1]之间
一颗M=3的B树
B树节点的定义
//定义B树的节点
template<typename K,typename V,size_t M = 3>
struct BTreeNode
{
pair<K,V> _kv[M];
BTreeNode<K,V> *_subs[M+1];
BTreeNode<K,V> *_parent;
//表示存储了多少个Key值
size_t _size;
//节点的构造函数
BTreeNode()
:_size(0),_parent(NULL)
{
for (size_t i = 0; i <= M; ++i)
{
_subs[i] = NULL;
}
}
};
我们按照B树的概念及其性质定义了如上的节点类
B树如何查找一个key值
//查找函数，其返回值的设计实现了Insert的复用 pair<Node*,int> Find(const K& key) { //若查询不到，则用parent记录需要插入的节点的父节点 //实现了Insert的复用 Node* cur = _root; Node* parent = NULL; while (cur) { size_t index = 0; while (index < cur->_size) { if (key > cur->_kv[index].first) { index++; } else if (key == cur->_kv[index].first) { //查询到，返回查询的节点 return make_pair(cur,index); } else { break; } } parent = cur; cur = cur->_subs[index]; } //没有查询到,返回需要插入节点的父亲节点 //实现了Insert函数的复用 return make_pair(parent,-1); }这里和搜索树的方式相同，只是由于定义的不同而实现的略有区别而已，概念都是一样的
这里使用了pair，pair是一个结构体类型，返回值返回的是节点的指针以及查找成功与否的bool
B树的插入方法
插入的时候可能遇到以下情况：
（1）B树为空
创造新节点，并给根赋值
（2）插入的时候，B树已经存在了该Key值
根据find返回值pair结构体的第二个参数，可以判断原B树是否存在对应的Key值
若存在，则插入失败；
否则再插入
（3）插入一个节点后，该节点未满
插入完成，直接返回TRUE
（4）插入一个节点后，该节点的关键值满了，需要分裂
分裂方法：
将该节点的右半区间移到一个新的节点中（移动时也要把孩子移过去）
生成节点后，还要注意之前有没有父亲节点；
若没有，就需要将中间的元素提到新的根节点；
（5）分裂时，若分裂的节点有父亲节点
这种情况可能继续调整，因为之前分裂会将一个key值给父亲节点
父亲节点的key值数量+1，也就有可能满了
上面的情况是分裂节点为空的情况，不用继续调整，就可结束
代码中有对所有情况的分析和注释
bool Insert(const pair<K,V>& kv)
{
//情况1.当根节点为空的时候，需要对_root进行赋值
if (_root == NULL)
{
_root = new Node;
_root->_size = 1;
_root->_kv[0] = kv;
return true;
}
//情况2.不为空，则找到插入的位置
//如果second的值不为-1，则表示已经存在，不需要插入
pair<Node*,int> ret = Find(kv.first);
if (ret.second != -1)
return false;
//进行插入
Node* cur = ret.first;
Node* temp = cur;
pair<K,V> newKV = kv;
Node* sub = NULL;
while (1)
{
//在cur节点插入kv和sub
_Insert(cur,newKV,sub);
//情况3.如果cur没满，则表示插入成功
//否则需要进行分裂
if (cur->_size < M)
return true;
//情况4.构造一个新节点tmp
Node* tmp = new Node;
size_t mid = M >> 1;
size_t i = mid+1;
size_t j = 0;
//将右半区间的元素移到tmp中
while (i < cur->_size)
{
tmp->_kv[j] = cur->_kv[i];
cur->_kv[i] = pair<K,V>();
tmp->_subs[j] = cur->_subs[i];
if (cur->_subs[i])
cur->_subs[i]->_parent = tmp;
//调整
i++;
j++;
tmp->_size++;
cur->_size--;
}
//拷走最后一个右孩子
tmp->_subs[j] = cur->_subs[i];
cur->_subs[i] = NULL;
if (cur->_subs[i])
cur->_subs[i]->_parent = tmp;
//情况5.如果cur没有父亲节点，需要创建
//如果cur有父亲节点，那么需要将中间元素插入到父亲节点里
if (cur->_parent)
{
//继续向上调整，判别是否parent会满
newKV = cur->_kv[mid];
sub = tmp;
cur->_size--;
cur = cur->_parent;
}
else
{
//定义一个新根节点，将中间元素放入该节点中
Node* newRoot = new Node;
newRoot->_kv[0] = cur->_kv[mid];
newRoot->_size = 1;
//设置新根节点的两个孩子cur和tmp
//并修改他们的父亲节点
newRoot->_subs[0] = cur;
cur->_parent = newRoot;
newRoot->_subs[1] = tmp;
tmp->_parent = newRoot;
cur->_size--;
//将根节点重新赋值
_root = newRoot;
return true;
}
}
}
B树的代码实现
#pragma once
#include<iostream>
using namespace std;
/*
* author:haohaosong
* date:2017/2/23
* note:B树的实现
*/
//B树的增删查改的时间复杂度 O(logM(N))
//定义B树的节点
template<typename K,_parent(NULL)
{
for (size_t i = 0; i <= M; ++i)
{
_subs[i] = NULL;
}
}
};
//B树的定义
template<typename K,size_t M = 3>
class BTree
{
typedef BTreeNode<K,V> Node;
public:
//构造函数
BTree()
:_root(NULL)
{}
//查找函数，其返回值的设计实现了Insert的复用
pair<Node*,-1);
}
bool Insert(const pair<K,V>& kv)
{
//当根节点为空的时候，需要对_root进行赋值
if (_root == NULL)
{
_root = new Node;
_root->_size = 1;
_root->_kv[0] = kv;
return true;
}
//不为空，则找到插入的位置
//如果second的值不为-1，则表示已经存在，不需要插入
pair<Node*,sub);
//如果cur没满，则表示插入成功
//否则需要进行分裂
if (cur->_size < M)
return true;
//构造一个新节点tmp
Node* tmp = new Node;
size_t mid = M >> 1;
size_t i = mid+1;
size_t j = 0;
//将右半区间的元素移到tmp中
while (i < cur->_size)
{
tmp->_kv[j] = cur->_kv[i];
cur->_kv[i] = pair<K,V>();
tmp->_subs[j] = cur->_subs[i];
if (cur->_subs[i])
cur->_subs[i]->_parent = tmp;
//调整
i++;
j++;
tmp->_size++;
cur->_size--;
}
//拷走最后一个右孩子
tmp->_subs[j] = cur->_subs[i];
cur->_subs[i] = NULL;
if (cur->_subs[i])
cur->_subs[i]->_parent = tmp;
//如果cur没有父亲节点，需要创建
//如果cur有父亲节点，那么需要将中间元素插入到父亲节点里
if (cur->_parent)
{
//继续向上调整，判别是否parent会满
newKV = cur->_kv[mid];
sub = tmp;
cur->_size--;
cur = cur->_parent;
}
else
{
//定义一个新根节点，将中间元素放入该节点中
Node* newRoot = new Node;
newRoot->_kv[0] = cur->_kv[mid];
newRoot->_size = 1;
//设置新根节点的两个孩子cur和tmp
//并修改他们的父亲节点
newRoot->_subs[0] = cur;
cur->_parent = newRoot;
newRoot->_subs[1] = tmp;
tmp->_parent = newRoot;
cur->_size--;
//将根节点重新赋值
_root = newRoot;
return true;
}
}
}
//中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
protected:
void _Insert(Node* cur,const pair<K,V>& newKV,Node* sub)
{
//这里要用int，不能用size_t，会影响while循环的判断条件
int index = (cur->_size)-1;
while (index >= 0)
{
//找到合适的插入位置，跳出
if (newKV.first > cur->_kv[index].first)
break;
//将key值向后移动，并且将孩子也移动
cur->_kv[index + 1] = cur->_kv[index];
cur->_subs[index + 2] = cur->_subs[index + 1];
index--;
}
//插入新的KV以及孩子
cur->_kv[index+1] = newKV;
cur->_subs[index+2] = sub;
//孩子存在，给其父亲赋值
if (sub)
sub->_parent = cur;
cur->_size++;
}
//中序遍历递归函数
void _InOrder(Node* root)
{
if (root == NULL)
return;
//访问每一个key值及其左孩子
size_t index = 0;
while (index < root->_size)
{
_InOrder(root->_subs[index]);
cout << root->_kv[index].first<<" ";
index++;
}
//打印最后一个key值的右孩子
_InOrder(root->_subs[root->_size]);
}
protected:
Node* _root;
};
void TestBtree()
{
BTree<int,int> t;
int a[] = { 53,75,139,49,145,36,101 };
for (size_t i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
t.Insert(make_pair(a[i],i));
t.InOrder();
}
t.InOrder();
}
B+树
B树的特点
B+树是B树的一种变形树，它的基本特性和B树一致
只是有下列区别：
（1）每个节点的key值和子节点的个数对应
（2）非叶子节点只是起到索引的作用，只有叶子节点内部存储数据
（3）所有的叶子节点由一个链表串起来，并且是有序的，可以根据关键值的次序遍历全部记录
B树和B+树的对比
B树的优点：
和B+树相比，每一个节点都有key和对应的value，如果访问的元素离根节点较近，则访问很迅速
B+树的优点：
（1）叶子节点是用链表串起来的，遍历一遍的速度很快；相反如果采用B树，则需要遍历整颗树
（2）B+树的数据是顺序排列的，并且是相连的所以在区间内查找时（比如查找成绩在70~80分之间的学生），B+树很方便就可以办到
而如果采用B树，B树要对每一层递归的进行遍历，效率低；
（3）空间局部性高，缓存命中率高
B树和B+树的主要应用：
一些主流的数据库，如MysqL，Oracle对B数，B+树都有运用
当然是进行优化过后的
