B樹的插入

一、B樹的定義

1970年，R. Bayer和E.m ccreight 提出了一種适合外查找的樹，它是一種平衡的多叉樹，稱為B樹，有些地方寫的是B-樹，注意不要誤讀成"B減樹"）

1、B樹（B-tree）是對2-3樹資料結構的擴充，又稱為多路平衡查找樹，它的一個節點可以擁有多于2個子節點的二叉查找樹。與自平衡二叉查找樹不同

2、B樹是一種自平衡樹資料結構，可以保持資料排序，它能夠存儲資料、對其進行排序并允許以O(log n)的時間複雜度運作進行查找、順序讀取、插入和删除的資料結構

3、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樹的插入

步驟：

1、插入一個元素時，首先在B樹中是否存在，如果不存在，即比較大小尋找插入位置，在葉子結點處結束，然後在葉子結點中插入該新的元素

2、如果葉子結點空間足夠，這裡需要向右移動該葉子結點中大于新插入關鍵字的元素，如果空間滿了以緻沒有足夠的空間去添加新的元素，則将該結點進行“分裂”，将一半數量的關鍵字元素分裂到新的其相鄰右結點中，中間關鍵字元素上移到父結點中（當然，如果父結點空間滿了，也同樣需要“分裂”操作）

3、當結點中關鍵元素向右移動了，相關的指針也需要向右移。如果在根結點插入新元素，空間滿了，則進行分裂操作，這樣原來的根結點中的中間關鍵字元素向上移動到新的根結點中，是以導緻樹的高度增加一層

eg：M階B樹--M=3

{53 , 75 , 139 , 49, 145, 36, 101};

插入36：

插入101後還需要分裂。

#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)
    {
      _Insert(pCur, key, pSub);
      size_t size = pCur->_size;
      if (size < M)
        return true;
      else
      {
        size_t mid = size >> 1;
        pNode tmp = new Node();
        for (size_t i= mid + 1; i < size; i++)
        {
          tmp->_key[tmp->_size] = pCur->_key[i];
          tmp->_pSub[tmp->_size] = pCur->_pSub[i];
          if (tmp->_pSub[tmp->_size])
            tmp->_pSub[tmp->_size]->_pParent = tmp;
          tmp->_size++;
        }
        tmp->_pSub[tmp->_size] = pCur->_pSub[pCur->_size];

        if (tmp->_pSub[tmp->_size])
          tmp->_pSub[tmp->_size]->_pParent = tmp;
        pCur->_size -= (tmp->_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] = tmp;
          tmp->_pParent = _pRoot;
          _pRoot->_size = 1;
          return true;
        }
        else
        {
          key = pCur->_key[mid];
          pCur = pCur->_pParent;
          pSub = tmp;
        }
      }
    }
  }

  pair<pNode, int> Find(const K& key)
  {
    pNode pCur = _pRoot;
    pNode pParent = NULL;

    while (pCur)
    {
      size_t 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
  }
private:
  void _Insert(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;
  }
private:
  Node *_pRoot;
};

int main()
{
  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]);

  system("pause");
  return 0;
}