B+樹：

(1)每個分支節點最多有m個子樹(孩子節點)。

階：即看當前的B+樹是幾階B+樹，就看每個分支節點最多有幾個子樹，還是看最下一層有幾個分叉就是幾階？？？

葉子節點：最下邊的一層叫葉子節點(不是跟B樹一樣的失敗節點)

非葉根節點：當前的B+樹中根節點下邊還有子節點，即根節點不是最下邊的一層節點(葉子節點)，則當前的根節點叫非葉子節點的根節點，即非葉根節點。

葉根節點：當前的B+樹只有一層，即只有一層根節點，根節點下邊再沒有子樹節點，則當前的根節點也是葉子節點(如圖2中的左一)

(2)非葉根節點至少有2棵子樹，其他每個分支節點至少有m/2向上取整個子樹，前者是為了讓B+樹盡可能的低，使查找效率高一點，所以要保持絕對平衡，即假如當前的根節點是非葉根節點，它如果有左子樹，則它必定有右子樹，否則不滿足B+樹要求(如圖2中的中間的圖)，后者是為了讓B+樹的每個節點上的關鍵字盡可能的多，也是為了保證B+樹的高度沒那么高，提高查找效率

(3)節點的子樹個數與關鍵字的個數相等。即一個節點上有幾個關鍵字，則它就有幾個分叉，即就有幾個子樹，如(3,9,15)節點上有3個關鍵字，則它就有3個分叉，即3個子樹，(1,3)(6,8,9)(13,15)。注意與B樹區分，B樹上一個節點上有2個關鍵字它得有3個分叉，即3個子樹

(4)葉節點包含以上成所有的關鍵字+指向相應記錄的指針，葉節點中的關鍵字按大小順序排列，相鄰葉節點按大小順序相互鏈接起來，即葉節點那一層支持橫向順序查找。每個關鍵字對應了一個指向詳細記錄的指針(如葉節點的關鍵字是一個個學號，學號連接著每個學生的具體信息，即學號連接著記錄)

(5)跟分塊查找的索引表類似，所有分支節點上的各個關鍵字都只包含了關鍵字指向子節點上的所有關鍵字的最大值。比如(3,9,15)中的3就是它的子節點(1,3)中關鍵字最大值，9是子節點(6,8,9)中的最大值，15是子節點(13,15)的最大值

對比分塊查找：

B+樹的查找：

查找成功目標元素9(實際查找的是9所指的記錄)： 從根節點開始找，第一個關鍵字15是它所有的子節點(所有的子節點指的是它的整個左子樹節點，包括子節點和孫子節點等待)中最大的關鍵字的值，15>9則如果目標元素存在，則它只能在15所指向的分塊中，讓指針指向下一級節點3，3是它所指的分塊中最大的關鍵字，3<9則9肯定不在3所指的分塊里，讓指針右移指向9，9==9，則在9所指的分塊里，讓指針下移，從左往右開始比較葉子節點，直到找到9==9，則9關鍵字所保存指針信息就可以找到9號元素的詳細記錄信息，進而讀出相應記錄

查找失敗目標元素7(實際查找的是7所指的記錄)： 從根節點開始找，15>7則如果目標元素存在，則它只能在15所指向的分塊中，讓指針指向下一級節點3，3<7則7肯定不在3所指的分塊中，讓指針右移9，7<9則如果7存在7一定在9所指的分塊中，讓指針下移指向(6,8,9)節點，從左往右開始比較葉子節點，6<7指針右移，7<8，因為已經找的是最下一層的葉子節點了，如果沒找到7證明7不存在，則查找失敗

無論查找成功還是失敗都要走到最下一層即葉子節點處才能確定到底是否查找成功，因為分支節點上的范圍并不是實際的關鍵字，實際有哪些關鍵字其實是在葉子節點存放，但是B樹查找不是，可能停留在任何一層就能知道?是否能查找成功了。

B+樹VSB樹：

m階B樹：

(1)節點中的n個關鍵字對應n+1個分叉，即n+1個子樹

(2)B樹中為了保證樹不太高，節點上的關鍵字不太空，所以要求B樹中的根節點的關鍵字個數不能少于1個，即根節點關鍵字個數范圍(1,m-1)【根節點中最多的關鍵字個數和其他節點的關鍵字個數最多一樣】，其他節點的分叉不能少于m/2向上取整，則關鍵字個數不能少于m/2向上取整-1個，對于m階B樹，則每個節點的最多分叉有m個，即最多的關鍵字個數有m-1個，即其他節點的關鍵字個數范圍(m/2向上取整-1，m-1)

(3)在B樹中，各個節點包含的關鍵字是不會重復出現的

(4)B樹中的各個關鍵字也存儲了實際關鍵字對應的記錄存儲地址，即不用找到葉子節點，只要找到了這個關鍵字就相當于找到了記錄存儲地址即記錄信息，但是B+樹不行，B+樹一定要在葉子節點上找到了這個關鍵字，才能找到這個關鍵字的存儲記錄的地址，才能找到實際存放的數據信息

?

m階B+樹：

(1)節點中的n個關鍵字對應n個分叉，即n個子樹

(2)B+樹中為了保證樹不太高，節點上的關鍵字不太空，所以要求B+樹中的根節點的關鍵字個數不能少于1個，即根節點關鍵字個數范圍(1,m)【根節點中最多的關鍵字個數和其他節點的關鍵字個數最多一樣】，其他節點的分叉不能少于m/2，則關鍵字個數不能少于m/2向上取整個，對于m階B+樹，則每個節點的最多分叉有m個，即最多的關鍵字個數有m個，即其他節點關鍵字個數范圍為(m/2，m)

(3)B+樹葉子節點中包含全部的關鍵字，則某個關鍵字可能會在其他非葉子節點多次出現，如下圖2中的15關鍵字在3處出現

(4)在B樹中，所有非葉子節點僅起到索引查找作用，實際并不包含目標元素記錄的存儲地址，而只有找到葉子節點了，才能找到該關鍵字對應記錄的存儲記錄，如學生信息，學生信息是記錄，關鍵字是學號，一個學號對應一個學生記錄。非葉子節點的每個索引項(指非葉子節點中的關鍵字)只包含了子樹的最大關鍵字和指向該子樹的指針

B+樹中的各個節點存儲在磁盤，操作系統對磁盤的讀寫一般是以一個磁盤塊為單位，一般B+樹的一個節點就會存儲在某個磁盤塊中，即B+樹中所有的節點都是存儲在不同的磁盤塊里，因此從根節點開始查找，會先確定根節點到底在哪個磁盤塊中，然后把根節點所在的磁盤塊讀入內存，即把(15,56)所在磁盤塊讀入內存，讀入內存之后計算機就可以處理查詢數據，就可以知道要去哪個分支去找，比如要找關鍵字42，在讀入內存之后就知道要去56指向的分塊去找，現在知道了56所指的分塊存儲在磁盤什么位置之后，就會把56所指的分塊讀入內存，即(35,42,56)讀入內存后，九三級去查詢分塊內的數據，然后計算機發現42存儲在42所指的分塊中，然后通過內存中的信息就可以知道，42所指的葉子節點存儲在磁盤的哪個位置，然后操作系統再把42所指的分塊讀入內存，讀入內存之后就可以知道42這個關鍵字它所對應的記錄到底存儲在磁盤的哪個位置，然后再把記錄讀入內存。磁盤是一個慢速設備，每次要讀取磁盤塊數據都會花費大量時間，因此假如B+樹高度越高就意味著在讀取磁盤的過程中讀取次數越多，導致查找速度更慢，如何降低B+樹高度，即讓B+樹節點存儲更多的關鍵字，即這也是為什么B+樹上的非葉子節點不存儲實際的記錄地址了，這樣能節省更多的空間來存儲關鍵字，并且這些一個個節點是存儲在每個磁盤塊中，而每個磁盤塊大小基本固定如1kb，而讓每個磁盤塊包含盡可能多的關鍵字的信息，當節點的空間大了則每個節點存儲的關鍵字就多了，則磁盤上就包含了盡可能多的關鍵字信息了。。。。。。，即每個關鍵字不存儲記錄指針，會讓關鍵字更多，即分叉更多，即B+樹的高度越矮，即讀取磁盤的次數減少，即效率更高。B樹的一個關鍵字中還包含了記錄的存儲地址，這就意味著一個節點存儲的關鍵字就會少，這也就意味著磁盤塊中存儲的節點上的關鍵字就會少，則B樹會導致磁盤塊讀取次數增多，而磁盤塊讀取又耗時，則會降低效率

知識回顧：

?

好羅里吧嗦。。。。。。。。。。。。。。。。。。。。。?

?