這一節(jié)關(guān)注根據(jù)key定位到數(shù)據(jù)進(jìn)行刪除的整個(gè)流程。
先來看這個(gè)過程的流程圖，其實(shí)很簡(jiǎn)單，包括以下幾個(gè)按部就班的步驟：
a) 首先，根據(jù)key查找對(duì)應(yīng)的記錄，這個(gè)在上一節(jié)已經(jīng)完整的介紹過了，當(dāng)時(shí)也提到，查找操作是后續(xù)進(jìn)行刪除和插入新數(shù)據(jù)時(shí)的基礎(chǔ)。
如果沒有找到記錄，說明原來就沒有，那么就不必繼續(xù)下去了。
假設(shè)現(xiàn)在找到了所要?jiǎng)h除的數(shù)據(jù)，接著以下幾步：
b) 將該記錄的magic number置為0xb0，第一節(jié)講解hash數(shù)據(jù)庫概述的時(shí)候提到過，每條記錄的頭部信息中有兩種不同magic number，根據(jù)這個(gè)判斷一條記錄是否被刪除了，現(xiàn)在將這個(gè)magic number置為0xb0就是表示這條記錄已經(jīng)被刪除了。
c) 將這條被刪除的記錄插入到free pool數(shù)組中的合適位置，這是下一節(jié)的重點(diǎn)，這里先知道這個(gè)操作就好。
d) 上一節(jié)提到過，同一個(gè)bucket index是以二叉樹形式組織在一起的，雖然不是平衡的二叉樹，但是刪除了一個(gè)數(shù)據(jù)之后會(huì)破壞二叉樹的性質(zhì)，所以需要在二叉樹中找到合適的記錄來替換刪除這條記錄之后剩下的位置。
熟悉數(shù)據(jù)結(jié)構(gòu)與算法的都知道，一個(gè)排序二叉樹如果按照中序遍歷的話，那么是有序的。所以要在刪除一個(gè)記錄之后仍然保持排序二叉樹的有序性，是刪除操作的重點(diǎn)，下面就是TC中刪除一個(gè)記錄時(shí)的調(diào)整算法：
if rec.left is not null and rec.right is null
child = rec.left
else if rec.left is null and rec.right is not null
child = rec.right
else if rec.left is null and rec.right is null
child = null
else
child = rec.left
right = rec.right
rec.right = child
while (rec.right is not null)
rec = rec.right
rec.right = right
replace rec's original place with child
也可以從下圖中來理解當(dāng)刪除一個(gè)記錄時(shí)，它的左右子節(jié)點(diǎn)都不為空時(shí)的處理：
從圖中可以看出，當(dāng)所要?jiǎng)h除的節(jié)點(diǎn)左右子節(jié)點(diǎn)都不為空時(shí)，會(huì)去尋找左子樹中的最右邊的子節(jié)點(diǎn)，然后將待刪除記錄的右子樹變成這個(gè)最右子節(jié)點(diǎn)的右子樹。
需要注意到的是，經(jīng)典的數(shù)據(jù)結(jié)構(gòu)算法中，當(dāng)在排序二叉樹中刪除一個(gè)節(jié)點(diǎn)之后，所做的調(diào)整與上面的流程有所不同，雖然也是找到的原記錄的左子樹的最右節(jié)點(diǎn)，但是是將這個(gè)最右節(jié)點(diǎn)直接替換掉原來記錄的位置，也就是如下圖：
所以，這里出現(xiàn)了一個(gè)新的問題，TC中的調(diào)整算法是有可能導(dǎo)致刪除記錄之后二叉樹不平衡的，那么為什么不選用第二種方法呢？
我的理解是：
1） 如前一節(jié)所述，TC中的二叉樹本來就不是必然平衡的，所以TC中的這種調(diào)整算法有可能會(huì)有“負(fù)負(fù)得正”的結(jié)果。
2）第二種經(jīng)典的做法中，需要的調(diào)整包括：a）將最右子節(jié)點(diǎn)從原來的父節(jié)點(diǎn)上刪除 b）最右子節(jié)點(diǎn)要替換原記錄的位置，那么要將原記錄的左右子樹分別賦值變?yōu)樽钣易庸?jié)點(diǎn)的左右子樹。上面的這個(gè)調(diào)整，每次調(diào)整都是需要修改節(jié)點(diǎn)的，而每次修改都會(huì)有對(duì)磁盤的I/O操作。
而第一種做法呢，僅需要一次修改操作-----將原記錄的右子樹變成最右子節(jié)點(diǎn)的右子樹即可。
綜合這幾個(gè)因素，TC選擇了I/O較少的做法。
我不清楚我的理解是否合理，歡迎補(bǔ)充。
e）刪除了記錄，也跳整了樹的結(jié)構(gòu)之后，最后的工作就是更新數(shù)據(jù)庫文件header的信息---因?yàn)楫?dāng)前記錄少了一條。
最后分析一下整個(gè)刪除操作的最壞復(fù)雜度，還是以1G的bucket對(duì)16G的數(shù)據(jù)庫文件記錄為例：
1）首先查找元素，前面一節(jié)說了，需要O(4)次磁盤I/O+O(1)讀取內(nèi)存
2）接著置所刪除記錄的magic number，一次磁盤I/O
3）將刪除插入到合適的free pool位置，這個(gè)下一節(jié)會(huì)提到，是在內(nèi)存中進(jìn)行的。
4）調(diào)整樹結(jié)構(gòu)，在所刪除記錄左右子樹都存在的情況下，首先要找到最右子節(jié)點(diǎn)，這又是一個(gè)O(4)的磁盤I/O操作，最后將原記錄的右子樹賦值給最右子節(jié)點(diǎn)，又是一次磁盤I/O。不過，上面這個(gè)推斷與前面是有矛盾的，假如在第一步查找中已經(jīng)需要O(4)的代價(jià)才能定位到所刪除元素了，那么最后的這個(gè)調(diào)整根本沒有必要了。