BTree的插入和查找算法分析

本文主要是介绍BTree的插入和查找算法分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.什么叫BTree？

一种适合外查找的树，它是一种平衡的多叉树，称为B树（或写成B-树，但是不能误读为“B减树”）。

2.BTree的性质

一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1. 根节点至少有两个孩子（孩子为NULL也算作孩子的数量）

2. 每个非根节点有[M/2,M]个孩子（注意孩子与关键字的关系，n个key，n+1孩子）

3. 每个非根节点有[M/2 - 1,M - 1]个关键字，并且以升序排列(这样才能进行查找)

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间

5. 所有的叶子节点都在同一层（整棵树的高度一致）

3.BTree结点的定义

template<class K,class V,size_t M>
//非类型的模板参数在推演时变成常量
//M阶树的孩子个数为	[M/2,M]		个孩子
//M阶树的关键字个数为	[M/2-1,M-1]	个关键字,且为升序排列
struct BTreeNode
{//将数组的大小预留出一位是为了便于分裂pair<K, V> _kvs[M];					//kvs数组,存放kvBTreeNode<K, V, M>* _parent;		   //指向父结点的指针，便于分裂BTreeNode<K, V, M>* _subs[M + 1];	  //指向孩子结点的指针数组size_t _size;				         //kvs数量,有效数据个数BTreeNode():_parent(NULL), _size(0){for (size_t i = 0; i < M + 1; i++){_subs[i] = NULL;}}
};

4.BTree查找算法的实现

注：本来Find的返回值应该设置为bool类型，但是为了后面的插入算法实现代码的复用，返回一个pair<Node*，int>

即Node*代表该结点位置是用来插入kv的，int代表的是该位置的下标，由于没有实现multi版本，所以不允许出现重复的数据，所以当出现相同的key值时，返回make_pair(NULL,-1)。当key大于_kvs[index].first（即kvs数组的key值）,应该接着往后找，直到key小于为止（如果是这种情况去_subs[index]即_kvs[index]的左孩子去找，比如图中的35）或者找不到key小于_kvs[index].first(即kvs数组的最后一个有效数据，比如图中的55)，那么就应该去它最后一个位置的右孩子去找。

注：代码实现

pair<Node* ,int>  Find(const K& key){Node* cur = _root;Node* parent = NULL;size_t index = 0;while (cur != NULL){index = 0;while (index < cur->_size){if (cur->_kvs[index].first == key){return make_pair(cur, -1);}else if (cur->_kvs[index].first > key){break;}else{++index;}}parent = cur;cur = cur->_subs[index];}//BTree并不需要在空位置插入，一个结点可以有多个关键字//当这个结点的孩子为空，没找到关键字时，就可以插入了return make_pair(parent, index);}

5.插入算法的实现

（1）首先判断树是否为空，为空新建一个结点，将pair<K,V>插入到kvs[0]中，记住把_root->_size++;

（2）首先通过Find函数找到你的数据该插入的结点的位置;

（3）在将pair<K,V>插入到当前的kvs数组，由于数组多预留了一个空间所以不会产生越界问题,每次插入数据之后记得把cur->_size++;

（4）判断当前的kvs数组的kv数量是否小于M，小于M证明当前数组插入数据之后是安全的，没有问题; 如果等于M需要进行分裂操作,将cur置成cue->parent.....重复(2)(3)(4),只不过第二部不需要通过Find函数了，中间还有许多细节问题，将会通过一个图例来说明！！！

	bool Insert(const pair<K, V> & kv){if (_root == NULL){_root = new Node();_root->_kvs[0] = kv;_root->_subs[0] = NULL;_root->_subs[1] = NULL;_root->_size++;}pair<Node*, int> ret = this->Find(kv.first);if (ret.second == -1)return false;//要插入位置的结点Node* cur = ret.first;Node* parent = cur->_parent;Node* sub = NULL;pair<K, V> newKV = kv;while (1){this->InsertKV(cur, newKV, sub);if (cur->_size < M){return true;}//走到这里表示结点存放的kv已经满了,需要分裂Node* brother = new Node();int mid = M / 2;int i = mid + 1;int j = 0;//将中间结点之后的数据复制给兄弟结点for (; i < M; i++){brother->_kvs[j] = cur->_kvs[i];brother->_size++;cur->_size--;if (cur->_subs[i] != NULL){cur->_subs[i]->_parent = brother;brother->_subs[j] = cur->_subs[i];cur->_subs[i] = NULL;}j++;}if (cur->_subs[i] != NULL)cur->_subs[i]->_parent = brother;brother->_subs[j] = cur->_subs[i];cur->_subs[i] = NULL;//如果已经到根结点if (parent == NULL){Node* root = new Node();root->_kvs[0] = cur->_kvs[mid];root->_subs[0] = cur;cur->_parent = root;cur->_size--;root->_subs[1] = brother;brother->_parent = root;_root = root;_root->_size++;return true;}//将中间结点上移newKV = cur->_kvs[mid];cur->_size--;cur = parent;parent = cur->_parent;sub = brother;}}void InsertKV(Node* cur,const pair<K, V>& kv,Node* sub){size_t index = 0;for (; index < cur->_size; index++){if (kv.first < cur->_kvs[index].first)break;}for (size_t i = cur->_size ; i > index; i--){cur->_kvs[i] = cur->_kvs[i - 1];cur->_subs[i + 1] = cur->_subs[i];}cur->_kvs[index] = kv;cur->_subs[index + 1] = sub;if (sub != NULL){sub->_parent = cur;}cur->_size++;return;}

6.中序遍历的实现

void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == NULL)return;size_t i = 0;for (; i < root->_size; i++){_InOrder(root->_subs[i]);cout << root->_kvs[i].first << " ：" << root->_kvs[i].second << endl;}_InOrder(root->_subs[i]);}