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;
    }
}