【数据结构】对B树的认识

B树的引入

  二叉搜索树、平衡二叉树、红黑树都是我们之前学过的典型的二叉搜索树,其查找的时间复杂度和树的高度都是O(log2N)。
  但是如果我们的数据量很大的话,比如像文件系统及数据库系统普遍都采用B-/+树作为索引结构。一般来说,索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储在磁盘上。这样的话,索引查找过程中就要产生磁盘I/O的消耗,相信大家都知道,相比于内存存取,I/O操作的消耗会更大,因此,我们需要尽量减少查找过程中磁盘I/O的存取次数。
  如果使用红黑树的结构,当然也可以达到目的,但这样的缺点是数据量大,树的高度太高,访问磁盘的次数增加,从而效率低下。


B树的定义

  B树也可以写作B-树(但不可以读成“B减树”,这样是不对的),它是一种平衡的多叉树。定义如下:
  一棵M阶(M>2)的B树,是一棵平衡的M路平衡搜索树,可以是空树或者满足一下性质:
 1. 根节点至少有两个孩子
 2. 每个非根节点至少有M/2(上取整)个孩子,至多有M个孩子
 3. 每个非根节点至少有M/2-1(上取整)个关键字,至多有M-1个关键字,并且以升序排列
 4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间
 5. 所有的叶子节点都在同一层
如下图所示:
这里写图片描述


B树的插入

  B树的插入需要在叶子结点处插入,当结点中的关键字满时,需要做分裂操作。为方便实现操作,我们在定义结点的时候多定义一个关键字和指针。举一个例子:在下面这个树中插入101这个数字。

这里写图片描述
这里写图片描述
总结一下:
1. 找插入位置(如果找到了,则不必再插入)
2. 将元素插入找到的位置(使用插入排序的思想)
3. 检测当前结点是否满足性质,关键字至多M-1个,如果不满足该性质,则需要将该结点分裂
4. 分裂:找中间位置,将中间位置以后的元素全部搬移到新结点(孩子结点比关键字多搬移一个),如果当前结点不是根结点,那么将中间元素搬移到当前结点的双亲,看双亲结点是否满足性质,继续循环;如果当前结点是根结点,则需要再将根结点分裂一次


B树与B+树的区别:

B+树与B树基本相同,区别在于B+树只有达到叶子结点才命中(B树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找。
B+树的特性:
1. 所有的关键字都出现在非叶子结点的链表中,且链表中的关键字恰好是有序的
2. 不可能在飞叶子结点命中
3. 非叶子结点相当于是叶子结点的索引,叶子结点相当于是存储数据的数据层
4. 更适合文件索引系统、
这里写图片描述


下面是B树具体的结构及插入操作,在此我将M默认设置为3,也可以修改为其他的值

#include <iostream>
using namespace std;
template <class K, int M=3>
struct BTreeNode
{
    BTreeNode()
    : _pParent(NULL)
    , _size(0)
    {
        for (size_t i = 0; i <= M; i++)
            _pSub[i] = NULL;
    }
    K _key[M];
    BTreeNode<K, M>* _pSub[M + 1];
    BTreeNode<K, M>* _pParent;
    size_t _size;
};
template <class K, int M=3>
class BTree
{
    typedef BTreeNode<K, M> Node;
    typedef Node* PNode;
public:
    BTree()
        : _pRoot(NULL)
    {}

    bool Insert(K& key)
    {
        if (_pRoot == NULL)//根结点直接插入
        {
            _pRoot = new Node();
            _pRoot->_key[0] = key;
            _pRoot->_size = 1;
            return true;
        }

        pair<PNode, int> ret = Find(key);
        if (ret.second >= 0)//没找到才需要插入结点
            return false;

        PNode pCur = ret.first;
        PNode pSub = NULL;
        while (1)
        {
            _InsertKey(pCur, key, pSub);//插入结点

            int size = pCur->_size;
            if (size < M)//插入成功,不需要分裂
                return true;
            else
            {
                int mid = size >> 1;
                PNode temp = new Node();

                for (size_t i = mid + 1; i < size; i++)//分裂 搬移结点中的key和孩子结点
                {
                    temp->_key[temp->_size] = pCur->_key[i];
                    temp->_pSub[temp->_size] = pCur->_pSub[i];
                    if (temp->_pSub[temp->_size])
                        temp->_pSub[temp->_size]->_pParent = temp;
                    temp->_size++;
                }
                temp->_pSub[temp->_size] = pCur->_pSub[pCur->_size];

                if (temp->_pSub[temp->_size])
                    temp->_pSub[temp->_size]->_pParent = temp;
                pCur->_size -= (temp->_size + 1);//处理size

                if (pCur == _pRoot)//如果当前结点是根结点,还需要再处理
                {
                    _pRoot = new Node;
                    _pRoot->_key[0] = pCur->_key[mid];
                    _pRoot->_pSub[0] = pCur;
                    pCur->_pParent = _pRoot;
                    _pRoot->_pSub[1] = temp;
                    temp->_pParent = _pRoot;
                    _pRoot->_size = 1;
                    return true;
                }
                else
                {
                    key = pCur->_key[mid];
                    pCur = pCur->_pParent;
                    pSub = temp;
                }
            }
        }
    }

    pair<PNode, int> Find(const K& key)//查找值为key的结点,找到返回结点及在结点中的位置,没找到返回当前结点的双亲结点及-1
    {
        PNode pCur = _pRoot;
        PNode pParent = NULL;
        while (pCur)
        {
            int i = 0;
            while (i < pCur->_size)
            {
                if (key == pCur->_key[i])
                    return pair<PNode, int>(pCur, i);
                else if (key < pCur->_key[i])
                    break;
                else
                    i++;
            }
            pParent = pCur;
            pCur = pCur->_pSub[i];
        }
        return make_pair(pParent, -1);//没找到返回-1
    }

    void InOrder()
    {
        _InOrder(_pRoot);
    }
private:
    void _InsertKey(PNode pCur, const K& key, PNode pSub)
    {
        //直接插入的思想
        int end = pCur->_size - 1;
        while (key < pCur->_key[end] && end >= 0)
        {
            pCur->_key[end + 1] = pCur->_key[end];
            pCur->_pSub[end + 2] = pCur->_pSub[end + 1];
            end--;
        }

        pCur->_key[end + 1] = key;
        pCur->_pSub[end + 2] = pSub;
        if (pSub)
            pSub->_pParent = pCur;
        pCur->_size += 1;
    }

    void _InOrder(PNode pRoot)
    {
        if (pRoot == NULL)
            return;
        for (size_t i = 0; i < pRoot->_size; i++)
        {
            _InOrder(pRoot->_pSub[i]);
            cout << pRoot->_key[i] << " ";
        }
        _InOrder(pRoot->_pSub[pRoot->_size]);
    }
private:
    PNode _pRoot;
};

void test()
{
    int arr[] = { 53, 75, 139, 49, 145, 36, 101 };
    BTree<int> b;
    size_t size = sizeof(arr) / sizeof(arr[0]);
    for (size_t i = 0; i < 7; i++)
    {
        b.Insert(arr[i]);
        b.InOrder();
        cout << endl;
    }
}
相关文章
相关标签/搜索
每日一句
    每一个你不满意的现在,都有一个你没有努力的曾经。
本站公众号
   欢迎关注本站公众号,获取更多程序园信息
开发小院