本文只總結(jié)刪除。

核心思想為，優(yōu)先處理下層次的結(jié)構(gòu)，處理好后，下層次不再改變；把錯誤往上傳遞。

——————————————————

B樹：

1、第一次被刪除的一定是葉子節(jié)點的某個元素

2、（暫定刪除節(jié)點元素為X）如果刪除后，本節(jié)點的元素數(shù)少于等于（1/2總元素數(shù)向上取整后-1），則3或4；否則直接結(jié)束

3、如果兄弟節(jié)點也沒有富裕元素，則兄弟和本節(jié)點和parent中連接兩節(jié)點的元素合并。注意parent中被合并的元素層次會下降。【如果此時參考點為葉子節(jié)點，則這時候相當于刪除了parent的一個元素?，F(xiàn)在把參考點設為parent，回到步驟2】【如果現(xiàn)在參考點不是葉子節(jié)點，則同樣要把上一層節(jié)點中的一個元素下降到這里，和自己與兄弟合并。參考點再次向上挪一層?；氐讲襟E2】

4、如果兄弟有富裕（大于 1/2總元素數(shù)向上取整后-1），則向parent借一個元素P，然后取一個兄弟的元素Q取代原來P的位置?！救绻F(xiàn)在參考點為葉子節(jié)點，則可以結(jié)束。】【此時如果參考點不是葉子節(jié)點，要把兄弟的Q的一棵子樹，給到被合并的元素X所在的那一個節(jié)點上】

————————————————

B+樹

比價樹的刪除要easy一些。

1、首先刪除的肯定是處于葉子節(jié)點。

2、這時候如果這個節(jié)點元素數(shù)不是很少，則直接結(jié)束。如果元素少于標準，則3或4

3、如果兄弟富裕，從兄弟借一個。具體操作為把父節(jié)點的一個關鍵字用兄弟兩端的某個元素代替，然后把兄弟的一個元素移過來。

4、如果兄弟不富裕，則和兄弟合并，刪除父節(jié)點的一個元素。

===》現(xiàn)在把參考點設為父節(jié)點。

此時父節(jié)點少了一個元素；且除了葉子節(jié)點，b+樹與b樹無異。

則現(xiàn)在直接把執(zhí)行流跳轉(zhuǎn)到b樹的第2條。