資料結構之B+樹
title: 資料結構之B+樹
date: 2018-11-04 20:39:00
tags: 資料結構與算法之美
一、 淺談B-樹索引
1.B-樹的特性
一棵m階B-樹，或者是空樹，或者是滿足以下性質的m叉樹
根結點至少有兩個分支；
除根以外的非葉結點，每個結點包含分支數範圍[[m/2],m]，即關鍵字字數的範圍是[[m/2]-1,m-1]，其中[m/2]表示取大于等于m/2的最小整數
所有葉子結點都在樹的同一層上，并且指針域為空；
所有的非終端結點應包含如下資訊： (n，A0，K1，A1，K2，A2，… ，Kn，An)，結點内關鍵字互不相等，且從小到大排列。
解釋：
m階的意思是這顆樹最多的分支是多少，每個節點可以包含很多關鍵字，範圍是[[m/2]-1,m-1]，比如m為 3，就說明是3階的B-樹，
那麼它的樹的節點的關鍵字最少2，最多4個。下面的B+樹也是同樣的了解。
2.B-樹索引結構圖
3.B-樹查找代價分析
設關鍵字的總數為 N ，求 m階 B- 樹的最大層次 L。
二、 B+樹的索引結構
1.B+樹特性
在實際的檔案系統中，基本上不使用B_樹，而是使用B_樹的一種變體，稱為m階B+樹。 它與B-樹的主要不同是葉子結點中存儲記錄。在B+樹中，所有的非葉子結點可以看成是索引，而其中的關鍵字是作為“分界關鍵
字”，用來界定某一關鍵字的記錄所在的子樹。一棵m階B+樹與m階B-樹的主要差異是：
1.若一個結點有n棵子樹，則必含有n個關鍵字；
2.所有葉子結點中包含了全部記錄的關鍵字資訊以及這些關鍵字記錄的指針，而且葉子結點按關鍵字的大小從小到大順序連結；
3.所有的非葉子結點可以看成是索引的部分，結點中隻含有其子樹的根結點中的最大(或最小)關鍵字。
2.B+樹索引結構圖
三、 B+樹的索引操作
1.B+樹查找
對B+樹可以進行兩種查找運算：
- 從最小關鍵字開始，進行順序查找。
- 從根結點開始，進行随機查找
在查找時，若非終端結點上的關鍵值等于給定值，并不終止，而是繼續向下直到葉子結點。是以，在B+樹中，不管查找成功與否，每次查找都是走了一條從根到葉子結點的路徑。其餘同B-樹的查找類似。
// 在樹中查找資料
bool BPlusTree::Search(KEY_TYPE data, char* sPath)
{
int i = 0;
int offset = 0;
if (NULL != sPath)
{
(void)sprintf(sPath+offset, "The serach path is:");
offset+=19;
}
CNode * pNode = GetRoot();
// 循環查找對應的葉子結點
while (NULL != pNode)
{
// 結點為葉子結點，循環結束
if (NODE_TYPE_LEAF == pNode->GetType())
{
break;
}
// 找到第一個鍵值大于等于key的位置
for (i = 1; (data >= pNode->GetElement(i) )&& (i <= pNode->GetCount()); i++)
{
}
if (NULL != sPath)
{
(void)sprintf(sPath+offset, " %3d -->", pNode->GetElement(1));
offset+=8;
}
pNode = pNode->GetPointer(i);
}
// 沒找到
if (NULL == pNode)
{
return false;
}
if (NULL != sPath)
{
(void)sprintf(sPath+offset, "%3d", pNode->GetElement(1));
offset+=3;
}
// 在葉子結點中繼續找
bool found = false;
for (i = 1; (i <= pNode->GetCount()); i++)
{
if (data == pNode->GetElement(i))
{
found = true;
}
}
if (NULL != sPath)
{
if (true == found)
{
(void)sprintf(sPath+offset, " ,successed.");
}
else
{
(void)sprintf(sPath+offset, " ,failed.");
}
}
return found;
}
2.B+樹查找代價分析
3.B+樹插入
m階B樹的插入操作在葉子結點上進行，假設要插入關鍵值a，找到葉子結點後插入a，做如下算法判别：
1、如果目前結點是根結點并且插入後結點關鍵字數目小于等于m，則算法結束；
2、如果目前結點是非根結點并且插入後結點關鍵字數目小于等于m，則判斷若a是新索引值時轉步驟④後結束，若a不是新索引值則直接結束；
3、如果插入後關鍵字數目大于m(階數)，則結點先分裂成兩個結點X和Y，并且他們各自所含的 關鍵字個數分别為：u=大于(m+1)/2的最小整數，v=小于(m+1)/2的最大整數；由于索引值位于結點的最左端或者最右端，不妨假設索引值位于結點最右端，有如下操作：
a)如果目前分裂成的X和Y結點原來所屬的結點是根結點，則從X和Y中取出索引的關鍵字，将這兩個關鍵字組成新的根結點，并且這個根結點指向X和Y，算法結束；
b)如果目前分裂成的X和Y結點原來所屬的結點是非根結點，依據假設條件判斷，如果a成為Y的新索引值，則轉步驟④得到Y的雙親結點P，如果a不是Y結點的新索引值，則求出X和Y結點的雙親結點P；然後提取X結點中的新索引值a’，在P中插入關鍵字a’，從P開始，繼續進行插入算法；
4、提取結點原來的索引值b，自頂向下，先判斷根是否含有b，是則需要先将b替換為a，然後從根結點開始，記錄結點位址P，判斷P的孩子是否含有索引值b而不含有索引值a，是則先将孩子結點中的b替換為a，然後将P的孩子的位址指派給P，繼續搜尋，直到發現P的孩子中已經含有a值時，停止搜尋，傳回位址P。
4.B+樹的插入過程
5.B+樹的删除操作
B+樹的删除僅在葉結點上進行。
當葉子結點中的最大關鍵字被删除時，其在非終端結點中的值可以作為一個“分界關鍵字”存在。若因删除而使結點中關鍵字的個數少于m/2 （m/2結果取上界，如5/2結果為3）時，其和兄弟結點的合并過程亦和B-樹類似。
6.B+樹的删除過程
四、 B+樹的優分析
1.為什麼選擇B+樹？
1、B+樹的磁盤讀寫代價更低
我們都知道磁盤時可以塊存儲的，也就是同一個磁道上同一盤塊中的所有資料都可以一次全部讀取。而B+樹的内部結點并沒有指向關鍵字具體資訊的指針 。是以其内部結點相對B_樹更小。如果把所有同一内部結點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多。這樣，一次性讀入記憶體中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。
2、B+樹的查詢效率更加穩定。
由于非終結點并不是最終指向檔案内容的結點，而隻是葉子結點中關鍵字的索引。是以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導緻每一個資料的查詢效率相當。
關注公衆号一起交流：