B树的简介
B 树是为了磁盘或其它存储设备而设计的一种多叉平衡查找树。与红黑树很相似，但在降低磁盘I/0操作方面要更好一些（树的深度较低）。许多数据库系统都一般使用B树或者B树的各种变形结构。
B树与红黑树最大的不同在于，B树的结点可以有许多子女，从几个到几千个。那为什么又说B树与红黑树很相似呢?因为与红黑树一样，一棵含n个结点的B树的高度也为O（lgn），但可能比一棵红黑树的高度小许多，应为它的分支因子比较大。所以，B树可以在O（logn）时间内，实现各种如插入（insert），删除（delete）等动态集合操作。
如下图所示，即是一棵B树，现在要从树种查找字母R（包含x个关键字的内结点，x+1 个子女。所有的叶结点都处于相同的深度，带阴影的结点为查找字母R时要检查的结点）：
非叶子结点最多子树个数也称为阶数，一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，满足一下性质：
1. 根节点至少有两个孩子
2. 每个非根节点有[M/2 ,M]个孩子;(M/2取上整)
3. 每个非根节点有[ M/2-1,M-1]个关键字，并且以升序排列。(M/2取上整)
4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
5. 所有的叶子节点都在同一层
现在你是不是对B—Tree树有了一个大体的认识了？如果还是一头雾水也没关系，相信看完后面的内容你会对B-Tree有所了解 O(∩_∩)O
OK现在我们一起来实现一下这个 B-Tree ......
该怎样实现这个B树呢，它的节点需要什么属性呢~~这是我们要思考的问题：
首先，节点中得有这个树的阶数（孩子节点的指针最多的个数）吧！好的那咱们定义一个M来做为你这个B树的阶数
然后呢，我们是不是得需要一个保存关键字的数组，和一个保存你需要保存关键字对应的信息的数组。比如说：我需要根据一个人的身证号来获取他的个人信息，这个身份证号就是关键字，个人信息就是我们经过检索想要得到的信息； 好的，我们现在就在节点中建立一个 _keys[M],_values[M] 哎哎.... 有的小伙伴会说一个节点最多有 M-1（阶数-1）个关键字么，你怎么数组长度定义为M 你憋着急。。后面你就知道它的好处了；
还有什么呢？没错应该是你这个节点中真实保存的关键字的数目，来确定是不是超出规定的阶数减一个了；
接下来，节点中是不是有一个指向孩纸节点的指针数组啊！对 那咱们在结构体中定义一个 Node* _subs[M+1]
还有撒子嘞，哦哦咱们还需要一个指向父亲节点的指针，供回溯时使用。 Node* _parent;
一切就绪 Load。。。
template<class K,class V,int M = >
struct BTreeNode
{
typedef BTreeNode<K, V, M> Node;
BTreeNode()
:_size(0), _parent(NULL)
{
for (int i = ; i < M + ; ++i)
{
_subs[i] = NULL;
}
}
K _keys[M]; //关键字数组
V _values[M]; //信息数组
Node* _subs[M + ]; //指向孩子节点的指针数组
size_t _size; //关键字的个数
Node* _parent; //指向父亲点的指针
};
节点创建好之后呢，我们来创建这个B-Tree
template<class K,class V> //实现返回两种类型的变量
struct Pair
{
K _first;
V _second; Pair(const K& key = K(), const V& value = V())
:_first(key), _second(value)
{}
}; template<class K,class V,int M = >
class BTree
{
typedef BTreeNode<K, V, M> Node;
public:
BTree()
:_root(NULL)
{}
public:
Pair<Node*, bool> _Find(const K& key); //查找（返回值是一个指向B-Tree节点的指针，和是否找到 true/false）
bool _Insert(const K& key, const V& value,Node* sub = NULL); //插入
void _Order() { Order(_root); }; //中序遍历
void Order(Node* root); protected:
Node* _root;
};
你没有看错，基本的 B—Tree 结构实现起来就是这麽个样子！现在就让我们来探究一下这背后的玄机....
template<class K, class V, int M = >
Pair<BTreeNode<K,V,M>*, bool> BTree<K, V, M>::_Find(const K& key)
{
Node* parent = NULL;
Node* cur = _root;
if (cur == NULL)
{
return Pair<Node*, bool>(cur, false);
}
else
{
while (cur)
{
int i = ;
for (; (key > cur->_keys[i]) && (i < cur->_size); ++i);
if (key == cur->_keys[i]) //找到相应的值了
{
return Pair<Node*, bool>(cur, true);
}
else
{
parent = cur;
cur = cur->_subs[i];
}
}
return Pair<Node*, bool>(parent, false);
}
} 查找函数到底是一个什么样的机制呢，这幅图能使你更清楚一些：
//B-Tree 的插入函数
template<class K, class V, int M = 3>
bool BTree<K, V, M>::_Insert(const K& key, const V& value,BTreeNode<K, V, M>* sub = NULL)
{
if (_root == NULL) //如果根节点为空
{
_root = new Node;
_root->_keys[] = key;
_root->_values[] = value;
_root->_size++;
}
else //根节点不为空
{
Pair<Node*, bool> exist = _Find(key);
if (exist._second) //如果该关键字已经存在
{
cout << "This Key already exists!" << endl;
return false;
}
else //B树中还没有此关键字，此时应该插入相应信息
{
Node* cur = exist._first;
Node* before = NULL;
Node* tmp = sub;
K middlekey = key;
V middlevalue = value;
while ()
{
//第一次分裂完成之后_keys[middle] 要往父亲节点中插入，
//父亲节点可能为空
if (cur == NULL)
{
Node* parent = new Node();
parent->_keys[] = middlekey;
parent->_values[] = middlevalue;
++parent->_size;
parent->_subs[] = before;
before->_parent = parent;
parent->_subs[] = tmp;
tmp->_parent = parent;
_root = parent;
return true;
}
int index = _BinarySearch<K>(cur->_keys, cur->_size, key);
for (int i = cur->_size; i > index; --i)
{
cur->_keys[i] = cur->_keys[i - ]; //将关键字后移
cur->_values[i] = cur->_values[i - ]; //将关键字对应的有效信息后移
cur->_subs[i + ] = cur->_subs[i]; //指向孩子节点的指针后移
}cur->_keys[index] = middlekey; //移动好之后将相应的数据更新
cur->_values[index] = middlevalue;
cur->_subs[index+] = tmp; //tmp是分裂出来的新节点
if (tmp)
{
tmp->_parent = cur;
}
++cur->_size; if (cur->_size < M) //关键字的个数合法
{
return true;
}
else //关键字的个数非法（M个关键字）
{
int middle = M / ;
int position = ;
int size = cur->_size;
Node* _tmp = new Node(); for (int i = middle + ; i <= cur->_size; ++i) //将右半边分裂出去（_tmp）
{
_tmp->_keys[position] = cur->_keys[i];
_tmp->_values[position] = cur->_values[i];
_tmp->_subs[position] = cur->_subs[i];
--cur->_size;
++_tmp->_size;
}
_tmp->_subs[_tmp->_size] = cur->_subs[size];middlekey = cur->_keys[middle]; //往上插入的关键字
middlevalue = cur->_values[middle];
--cur->_size; before = cur;
cur = cur->_parent;
tmp = _tmp;
}
}
}
}
} //插入的过程图解template<class K>
int _BinarySearch(const K* keys, int size,const K& key)
{
assert(keys);
int low = ;
int high = size - ;
while (low < high)
{
int middle = (high - low) / + low;
key > keys[middle] ? (low = middle + ) : (high = middle - );
}
return (key > keys[low] ? low + : low);
}
//中序遍历
template<class K, class V, int M = >
void BTree<K, V, M>::Order(Node* root)
{
if (root == NULL)
{
return;
}
else
{
for (int i = ; i < root->_size; ++i)
{
Order(root->_subs[i]);
cout << "[" << root->_keys[i] << "]" << " :" << root->_values[i] << endl;
}
Order(root->_subs[root->_size]);
}
}
//测试用例
void Test()
{
BTree<int, string> btree;
btree._Insert(, "数据结构");
btree._Insert(,"Linux");
btree._Insert(,"算法导论");
btree._Insert(,"剑指offer");
btree._Insert(,"c++ Primer");
btree._Insert(,"操作系统");
btree._Insert(, "计算机原理"); /*中序遍历*/
btree._Order();
}
//此为中序遍历的结果
到这里呢，这个B-Tree的构建就基本完成了，如果小伙伴们还有什么更好的方法，或者说是对这篇博文有什么意见或者建议什么的欢迎参与评论，跪求赐教~~