B樹

1.查詢效率

圖片.png

來模擬下查找文件29的過程：

(1) 根據(jù)根結(jié)點指針找到文件目錄的根磁盤塊1，將其中的信息導入內(nèi)存?！敬疟PIO操作1次】

(2) 此時內(nèi)存中有兩個文件名17，35和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)17<29<35，因此我們找到指針p2。

(3) 根據(jù)p2指針，我們定位到磁盤塊3，并將其中的信息導入內(nèi)存。【磁盤IO操作2次】

(4) 此時內(nèi)存中有兩個文件名26，30和三個存儲其他磁盤頁面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)26<29<30，因此我們找到指針p2。

(5) 根據(jù)p2指針，我們定位到磁盤塊8，并將其中的信息導入內(nèi)存?！敬疟PIO操作3次】

(6) 此時內(nèi)存中有兩個文件名28，29。根據(jù)算法我們查找到文件29，并定位了該文件內(nèi)存的磁盤地址。

2.插入操作理解過程

1、插入以下字符字母到一棵空的B 樹中（非根結(jié)點關鍵字數(shù)小了（小于2個）就合并，大了（超過4個）就分裂）：C N G A H E K Q M F W L T Z D P R X Y S，首先，結(jié)點空間足夠，4個字母插入相同的結(jié)點中，如下圖：

圖片.png

2、當試著插入H時，結(jié)點發(fā)現(xiàn)空間不夠，以致將其分裂成2個結(jié)點，移動中間元素G上移到新的根結(jié)點中，在實現(xiàn)過程中，咱們把A和C留在當前結(jié)點中，而H和N放置新的其右鄰居結(jié)點中。如下圖：

圖片.png

3、當咱們插入E,K,Q時，不需要任何分裂操作

圖片.png

4、插入M需要一次分裂，注意M恰好是中間關鍵字元素，以致向上移到父節(jié)點中

圖片.png

5、插入F,W,L,T不需要任何分裂操作

圖片.png

6、插入Z時，最右的葉子結(jié)點空間滿了，需要進行分裂操作，中間元素T上移到父節(jié)點中，注意通過上移中間元素，樹最終還是保持平衡，分裂結(jié)果的結(jié)點存在2個關鍵字元素。

圖片.png

7、插入D時，導致最左邊的葉子結(jié)點被分裂，D恰好也是中間元素，上移到父節(jié)點中，然后字母P,R,X,Y陸續(xù)插入不需要任何分裂操作（別忘了，樹中至多5個孩子）。

圖片.png

8、最后，當插入S時，含有N,P,Q,R的結(jié)點需要分裂，把中間元素Q上移到父節(jié)點中，但是情況來了，父節(jié)點中空間已經(jīng)滿了，所以也要進行分裂，將父節(jié)點中的中間元素M上移到新形成的根結(jié)點中，注意以前在父節(jié)點中的第三個指針在修改后包括D和G節(jié)點中。這樣具體插入操作的完成。

圖片.png

3.刪除節(jié)點理解

eg1.

1、首先刪除元素H，當然首先查找H，H在一個葉子結(jié)點中，且該葉子結(jié)點元素數(shù)目3大于最小元素數(shù)目ceil(m/2)-1=2，則操作很簡單，咱們只需要移動K至原來H的位置，移動L至K的位置（也就是結(jié)點中刪除元素后面的元素向前移動）

圖片.png

2、下一步，刪除T,因為T沒有在葉子結(jié)點中，而是在中間結(jié)點中找到，咱們發(fā)現(xiàn)他的繼承者W(字母升序的下個元素)，將W上移到T的位置，然后將原包含W的孩子結(jié)點中的W進行刪除，這里恰好刪除W后，該孩子結(jié)點中元素個數(shù)大于2，無需進行合并操作。

圖片.png

3、下一步刪除R，R在葉子結(jié)點中,但是該結(jié)點中元素數(shù)目為2，刪除導致只有1個元素，已經(jīng)小于最小元素數(shù)目ceil(5/2)-1=2,而由前面我們已經(jīng)知道：如果其某個相鄰兄弟結(jié)點中比較豐滿（元素個數(shù)大于ceil(5/2)-1=2），則可以向父結(jié)點借一個元素，然后將最豐滿的相鄰兄弟結(jié)點中上移最后或最前一個元素到父節(jié)點中（有沒有看到紅黑樹中左旋操作的影子?），在這個實例中，右相鄰兄弟結(jié)點中比較豐滿（3個元素大于2），所以先向父節(jié)點借一個元素W下移到該葉子結(jié)點中，代替原來S的位置，S前移；然后X在相鄰右兄弟結(jié)點中上移到父結(jié)點中，最后在相鄰右兄弟結(jié)點中刪除X，后面元素前移。

圖片.png

4、最后一步刪除E， 刪除后會導致很多問題，因為E所在的結(jié)點數(shù)目剛好達標，剛好滿足最小元素個數(shù)（ceil(5/2)-1=2）,而相鄰的兄弟結(jié)點也是同樣的情況，刪除一個元素都不能滿足條件，所以需要該節(jié)點與某相鄰兄弟結(jié)點進行合并操作；首先移動父結(jié)點中的元素（該元素在兩個需要合并的兩個結(jié)點元素之間）下移到其子結(jié)點中，然后將這兩個結(jié)點進行合并成一個結(jié)點。所以在該實例中，咱們首先將父節(jié)點中的元素D下移到已經(jīng)刪除E而只有F的結(jié)點中，然后將含有D和F的結(jié)點和含有A,C的相鄰兄弟結(jié)點進行合并成一個結(jié)點。

圖片.png

5、也許你認為這樣刪除操作已經(jīng)結(jié)束了，其實不然，在看看上圖，對于這種特殊情況，你立即會發(fā)現(xiàn)父節(jié)點只包含一個元素G，沒達標（因為非根節(jié)點包括葉子結(jié)點的關鍵字數(shù)n必須滿足于2=<n<=4，而此處的n=1），這是不能夠接受的。如果這個問題結(jié)點的相鄰兄弟比較豐滿，則可以向父結(jié)點借一個元素。假設這時右兄弟結(jié)點（含有Q,X）有一個以上的元素（Q右邊還有元素），然后咱們將M下移到元素很少的子結(jié)點中，將Q上移到M的位置，這時，Q的左子樹將變成M的右子樹，也就是含有N，P結(jié)點被依附在M的右指針上。所以在這個實例中，咱們沒有辦法去借一個元素，只能與兄弟結(jié)點進行合并成一個結(jié)點，而根結(jié)點中的唯一元素M下移到子結(jié)點，這樣，樹的高度減少一層。

圖片.png

eg2.

這里是一棵不同的5序B樹，那咱們試著刪除C

圖片.png

于是將刪除元素C的右子結(jié)點中的D元素上移到C的位置，但是出現(xiàn)上移元素后，只有一個元素的結(jié)點的情況。

又因為含有E的結(jié)點，其相鄰兄弟結(jié)點才剛脫貧（最少元素個數(shù)為2），不可能向父節(jié)點借元素，所以只能進行合并操作，于是這里將含有A,B的左兄弟結(jié)點和含有E的結(jié)點進行合并成一個結(jié)點。

圖片.png

這樣又出現(xiàn)只含有一個元素F結(jié)點的情況，這時，其相鄰的兄弟結(jié)點是豐滿的（元素個數(shù)為3>最小元素個數(shù)2），這樣就可以想父結(jié)點借元素了，把父結(jié)點中的J下移到該結(jié)點中，相應的如果結(jié)點中J后有元素則前移，然后相鄰兄弟結(jié)點中的第一個元素（或者最后一個元素）上移到父節(jié)點中，后面的元素（或者前面的元素）前移（或者后移）；注意含有K，L的結(jié)點以前依附在M的左邊，現(xiàn)在變?yōu)橐栏皆贘的右邊。這樣每個結(jié)點都滿足B樹結(jié)構(gòu)性質(zhì)。

圖片.png

從以上操作可看出：除根結(jié)點之外的結(jié)點（包括葉子結(jié)點）的關鍵字的個數(shù)n滿足：（ceil(m  / 2)-1）<= n <= m-1，即2<=n<=4。這也佐證了咱們之前的觀點。刪除操作完。