B树

2015-08-07 20:50:29   最后更新: 2015-08-07 20:50:29   访问数量:881




B树是为磁盘或其他直接辅助互存储设备而设计的一种平衡查找树,可以有效降低磁盘IO操作次数

B树的分支因子可能很大,即一个节点可能有几个甚至几千个子女,因此B树的高度就会很小

下图给出一个简单的B树,如果B树内结点 x 包含 n 个关键字,则 x 有 n+1 个子女。x中的关键字是用来将x所处理的关键字域划分成 n+1 个子域的分割点,每个子域都由x中的一个子女来处理。叶结点的结构不同于内结点的结构

 

 

众所周知,磁盘的读写速度与内存相比是非常慢的,并且由于磁盘的数据量过大,是不可能装入主存的,因此使用分页机制,只将所需要的页读取出来装入主存进行处理,因此,B树就是通过尽量少的比较次数快速定位磁盘的分页位置的数据结构

B树中,一个节点的大小通常相当于一个完整的磁盘页,因此,一个B树结点可以拥有的子女数就由分页的大小决定

对储存在磁盘上的一棵大的B树,通常采用的分支因子为50到2000,具体要取决于一个关键字相对于一页的大小。大的分支因子可以大大降低树的高度,因为根节点可以持久的保存在主存中,因此在下面这棵树中 ,寻找一个关键字将最多只需两次磁盘存取

 

 

一棵B树T是具有如下性质的有根树(根为root):

 

1、每个结点x有以下域:

  • n,当前存储在节点x中的关键字数
  • n个关键字本身,以非降序存放
  • isleaf,布尔值,只有当该节点为叶子节点时为TRUE

2、每个内结点x还包含n+1个指向其子女的指针

3、各个关键字key[i]对储存在各子树中的关键字范围加以分隔

4、每个叶结点具有相同的深度,即树的高度h

5、每一个节点能包含的关键字数有一个上界和下界,这些界可用一个称作B树的最小度数的固定整数t>=2来表示

  • 每个非根节点必须至少有 t-1 个关键字,每个非根的内结点至少有 t 个子女,如果属实非空的,则根节点至少包含一个关键字
  • 每个节点可以包含至多 2t-1 个关键字,所以每一个内结点至多有 2t 个子女,如果一个节点恰好有 2t-1 个关键字,我们就说一个结点是满的

 

当 t=2 时,B树的结构是最简单的,每个内结点有2个、3个或4个子女,即一棵2-3-4树

 

B树的高度

 

根据上图,由于

 

可得:

 

 

B+ 树

  1. B树中同一键值不会出现多次,并且它有可能出现在叶结点,也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中,并且有可能在非叶结点中也有可能重复出现,以维持B+树的平衡。
  2. 因为B树键位置不定,且在整个树结构中只出现一次,虽然可以节省存储空间,但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。
  3. B树的查询效率与键在树中的位置有关,最大时间复杂度与B+树相同(在叶结点的时候),最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的。

 

B* 树

B*树是B树的另一种常用变形,在B*树中要求每个内结点至少是2/3满的,而B树则要求每个内结点至少是半满的

 

插入元素

B树的设计的难点之一就在于元素的插入算法

与普通的排序树一样,我们要将新的元素插入到叶子节点,但是由于B树有元素个数的限制,必须在 2*t 以内,所以当我们插入元素的时候需要注意防止超出界限

一旦插入元素后导致节点内元素个数大于 2*t,那么,我们就必须要进行节点的分裂,以使分裂后的两个节点分别具有 t 个元素,符合B树的限制条件

节点的分裂算法如下面两幅图所示:

 

 

 

如图我们可以发现,分裂后的两个节点分别具有 t 个元素,符合B树的限制,但是两节点的父节点却多了一个元素,我们同样需要保证父节点的元素个数在 t-1 到 2t 之间,所以在必要的时候也需要对父节点进行分裂,这样就构成了一个回溯算法

为了避免回溯,我们可以在下行遍历的过程中对每一个经过的非叶子节点也进行判断,一旦其元素个数为 2*t 即对其进行分裂,这样,我们可以保证在找到插入位置后,即使进行分裂,其父节点也不会超出限制,从而避免了回溯,降低了时间复杂度

 

删除算法

元素删除算法相对于元素的插入算法要复杂一些

当被删除元素所在节点在删除元素后元素数量小于 t-1 时,我们需要一个策略去填充这个节点,具体的算法流程如下图所示

 

 

打印算法

当然,我们也常常需要打印出来当前的 B 树结构来查看 B 树的具体情况

我使用的算法是先根序遍历

树的先根序遍历是基本的算法,这里就不赘述了,详见代码

 

树的释放

与打印算法一样,通过先根序遍历整个树的结构,在遍历过程中对局部的根进行释放,从而最终完成整个树的释放工作

 

/* * file: main.cc * author: 龙泉居士 * date: 2013-07-20 18:23 */ #include <iostream> #include "function/function.h" using namespace std; int main () { B_tree *btree = new B_tree(); cout << "Please input the element:" << endl; int a; while (cin >> a) btree->insert(a); btree->print_tree(); while (1) { cout << "Please input the element be deleted" << endl; cin.clear(); cin >> a; btree->remove (a); cout << "The tree is:" << endl; btree->print_tree(); } delete btree; }

 

 

/* * file: function.h * author: 龙泉居士 * date: 2013-07-20 18:24 */ #ifndef _FUNCTION_20130708_ #define _FUNCTION_20130708_ class B_tree { private: struct Node { Node(bool isleaf=true); ~Node(); int n; //关键字数,对于非根节点n>=t-1,n<=2*t int *key_array; //关键字数组 bool isleaf; //是否是叶子节点 Node **son_array; //叶子节点该值为NULL,否则为指向子女指针的数组,n+1元素 Node *parrent; }; static int t; //关键字数限制,t>=2 void split (Node *node); void sort (Node *node); void fill_element (Node *node); public: B_tree(int t=2); ~B_tree(); Node *root; void print_tree(); Node *search(int *index, int element); void insert(int element); void remove(int element); void remove(Node *node, int index); }; #endif

 

 

/* * file: function.cc * author: 龙泉居士 * date: 2013-07-20 18:24 */ #include <iostream> #include <queue> #include "function.h" using namespace std; int B_tree::t; B_tree::Node::Node(bool isleaf):isleaf(isleaf), son_array(NULL), parrent(NULL) { n=0; key_array = new int[2*B_tree::t+1]; if (!isleaf) son_array = new B_tree::Node *[2*B_tree::t+2]; } B_tree::Node::~Node() { delete [] key_array; if (!isleaf) delete [] son_array; } B_tree::B_tree(int t):root(NULL) { if (t > 2) B_tree::t = t; else B_tree::t = 2; } B_tree::~B_tree() { B_tree::Node *node_tmp = root; int key_index; queue<B_tree::Node *> nque; queue<int> ique; while (node_tmp != NULL) { key_index = 0; if (!node_tmp->isleaf) { nque.push (node_tmp); ique.push (key_index); } else if (nque.empty()) { delete node_tmp; break; } else delete node_tmp; node_tmp = nque.front()->son_array[ique.front()]; ++ique.front(); if (ique.front() > nque.front()->n) { delete nque.front(); nque.pop(); ique.pop(); } } } void B_tree::print_tree() { if (root == NULL) return; B_tree::Node *node_tmp = root; int key_index; queue<B_tree::Node *> nque; queue<int> ique; while (node_tmp != NULL) { key_index = 0; for (int i=0; i<node_tmp->n; ++i) cout << node_tmp->key_array[i] << ' '; cout << endl; if (!node_tmp->isleaf) { nque.push (node_tmp); ique.push (key_index); } else if (nque.empty()) break; node_tmp = nque.front()->son_array[ique.front()]; ++ique.front(); if (ique.front() > nque.front()->n) { nque.pop(); ique.pop(); } } } B_tree::Node *B_tree::search (int *index, int element) { if (index == NULL) { cout << "search input error" << endl; return NULL; } B_tree::Node *tmp_node = root; while (1) { int i; for (i=0; i<tmp_node->n; ++i) { if (element == tmp_node->key_array[i]) { *index = i; return tmp_node; } if (element < tmp_node->key_array[i]) { if (tmp_node -> isleaf) { *index = -1; return NULL; } tmp_node = tmp_node->son_array[i]; i = 0; break; } } if (i == tmp_node->n) { *index = -1; return NULL; } } } void B_tree::split (B_tree::Node *node) { if (node == NULL) { cout << "split input error" << endl; return; } B_tree::Node *new_node = new B_tree::Node(node->isleaf); new_node->n = (node->n-1)/2; new_node->parrent = node->parrent; Node *p = node->parrent; for (int i=new_node->n-1; i>=0; --i) { new_node->key_array[i] = node->key_array[node->n/2+1+i]; if (!node->isleaf) { new_node->son_array[i+1] = node->son_array[node->n/2+i+2]; new_node->son_array[i+1]->parrent = new_node; } } if (node->son_array != NULL) { new_node->son_array[0] = node->son_array[node->n/2+1]; new_node->son_array[0]->parrent = new_node; } if (p == NULL) { root = new B_tree::Node(false); new_node->parrent = node->parrent = root; root->son_array[0] = node; p = root; } p->key_array[p->n] = node->key_array[node->n/2]; p->son_array[p->n+1] = new_node; ++p->n; sort (p); node->n = (node->n-1)/2; } void B_tree::sort (B_tree::Node *node) { if (node == NULL) { cout << "sort input error" << endl; return; } for (int i=0; i<node->n-1; ++i) if (node->key_array[i] >= node->key_array[node->n-1]) { int tmp = node->key_array[node->n-1]; B_tree::Node *tmp_node = NULL; if (!node->isleaf) tmp_node = node->son_array[node->n]; for (int j=node->n-2; j>=i; --j) { node->key_array[j+1] = node->key_array[j]; if (!node->isleaf) node->son_array[j+2] = node->son_array[j+1]; } node->key_array[i] = tmp; if (!node->isleaf) node->son_array[i+1] = tmp_node; break; } } void B_tree::insert (int element) { if (root == NULL) { root = new B_tree::Node(); root->key_array[root->n] = element; root->n++; return; } B_tree::Node *tmp_node = root; while (!tmp_node->isleaf) { bool isend = false; for (int i=0; i<tmp_node->n; ++i) if (tmp_node->key_array[i] >= element) { tmp_node = tmp_node->son_array[i]; isend = true; break; } if (!isend) tmp_node = tmp_node->son_array[tmp_node->n]; } tmp_node->key_array[tmp_node->n] = element; ++tmp_node->n; sort (tmp_node); while (tmp_node->n == 2*B_tree::t+1) { split (tmp_node); tmp_node = tmp_node->parrent; } } void B_tree::remove (B_tree::Node *node, int index) { if (node == NULL || index >= node->n) { cerr << "remove input error" << endl; return; } if (!node->isleaf) { if (node->son_array[index]->n >= B_tree::t) { node->key_array[index] = node->son_array[index]->key_array[node->son_array[index]->n-1]; remove (node->son_array[index], node->son_array[index]->n-1); } else if (node->son_array[index+1]->n >= B_tree::t) //说明待删除元素左侧孩子中元素个数为t-1 { node->key_array[index] = node->son_array[index+1]->key_array[0]; remove (node->son_array[index+1], 0); } else //说明待删除元素左右孩子元素个数均为t-1,此时合并两孩子并删除该元素 { for (int i=0; i<node->son_array[index+1]->n; ++i) { node->son_array[index]->key_array[B_tree::t-1+i] = node->son_array[index+1]->key_array[i]; if (!node->son_array[index] -> isleaf) { node->son_array[index]->son_array[B_tree::t+i] = node->son_array[index+1]->son_array[i]; node->son_array[index]->son_array[B_tree::t+i]->parrent = node->son_array[index]; } } if (!node->son_array[index]->isleaf) { node->son_array[index]->son_array[2*B_tree::t-2] = node->son_array[index+1]->son_array[B_tree::t-1]; node->son_array[index]->son_array[2*B_tree::t-2]->parrent = node->son_array[index]; } node->son_array[index]->n = 2*B_tree::t-2; delete node->son_array[index+1]; for (int i=index; i<node->n-1; ++i) { node->key_array[i] = node->key_array[i+1]; node->son_array[i+1] = node->son_array[i+2]; } node->n--; if (node->parrent == NULL) { if (node->n == 0) { root = node->son_array[index]; root->parrent = NULL; delete node; } } else if (node->n < B_tree::t-1) fill_element (node); } } else //node是叶子 { for (int i=index; i<node->n-1; ++i) node->key_array[i] = node->key_array[i+1]; node->n--; if (node->parrent == NULL) { if (node->n == 0) { delete node; root = NULL; } } else if (node->n < B_tree::t-1) fill_element (node); } } void B_tree::fill_element (Node *node) { if (node->parrent == NULL || node->n != B_tree::t-2) { cerr << "fill input error" << endl; return; } Node *p = node->parrent; int index = -1; for (int i=0; i<node->parrent->n-1; ++i) if (p->key_array[i] <= node->key_array[0] && p->key_array[i+1] >= node->key_array[node->n-1]) { index = i; break; } if (index == -1) //node的右兄弟不存在,则说明node为最右节点 { Node *a = p->son_array[p->n-1]; //node的左兄弟 if (a->n > B_tree::t-1) { for (int i=node->n; i>=0; --i) { if (i>0) node->key_array[i] = node->key_array[i-1]; if (!node->isleaf) node->son_array[i+1] = node->son_array[i]; } ++node->n; node->key_array[0] = p->key_array[p->n-1]; if (!node->isleaf) { node->son_array[0] = a->son_array[a->n]; a->son_array[a->n]->parrent = node; } p->key_array[p->n-1] = a->key_array[a->n-1]; --a->n; } else //a->n == B_tree::t-1 { for (int i=0; i<B_tree::t; ++i) { if (i == B_tree::t-1) { a->key_array[a->n] = p->key_array[p->n-1]; if (!a->isleaf) { a->son_array[a->n+1+i] = node->son_array[i]; node->son_array[i]->parrent = a; } } else { a->key_array[a->n+1+i] = node->key_array[i]; if (!a->isleaf) { a->son_array[a->n+1+i] = node->son_array[i]; node->son_array[i]->parrent = a; } } } a->n = B_tree::t*2-2; delete node; --p->n; if (p->parrent == NULL && p->n == 0) { root = a; a->parrent = NULL; delete a; } else if (p->n < B_tree::t-1) fill_element (p); } } else //node的右兄弟存在 { Node *b = p->son_array[index+2]; if (b->n > B_tree::t-1) { node->key_array[node->n] = p->key_array[index+1]; if (!node->isleaf) { node->son_array[node->n+1] = b->son_array[0]; b->son_array[0]->parrent = node; } p->key_array[index+1] = b->key_array[0]; ++node->n; for (int i=0; i<b->n; ++i) { if (i<b->n-1) b->key_array[i] = b->key_array[i+1]; if (!b->isleaf) b->son_array[i] = b->son_array[i+1]; } --b->n; } else { for (int i=0; i<=B_tree::t; ++i) { if (i == B_tree::t) { node->key_array[node->n] = p->key_array[index+1]; if (!node->isleaf) { node->son_array[node->n+1+i] = b->son_array[b->n]; b->son_array[b->n]->parrent = node; } } else { node->key_array[node->n+1+i] = b->key_array[i]; if (!node->isleaf) { node->son_array[node->n+1+i] = b->son_array[i]; b->son_array[i]->parrent = node; } } } node->n = 2*B_tree::t-2; for (int i=index+1; i<p->n-1; ++i) { p->key_array[i] = p->key_array[i+1]; p->son_array[i+1] = p->son_array[i+2]; } --p->n; if (p->parrent == NULL && p->n == 0) { delete p; root = node; node->parrent = NULL; } else if (p->n < B_tree::t-1) fill_element(p); } } } void B_tree::remove (int element) { int index = -1; B_tree::Node *node = search (&index, element); if (node!=NULL && index>=0 && index<node->n) remove (node, index); else cerr << "Sorray! There's no element as " << element << endl; }

 

 






读书笔记      技术帖      算法      算法导论      数据结构      龙潭书斋      tree      b树      b tree      btree      多分支树     


京ICP备15018585号