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

た入场券 2022-05-29 07:30 214阅读 0赞

## 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. 所有的叶子节点都在同一层  
如下图所示:  
![这里写图片描述][Image 1]

--------------------

## B树的插入 ##

B树的插入需要在叶子结点处插入，当结点中的关键字满时，需要做分裂操作。为方便实现操作，我们在定义结点的时候多定义一个关键字和指针。举一个例子：在下面这个树中插入101这个数字。  
![Image 1][]  
![这里写图片描述][Image 1]  
![这里写图片描述][Image 1]  
总结一下：  
1. 找插入位置（如果找到了，则不必再插入）  
2. 将元素插入找到的位置（使用插入排序的思想）  
3. 检测当前结点是否满足性质，关键字至多M-1个，如果不满足该性质，则需要将该结点分裂  
4. 分裂：找中间位置，将中间位置以后的元素全部搬移到新结点（孩子结点比关键字多搬移一个），如果当前结点不是根结点，那么将中间元素搬移到当前结点的双亲，看双亲结点是否满足性质，继续循环；如果当前结点是根结点，则需要再将根结点分裂一次

--------------------

## B树与B+树的区别： ##

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

--------------------

下面是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;
        }
    }

[Image 1]: