首页 > 数据结构 > 树形结构 > B树(一)概述和C++实现
2014
06-08

B树(一)概述和C++实现

B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B-树为系统最优化大块数据的读和写操作。
为什么要使用b树?大多数其他的自动平衡搜索树(比如AVL树和红黑树),都假设一切都是在主内存。我们必须考虑大量的数据,不能全部放入主存。B树由于是多叉树,可以大大的降低树的高度,从而减少磁盘的访问的次数(此部分在算法导论一书有详细介绍)。普遍运用在数据库和文件系统。

B树的定义

是一种多路搜索树(并不是二叉的),具有以下的性质:
1. 由最小度数 t 定义,t根据磁盘块大小确定。
2. 除根节点以外的其它节点,必须包含至少 t-1 个关键字。根节点可以至少有1个关键字。
3. 所有节点(包括根节点),可以包含最多 2t-1 个关键字。
4.  非叶子结点的关键字个数=指向儿子的指针个数 – 1
6. 非叶子结点的关键字:K[1], K[2], …, K[2t-1];且K[i] < K[i+1];就是说升序排列。
7. 非叶子结点的指针:P[1], P[2], …, P[2t-1];其中P[1]指向关键字小于K[1]的子树,P[2t-1]指向关键字大于K[2t-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
8.所有叶子结点位于同一层;

如:(t=3)时,即最少要有2个以上的关键字:

BTreeIntro1

B-树的特性:
1.关键字集合分布在整颗树中;
2.任何一个关键字出现且只出现在一个结点中;
3.搜索有可能在非叶子结点结束;
4.其搜索性能等价于在关键字全集内做一次二分查找;
5.自动层次控制;

B-树的搜索

从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;

B-树的遍历
和二叉树的先序遍历类似。我们从最左边的孩子开始,递归地打印最左边的孩子,然后剩下的孩子重复相同的过程。最后,递归地打印最右边的孩子。

代码实现

#include<iostream>
using namespace std;

// 一个 BTree 节点
class BTreeNode
{
    int *keys;  // 关键字 的数组
    int t;      //最小的度
    BTreeNode **C; // 孩子节点指针数组
    int n;     // 当前节点关键字的数量
    bool leaf; // 是否是叶子节点
public:
    BTreeNode(int _t, bool _leaf);   // 构造函数

    // 遍历B树
    void traverse();

    //在B树中查找 k
    BTreeNode *search(int k);

friend class BTree;
};

// B树类
class BTree
{
    BTreeNode *root; // 指向根节点
    int t;  // 最小的度
public:
    // 构造函数
    BTree(int _t)
    {  root = NULL;  t = _t; }

    // 遍历树
    void traverse()
    {  if (root != NULL) root->traverse(); }

    // 查找
    BTreeNode* search(int k)
    {  return (root == NULL)? NULL : root->search(k); }
};

// 构造函数
BTreeNode::BTreeNode(int _t, bool _leaf)
{
    t = _t;
    leaf = _leaf;

    // 分配内存
    keys = new int[2*t-1];
    C = new BTreeNode *[2*t];

    // 初始关键字个数为0
    n = 0;
}

// 遍历当前节点和当前节点下的子树
void BTreeNode::traverse()
{
    // n个关键字,和n+1个孩子
    int i;
    for (i = 0; i < n; i++)
    {
        if (leaf == false)
            C[i]->traverse();
        cout << " " << keys[i];
    }

    //遍历最后一个孩子
    if (leaf == false)
        C[i]->traverse();
}

// 在当前节点下查找 k
BTreeNode *BTreeNode::search(int k)
{
    // 找到第一个大于或等于k的关键字
    int i = 0;
    while (i < n && k > keys[i])
        i++;

    //如果相等,就找到了
    if (keys[i] == k)
        return this;

    //如果是叶节点,未找到
    if (leaf == true)
        return NULL;

    // 否则可能在子树中
    return C[i]->search(k);
}

上面的代码只是初步的实现,后续文章会实现 B树的插入和删除操作,并给出完整的包含测试的代码。

参考:http://www.geeksforgeeks.org/b-tree-set-1-introduction-2/


  1. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }