數(shù)據(jù)結(jié)構(gòu)-樹

原文地址: https://blog.wangriyu.wang/2018/06-Tree.html

與數(shù)據(jù)庫相關(guān)的樹結(jié)構(gòu)主要為 B 類樹，B 類樹通常用于數(shù)據(jù)庫和操作系統(tǒng)的文件系統(tǒng)

在學(xué)習(xí) B 類樹之前先復(fù)習(xí)一下二叉查找樹的概念和紅黑樹

二叉樹

二叉樹 - Binary Tree 是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支（即不存在分支度大于 2 的節(jié)點(diǎn)）的樹結(jié)構(gòu)目养。

分類

  • 完美二叉樹 (Perfect Binary Tree): 除了葉子結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子，每一層(當(dāng)然包含最后一層)都被完全填充
  • 完全二叉樹 (Complete Binary Tree): 除了最后一層之外的其他每一層都被完全填充，并且所有結(jié)點(diǎn)都保持向左對(duì)齊
  • 滿二叉樹 (Full/Strictly Binary Tree): 除了葉子結(jié)點(diǎn)之外的每一個(gè)結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)

遍歷

  • 前序遍歷: 首先訪問根結(jié)點(diǎn)然后遍歷左子樹涩赢，最后遍歷右子樹冀惭。在遍歷左染坯、右子樹時(shí)，仍然先訪問根結(jié)點(diǎn)倚评，然后遍歷左子樹浦徊，最后遍歷右子樹
  • 中序遍歷: 首先遍歷左子樹，然后訪問根結(jié)點(diǎn)天梧，最后遍歷右子樹盔性。在遍歷左、右子樹時(shí)呢岗，仍然先遍歷左子樹冕香，再訪問根結(jié)點(diǎn)，最后遍歷右子樹
  • 后序遍歷: 首先遍歷左子樹后豫，然后遍歷右子樹悉尾，最后訪問根結(jié)點(diǎn)。在遍歷左挫酿、右子樹時(shí)焕襟，仍然先遍歷左子樹，然后遍歷右子樹饭豹，最后遍歷根結(jié)點(diǎn)
  • 深度優(yōu)先搜索: 顧名思義鸵赖，查找時(shí)深度優(yōu)先，從根結(jié)點(diǎn)訪問最遠(yuǎn)的結(jié)點(diǎn)直到找到所有節(jié)點(diǎn)拄衰。前序它褪，中序和后序遍歷都是深度優(yōu)先遍歷的特例
  • 廣度優(yōu)先搜索: 廣度優(yōu)先遍歷會(huì)先訪問離根節(jié)點(diǎn)最近的節(jié)點(diǎn)，二叉樹的廣度優(yōu)先遍歷又稱按層次遍歷翘悉。算法借助隊(duì)列實(shí)現(xiàn)

二叉查找樹

二叉查找樹 - Binary Search Tree: 也稱二叉搜索樹茫打、有序二叉樹。對(duì)于根樹和所有子樹都滿足，每個(gè)節(jié)點(diǎn)都大于左子樹元素老赤，而小于右子樹元素轮洋，且沒有鍵值相等的結(jié)點(diǎn)

搜索、插入抬旺、刪除的復(fù)雜度等于樹高弊予，期望 O(\log_2^n)，最壞 O(n)（數(shù)列有序开财，樹退化成線性表）

二叉查找樹動(dòng)態(tài)展示: https://visualgo.net/zh/bst

缺陷

當(dāng)數(shù)據(jù)基本有序時(shí)汉柒，二叉查找樹會(huì)退化成線性表，查找效率嚴(yán)重下降

所以后面出現(xiàn)了很多改進(jìn)的平衡樹結(jié)構(gòu)以滿足樹高最壞也為 O(\log_2^n)责鳍，
如伸展樹 (Splay Tree)碾褂、平衡二叉樹 (SBT)、AVL 樹历葛、紅黑樹等

紅黑樹

紅黑樹 - Red–black tree 是一種自平衡二叉查找樹正塌，除了符合二叉查找樹的性質(zhì)外，它還滿足以下五條性質(zhì):

  1. 每個(gè)結(jié)點(diǎn)要么是紅的恤溶，要么是黑的
  2. 根結(jié)點(diǎn)是黑的
  3. 每個(gè)葉子結(jié)點(diǎn)是黑的（葉子結(jié)點(diǎn)指樹尾端 NIL 指針或 NULL 結(jié)點(diǎn)传货，不包含數(shù)據(jù)，只充當(dāng)樹在此結(jié)束的指示）
  4. 如果一個(gè)結(jié)點(diǎn)是紅的宏娄，那么它的兩個(gè)子節(jié)點(diǎn)都是黑的 (從根到每個(gè)葉子的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
  5. 對(duì)于任一結(jié)點(diǎn)而言问裕，其到葉結(jié)點(diǎn)樹尾端 NIL 指針的每一條路徑都包含相同數(shù)目的黑結(jié)點(diǎn)

[圖片上傳失敗...(image-4796e2-1545273869084)]

平衡優(yōu)勢(shì)

上述約束確保了紅黑樹的關(guān)鍵特性: 從根到葉子的最長路徑不會(huì)超過最短路徑的兩倍

證明: 主要看性質(zhì) 4 和 性質(zhì) 5，假設(shè)從根到葉子的最短路徑 a 上有黑色節(jié)點(diǎn) n 個(gè)孵坚，最長路徑 b 肯定是交替的紅色和黑色節(jié)點(diǎn)粮宛，而根據(jù)性質(zhì) 5 可知從根到葉子的所有路徑都有相同數(shù)目的黑色節(jié)點(diǎn)，
這就表明 b 的黑色節(jié)點(diǎn)也為 n 個(gè)卖宠，但 b 出現(xiàn)的紅色節(jié)點(diǎn)不可能超過黑色節(jié)點(diǎn)個(gè)數(shù)巍杈，否則會(huì)破壞性質(zhì) 4 (抽屜原理)，所以從根到葉子的最長路徑不會(huì)超過最短路徑的兩倍

調(diào)整

因?yàn)槊恳粋€(gè)紅黑樹也是一個(gè)特化的二叉查找樹扛伍，因此紅黑樹上的只讀操作與普通二叉查找樹上的只讀操作相同筷畦。然而，在紅黑樹上進(jìn)行插入操作和刪除操作會(huì)導(dǎo)致不再匹配紅黑樹的性質(zhì)刺洒。
恢復(fù)紅黑樹的性質(zhì)需要少量 O(\log_2^n) 的顏色變更（實(shí)際是非潮畋觯快速的）和不超過三次樹旋轉(zhuǎn)（對(duì)于插入操作是兩次）。雖然插入和刪除很復(fù)雜逆航，但操作時(shí)間仍可以保持為 O(\log_2^n) 次鼎文。

紅黑樹發(fā)生變更時(shí)需要 [變色] 和 [旋轉(zhuǎn)] 來調(diào)整，其中旋轉(zhuǎn)又分 [左旋] 和 [右旋]因俐。

  • 變色就是更改顏色
  • 左旋: 以 X 為支點(diǎn)逆時(shí)針旋轉(zhuǎn)紅黑樹的兩個(gè)節(jié)點(diǎn) X-Y拇惋，使得父節(jié)點(diǎn)被自己的右孩子取代周偎，而自己下降為左孩子

[圖片上傳失敗...(image-865975-1545273869084)]

  • 右旋: 以 X 為支點(diǎn)順時(shí)針旋轉(zhuǎn)紅黑樹的兩個(gè)節(jié)點(diǎn) X-Y，使得父節(jié)點(diǎn)被自己的左孩子取代撑帖，而自己下降為右孩子

[圖片上傳失敗...(image-a67ea6-1545273869084)]

旋轉(zhuǎn)過程中只需要做三次指針變更就行

插入和刪除

插入節(jié)點(diǎn)

插入節(jié)點(diǎn)的位置跟二叉查找樹的尋找方法基本一致蓉坎，如果插入結(jié)點(diǎn) z 小于當(dāng)前遍歷到的結(jié)點(diǎn)，則到當(dāng)前結(jié)點(diǎn)的左子樹中繼續(xù)查找胡嘿，如果 z 大于當(dāng)前結(jié)點(diǎn)蛉艾，則到當(dāng)前結(jié)點(diǎn)的右子樹中繼續(xù)查找，
如果 z 依然比此刻遍歷到的新的當(dāng)前結(jié)點(diǎn)小灶平，則 z 作為當(dāng)前結(jié)點(diǎn)的左孩子伺通，否則作為當(dāng)前結(jié)點(diǎn)的右孩子箍土。而紅黑樹插入節(jié)點(diǎn)后逢享，為了保持約束還需要進(jìn)行調(diào)整修復(fù)(變色加旋轉(zhuǎn))。

所以插入步驟如下: 紅黑樹按二叉查找樹的規(guī)則找到位置后插入新節(jié)點(diǎn) z吴藻，z 的左孩子瞒爬、右孩子都是葉子結(jié)點(diǎn) nil， z 結(jié)點(diǎn)初始都為紅色沟堡，再根據(jù)下述情形進(jìn)行變色旋轉(zhuǎn)等操作侧但，最后達(dá)到平衡。

  • 情形 1: 如果當(dāng)前節(jié)點(diǎn)是根結(jié)點(diǎn)航罗，為滿足性質(zhì) 2禀横，所以直接把此結(jié)點(diǎn) z 涂為黑色
  • 情形 2: 如果當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是黑色，由于不違反性質(zhì) 2 和性質(zhì) 4粥血，紅黑樹沒有被破壞柏锄，所以此時(shí)也是什么也不做

比如上圖插入 12 時(shí)滿足情形 2:

[圖片上傳失敗...(image-f4d607-1545273869084)]

以下情形需要作出額外調(diào)整:

  • 情形 3: 如果當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色且祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)(叔叔結(jié)點(diǎn))是紅色
  • 情形 4: 當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色，叔叔結(jié)點(diǎn)是黑色或者 nil复亏，當(dāng)前結(jié)點(diǎn)相對(duì)其父結(jié)點(diǎn)的位置和父節(jié)點(diǎn)相對(duì)祖父節(jié)點(diǎn)的位置不在同側(cè)
  • 情形 5: 當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色趾娃，叔叔結(jié)點(diǎn)是黑色或者 nil，當(dāng)前結(jié)點(diǎn)相對(duì)其父結(jié)點(diǎn)的位置和父節(jié)點(diǎn)相對(duì)祖父節(jié)點(diǎn)的位置在同側(cè)

下面著重講講后三種情況如何調(diào)整

情形 3

當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色且祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)(叔叔結(jié)點(diǎn))是紅色

因?yàn)楫?dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色缔御，所以父節(jié)點(diǎn)不可能是根節(jié)點(diǎn)抬闷，當(dāng)前節(jié)點(diǎn)肯定有祖父節(jié)點(diǎn)，也就有叔叔節(jié)點(diǎn)

解決步驟: 將當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)和叔叔結(jié)點(diǎn)涂黑耕突，祖父結(jié)點(diǎn)涂紅笤成，再把祖父結(jié)點(diǎn)當(dāng)做新節(jié)點(diǎn)(即當(dāng)前節(jié)點(diǎn)的指針指向祖父節(jié)點(diǎn))重新檢查各種情形進(jìn)行調(diào)整

由于對(duì)稱性，不管父結(jié)點(diǎn)是祖父結(jié)點(diǎn)的左子還是右子眷茁，當(dāng)前結(jié)點(diǎn)是其父結(jié)點(diǎn)的左子還是右子仆邓，處理都是一樣的

我們插入 21 這個(gè)元素，當(dāng)前節(jié)點(diǎn)指向 21：

[圖片上傳失敗...(image-43889e-1545273869084)]

此時(shí)會(huì)發(fā)現(xiàn) 21询枚、22 兩個(gè)紅色相連與性質(zhì) 4 沖突腿箩，但 21 節(jié)點(diǎn)滿足情形 3挣磨，修復(fù)后:

[圖片上傳失敗...(image-f5864e-1545273869084)]

此時(shí)當(dāng)前節(jié)點(diǎn)指向 21 的祖父節(jié)點(diǎn)，即 25荤懂。而 25 節(jié)點(diǎn)同樣遇到情形 3 的問題茁裙，繼續(xù)修復(fù):

[圖片上傳失敗...(image-6402bf-1545273869084)]

此時(shí)當(dāng)前節(jié)點(diǎn)指向根節(jié)點(diǎn)，滿足情形 1节仿，將 14 節(jié)點(diǎn)涂黑即可恢復(fù)紅黑樹平衡

情形 4

當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色晤锥，叔叔結(jié)點(diǎn)是黑色或者 nil，當(dāng)前結(jié)點(diǎn)相對(duì)其父結(jié)點(diǎn)的位置和父節(jié)點(diǎn)相對(duì)祖父節(jié)點(diǎn)的位置不在同側(cè)

解決步驟:

  • 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子廊宪，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左子矾瘾，以當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)做為新結(jié)點(diǎn)(即當(dāng)前節(jié)點(diǎn)的指針指向父節(jié)點(diǎn))，并作為支點(diǎn)左旋
  • 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子箭启，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右子壕翩，以當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)做為新結(jié)點(diǎn)(即當(dāng)前節(jié)點(diǎn)的指針指向父節(jié)點(diǎn))，并作為支點(diǎn)右旋

在上圖的基礎(chǔ)上我們繼續(xù)插入 5 這個(gè)元素:

[圖片上傳失敗...(image-8c35a8-1545273869084)]

可以看出 5 是父節(jié)點(diǎn)的左子傅寡，而父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右子放妈，不同側(cè)則為情形 4，將當(dāng)前節(jié)點(diǎn)指向 5 的父節(jié)點(diǎn) 6荐操，并以 6 為支點(diǎn)進(jìn)行右旋:

[圖片上傳失敗...(image-bc915a-1545273869084)]

此時(shí)當(dāng)前節(jié)點(diǎn)是 6芜抒，而 6 是父節(jié)點(diǎn) 5 的右子，父節(jié)點(diǎn) 5 也是祖父節(jié)點(diǎn) 1 的右子托启，同側(cè)則轉(zhuǎn)為情形 5宅倒，繼續(xù)往下看

情形 5

當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)是紅色，叔叔結(jié)點(diǎn)是黑色或者 nil屯耸，當(dāng)前結(jié)點(diǎn)相對(duì)其父結(jié)點(diǎn)的位置和父節(jié)點(diǎn)相對(duì)祖父節(jié)點(diǎn)的位置在同側(cè)

解決步驟:

  • 首先把父結(jié)點(diǎn)變?yōu)楹谏涨ǎ娓附Y(jié)點(diǎn)變?yōu)榧t色
  • 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左子，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左子肩民，以祖父結(jié)點(diǎn)為支點(diǎn)右旋
  • 如果當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右子唠亚，父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右子，以祖父結(jié)點(diǎn)為支點(diǎn)左旋

在上一張圖的基礎(chǔ)上修改節(jié)點(diǎn) 5 為黑色持痰，節(jié)點(diǎn) 1 為紅色灶搜，再以 1 為支點(diǎn)左旋:

[圖片上傳失敗...(image-65ef52-1545273869084)]

此時(shí)便恢復(fù)平衡

刪除節(jié)點(diǎn)

刪除節(jié)點(diǎn) X 時(shí)第一步先判斷兩個(gè)孩子是否都是非空的，如果都非空工窍，就先按二叉查找樹的規(guī)則處理:

在刪除帶有兩個(gè)非空子樹的節(jié)點(diǎn) X 的時(shí)候割卖，我們可以找到左子樹中的最大元素(或者右子樹中的最小元素)，并把這個(gè)最值復(fù)制給 X 節(jié)點(diǎn)患雏，只代替原來要?jiǎng)h除的值鹏溯，不改變節(jié)點(diǎn)顏色。

然后我們只要?jiǎng)h除那個(gè)被復(fù)制出值的那個(gè)節(jié)點(diǎn)就行淹仑，因?yàn)槭亲钪倒?jié)點(diǎn)所以它的孩子不可能都非空丙挽。

因?yàn)橹皇菑?fù)制了一個(gè)值肺孵，不違反任何性質(zhì)，這就把原問題轉(zhuǎn)化為如何刪除最多有一個(gè)非空子樹的節(jié)點(diǎn)的問題颜阐。它不關(guān)心這個(gè)節(jié)點(diǎn)是最初要?jiǎng)h除的節(jié)點(diǎn)還是被復(fù)制出值的那個(gè)節(jié)點(diǎn)平窘。

我們以圖為例，圖中三角形代表可能為空的子樹:

[圖片上傳失敗...(image-b6ffa6-1545273869084)]

節(jié)點(diǎn) X 是要?jiǎng)h除的節(jié)點(diǎn)凳怨，發(fā)現(xiàn)它的兩個(gè)子樹非空瑰艘，我們可以找左子樹中最大的元素 Max (也可以找右子樹中最小的元素 Min)，把 Max 值(或者 Min 值)復(fù)制到 X 上覆蓋原來的值肤舞，不修改其他屬性紫新，然后刪除 Max 節(jié)點(diǎn)(或 Min 節(jié)點(diǎn))即可，可以很清楚的看到最值節(jié)點(diǎn)最多只會(huì)有一個(gè)非空子樹

接下來就是如何處理刪除最多有一個(gè)非空子樹的節(jié)點(diǎn) X 的問題

簡單情形:

  1. 如果 X 的兩個(gè)兒子都為空李剖，即均為葉子芒率，我們將其中任意一個(gè)看作它的兒子
  2. 如果 X 是一個(gè)紅色節(jié)點(diǎn)，它的父親和兒子一定是黑色的杖爽，所以簡單的用它的黑色兒子替換它就行敲董，這并不會(huì)破壞性質(zhì) 3 和性質(zhì) 4紫皇，通過被刪除節(jié)點(diǎn)的所有路徑只是少了一個(gè)紅色節(jié)點(diǎn)慰安，這樣可以繼續(xù)保證性質(zhì) 5
  3. 如果 X 是黑色而它的兒子是紅色，如果只是刪除這個(gè)黑色節(jié)點(diǎn)聪铺，用它的紅色兒子代替的話化焕，會(huì)破壞性質(zhì) 5，我們可以重繪它的兒子為黑色铃剔，則曾經(jīng)通過 X 的所有路徑將通過它的黑色兒子撒桨，這樣可以繼續(xù)保持性質(zhì) 5

如果 X 和它的兒子都是黑色，這是一種復(fù)雜的情況键兜，我們單拎出來講

我們首先把要?jiǎng)h除的節(jié)點(diǎn) X 替換為它的兒子凤类。出于方便，稱呼這個(gè)新上位的兒子為 N普气，稱呼它的兄弟為 S谜疤，使用 P 稱呼 N 的新父親，SL 稱呼 S 的左兒子现诀，SR 稱呼 S 的右兒子

有以下六種情形需要考慮:

情形 1

N 是新的根

我們不需要做什么夷磕，因?yàn)樗新窂蕉既コ艘粋€(gè)黑色節(jié)點(diǎn)，而新根也是黑色的仔沿，所以性質(zhì)都保持著

情形 2坐桩、5、6 涉及到左右不同的情況封锉，只取一種處理

情形 2

S 是紅色

  • 交換兄弟 S 和父親 P 的顏色
  • 如果 N 是其父親的左節(jié)點(diǎn)绵跷，我們?cè)?N 的父親上做左旋膘螟，把紅色兄弟轉(zhuǎn)換成 N 的祖父
  • 如果 N 是其父親的右節(jié)點(diǎn)，我們?cè)?N 的父親上做右旋碾局，把紅色兄弟轉(zhuǎn)換成 N 的祖父

[圖片上傳失敗...(image-45d067-1545273869084)]

完成這兩個(gè)操作后萍鲸，盡管所有路徑上黑色節(jié)點(diǎn)的數(shù)目沒有改變，但現(xiàn)在 N 有了一個(gè)黑色的兄弟和一個(gè)紅色的父親擦俐，所以我們可以接下去按情形 4脊阴、情形 5 或情形 6 來處理

情形 3

N 的父親、S 和 S 的兒子都是黑色的

  • 重繪 S 為紅色
  • 將 P 作為新的 N蚯瞧，從情形 1 開始嘿期，在 P 上做平衡處理

[圖片上傳失敗...(image-7d1251-1545273869084)]

在這種情形下，我們簡單的重繪 S 為紅色埋合。結(jié)果是通過 S 的所有路徑都少了一個(gè)黑色節(jié)點(diǎn)备徐。這與刪除 N 的初始父親 X 造成通過 N 的所有路徑少了一個(gè)黑色節(jié)點(diǎn)達(dá)成平衡。但是甚颂，通過 P 的所有路徑現(xiàn)在比不通過 P 的路徑少了一個(gè)黑色節(jié)點(diǎn)蜜猾，所以仍然違反性質(zhì) 5。要修正這個(gè)問題振诬，我們要從情形 1 開始蹭睡，在 P 上做重新平衡處理

情形 4

S 和 S 的兒子都是黑色，但是 N 的父親是紅色

  • 交換 N 的兄弟 S 和父親 P 的顏色

[圖片上傳失敗...(image-317820-1545273869084)]

在這種情形下赶么，我們簡單的交換 N 的兄弟和父親的顏色肩豁。這不影響不通過 N 的路徑的黑色節(jié)點(diǎn)的數(shù)目，但是它在通過 N 的路徑上對(duì)黑色節(jié)點(diǎn)數(shù)目增加了一辫呻，添補(bǔ)了在這些路徑上刪除的黑色節(jié)點(diǎn)

情形 5

S 是黑色清钥，S 的其中一個(gè)兒子是紅色，且紅色兒子的位置與 N 相對(duì)于父親的位置處于同側(cè)

  • 如果 N 是其父親的左節(jié)點(diǎn)放闺，S 的左兒子是紅色祟昭，右兒子是黑色，則在 S 上做右旋轉(zhuǎn)
  • 如果 N 是其父親的右節(jié)點(diǎn)怖侦，S 的左兒子是黑色篡悟，右兒子是紅色，則在 S 上做左旋轉(zhuǎn)
  • 將 S 和它之前的紅色兒子交換顏色

[圖片上傳失敗...(image-836dbd-1545273869084)]

所有路徑仍有同樣數(shù)目的黑色節(jié)點(diǎn)础钠，但是現(xiàn)在 N 有了一個(gè)黑色兄弟恰力，且兄弟的一個(gè)兒子仍為紅色的，其位置與 N 相對(duì)于父親的位置處于不同側(cè)旗吁，進(jìn)入情形 6

情形 5踩萎、6 中父節(jié)點(diǎn) P 的顏色可以為黑色也可以是紅色

情形 6

S 是黑色，S 的其中一個(gè)兒子是紅色很钓，且其位置與 N 相對(duì)于父親的位置處于不同側(cè)

  • 交換 N 的父親 P 和 S 的顏色
  • 如果 N 是其父親的右節(jié)點(diǎn)香府，S 的左兒子是紅色董栽，右兒子是黑色，則在 N 的父親上做右旋轉(zhuǎn)企孩，并使 S 的左兒子涂黑
  • 如果 N 是其父親的左節(jié)點(diǎn)锭碳，S 的左兒子是黑色，右兒子是紅色勿璃，則在 N 的父親上做左旋轉(zhuǎn)擒抛，并使 S 的右兒子涂黑

[圖片上傳失敗...(image-aa5efa-1545273869084)]

交換前 N 的父親可以是紅色也可以是黑色，交換后补疑，N 增加了一個(gè)黑色祖先歧沪，所以通過 N 的路徑都增加了一個(gè)黑色節(jié)點(diǎn)，S 的右子樹黑色節(jié)點(diǎn)個(gè)數(shù)也沒有變化莲组，達(dá)到平衡

實(shí)例

還是以之前的圖為例

[圖片上傳失敗...(image-afca5f-1545273869084)]

我們自下而上開始嘗試刪除每一個(gè)節(jié)點(diǎn):

  • 假如要?jiǎng)h除元素 1诊胞，根據(jù)簡單情形中的第二條，我們直接刪除 1锹杈，并用一個(gè) nil 節(jié)點(diǎn)代替即可撵孤，元素 6、12竭望、21 的處理與此相同

  • 假如要?jiǎng)h除元素 5邪码，因?yàn)樽笥易訕渚粸榭眨哉易笞訕涞淖畲笾?1 (或者右子樹的最小值 6)市框，用找到的值代替 5 (這里只是值替換霞扬，其他均不變)糕韧，然后去刪除 1 節(jié)點(diǎn)枫振，這就轉(zhuǎn)到問題 1 上了

  • 假如要?jiǎng)h除元素 11，根據(jù)簡單情形的第三條萤彩，我們直接刪除 11粪滤，并用子節(jié)點(diǎn) 12 代替，同時(shí)把 12 涂黑即可雀扶，元素 22 的處理與此相同

  • 假如要?jiǎng)h除元素 25杖小，因?yàn)樽笥易訕渚粸榭眨哉易笞訕涞淖畲笾?22 (或者右子樹的最小值 27)愚墓，我們這里用值 22 代替 25予权，顏色不變。然后去刪除 22 節(jié)點(diǎn)浪册，這變成上一個(gè)問題了

  • 假如要?jiǎng)h除元素 27扫腺，黑色的 nil 葉子節(jié)點(diǎn)代替 27 節(jié)點(diǎn)，因?yàn)樾值芄?jié)點(diǎn) 22 有一個(gè)紅色孩子村象，且在左邊笆环，和 nil 節(jié)點(diǎn)相對(duì)父親 25 的位置不同側(cè)攒至，屬于情形 6，所以第一步交換 22 和 25 的顏色躁劣，再以 25 為支點(diǎn)做右旋轉(zhuǎn)迫吐，然后將 21 節(jié)點(diǎn)涂黑即可

  • 假如要?jiǎng)h除元素 8，選擇右子樹最小值 11 替換 8账忘。然后去刪除節(jié)點(diǎn) 11志膀，對(duì)應(yīng)問題 3

  • 假如要?jiǎng)h除元素 17，選擇左子樹最大值 15 替換 17鳖擒。然后去刪除節(jié)點(diǎn) 15梧却，過程看下一個(gè)問題

  • 假如要?jiǎng)h除元素 15，刪除的元素和替代的元素都是黑色败去，這屬于復(fù)雜情形放航。檢查其類型可以匹配到情形 2，元素 15 是被移除的 X圆裕，代替它的是 nil 節(jié)點(diǎn)广鳍，即為 N，17 為 P吓妆，25 為 S赊时，根據(jù)上文可知第一步先交換 P 和 S 的顏色，然后以 P 為支點(diǎn)進(jìn)行左旋行拢，此時(shí) N 多了一個(gè)黑色的兄弟 22 和紅色的父親 17:

[圖片上傳失敗...(image-c04a29-1545273869084)]

此時(shí) N 的兄弟 S 變?yōu)?22祖秒，P 變?yōu)?17，S 的左孩子是紅色的 21舟奠，屬于情形 5竭缝。S 做右旋轉(zhuǎn)，并交換 22 和 21 的顏色:

[圖片上傳失敗...(image-a0355b-1545273869084)]

此時(shí) N 的兄弟 S 變?yōu)楹谏?21沼瘫，但 21 的紅色孩子節(jié)點(diǎn) 22 變?yōu)橛覀?cè)抬纸，進(jìn)入情形 6

[圖片上傳失敗...(image-e86c3d-1545273869084)]

P 節(jié)點(diǎn) 17 做左旋轉(zhuǎn)，并將 S 的右節(jié)點(diǎn)涂黑耿戚，此時(shí)樹恢復(fù)平衡

  • 假如要?jiǎng)h除根節(jié)點(diǎn) 14湿故，取左子樹最大值 12 代替 14。然后去刪除節(jié)點(diǎn) 12膜蛔，對(duì)應(yīng)問題 1

至此坛猪，我們已經(jīng)把節(jié)點(diǎn)都刪了個(gè)遍，相信你對(duì)紅黑樹的刪除操作應(yīng)該了解了

紅黑樹動(dòng)態(tài)展示: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

實(shí)際問題

紅黑樹還是典型的二叉搜索樹結(jié)構(gòu)皂股，主要應(yīng)用在一些 map 和 set 類型的實(shí)現(xiàn)上墅茉，比如 Java 中的 TreeMap 和 C++ 的 set/map/multimap 等。其查找的時(shí)間復(fù)雜度 O(\log_2^n) 與樹的深度相關(guān)，降低樹的深度可以提高查找效率躁锁。

Java 的 hashmap 和 golang 的 map 是用哈希實(shí)現(xiàn)的

但是大規(guī)模數(shù)據(jù)存儲(chǔ)中纷铣，實(shí)現(xiàn)索引查詢這樣一個(gè)實(shí)際背景下，樹節(jié)點(diǎn)存儲(chǔ)的元素?cái)?shù)量是有限的（如果元素?cái)?shù)量非常多的話战转，查找就退化成節(jié)點(diǎn)內(nèi)部的線性查找了）搜立，
這樣導(dǎo)致二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤 I/O 讀寫過于頻繁，進(jìn)而導(dǎo)致查詢效率低下槐秧，因此我們?cè)撓朕k法降低樹的深度啄踊，從而減少磁盤查找存取的次數(shù)。

一個(gè)基本的思想就是：采用多叉樹結(jié)構(gòu)刁标，所以出現(xiàn)了下述的平衡多路查找樹

B 樹 (B - Tree)

B-樹颠通，即為 B 樹，不要讀作 B 減樹

B 樹與紅黑樹最大的不同在于膀懈，B 樹的結(jié)點(diǎn)可以有許多子女顿锰，從幾個(gè)到幾千個(gè)。

定義

B 樹的定義有兩種启搂，一種以階數(shù)為限制的 B 樹(下文所述的)硼控，一種以度數(shù)為限制的 B 樹(算法導(dǎo)論所描述的)，兩者原理類似胳赌，這里以階數(shù)來定義

B 樹屬于平衡多路查找樹牢撼。一棵 m 階(m 階即代表樹中任一結(jié)點(diǎn)最多含有 m 個(gè)孩子)的 B 樹的特性如下:

  1. 除根節(jié)點(diǎn)外所有節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)范圍: [\lceil\frac m2\rceil-1, m-1]
  2. 若非葉子節(jié)點(diǎn)含 n 個(gè)關(guān)鍵字，則子樹有 n+1 個(gè)疑苫，由關(guān)鍵字范圍可知子樹的個(gè)數(shù)范圍: [\lceil\frac m2\rceil, m]
  3. 根節(jié)點(diǎn)至少包含一個(gè)關(guān)鍵字熏版，至少有兩個(gè)孩子(除非 B 樹只存在一個(gè)節(jié)點(diǎn): 根結(jié)點(diǎn))，即根節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)范圍: [1, m-1]捍掺，孩子數(shù)范圍: [2, m]
  4. 所有葉子節(jié)點(diǎn)都處在同一層撼短，即高度都一樣
  5. 每個(gè)節(jié)點(diǎn)中的關(guān)鍵字從小到大排列，節(jié)點(diǎn)當(dāng)中 k-1 個(gè)元素正好是 k 個(gè)孩子包含的元素的值域劃分

[圖片上傳失敗...(image-60ffca-1545273869084)]

如圖是一個(gè)典型的 2-3-4 樹結(jié)構(gòu)乡小，也是階為 4 的 B 樹阔加。從圖中查詢?cè)刈疃嘀恍枰?3 次磁盤 I/O 就可以訪問到我們需要的數(shù)據(jù)節(jié)點(diǎn)，將節(jié)點(diǎn)數(shù)據(jù)塊讀入內(nèi)存后再查找指定元素會(huì)很快满钟。如果同樣的數(shù)據(jù)用紅黑樹表示，樹高會(huì)增長很多胳喷，造成遍歷節(jié)點(diǎn)的次數(shù)增多湃番，訪問磁盤的次數(shù)增多，查找性能會(huì)下降吭露。

對(duì)于一棵包含 n 個(gè)元素吠撮、高度為 h 、階數(shù)為 m 的 B 樹:
影響 B 樹高度的是每個(gè)結(jié)點(diǎn)所包含的子樹數(shù)讲竿，如果盡可能使結(jié)點(diǎn)孩子數(shù)都等于 \lceil\frac m2\rceil泥兰，則層數(shù)最多弄屡，為最壞情況；如果盡可能使結(jié)點(diǎn)孩子數(shù)都等于 m鞋诗，則層數(shù)最少膀捷，為最好情況。所以有

\log _m{(n + 1)} \leq h \leq \log _{\lceil\frac m2\rceil}{(\frac{n + 1}{2})} + 1

底數(shù) \lceil\frac m2\rceil 可以取很大削彬，比如 m 可以達(dá)到幾千全庸，從而在關(guān)鍵字?jǐn)?shù)一定的情況下，使得最終的 h 值盡量比較小融痛，樹的高度比較低壶笼。

實(shí)際運(yùn)用中 B 樹中的每個(gè)結(jié)點(diǎn)根據(jù)實(shí)際情況可以包含大量的關(guān)鍵字信息和分支(但不能超過磁盤塊的大小，根據(jù)磁盤驅(qū)動(dòng)的不同雁刷，一般塊的大小在 1k~4k 左右)覆劈；這樣樹的深度降低了，意味著查找一個(gè)元素只要很少的結(jié)點(diǎn)從外存磁盤中讀入內(nèi)存沛励，就可以很快地訪問到要查找的數(shù)據(jù)

查找

一個(gè)節(jié)點(diǎn)的結(jié)構(gòu)可以定義為:

type BTNode struct {
  KeyNum   int       // 關(guān)鍵字個(gè)數(shù)墩崩，math.Ceil(m/2)-1 <= KeyNum < 階數(shù) m
  Parent   *BTNode   // 指向父節(jié)點(diǎn)的指針
  IsLeaf   bool      // 是否為葉子，葉子節(jié)點(diǎn) children 為 nil
  Key      []int     // 關(guān)鍵字切片侯勉，長度為 KeyNum
  Children []*BTNode // 子節(jié)點(diǎn)指針切片鹦筹，長度為 KeyNum+1
}

以上面 2-3-4 樹的根節(jié)點(diǎn)為例：

[圖片上傳失敗...(image-d204b0-1545273869084)]

所有數(shù)據(jù)以塊的方式存儲(chǔ)在外磁盤中，我們通過 B 樹來查找數(shù)據(jù)時(shí)址貌，每遍歷到一個(gè)節(jié)點(diǎn)铐拐，便將其讀入內(nèi)存，比較其中的關(guān)鍵字练对，若能匹配到我們要找的元素遍蟋，便返回；若未能找到螟凭，通過比較確定在哪兩個(gè)關(guān)鍵字的值域區(qū)間虚青， 即可確定子樹的節(jié)點(diǎn)指針，繼續(xù)往下找螺男，把下一個(gè)節(jié)點(diǎn)的數(shù)據(jù)讀入內(nèi)存棒厘，重復(fù)以上步驟

插入

對(duì)于一棵 m 階的 B 樹來說，插入一個(gè)元素(或者叫關(guān)鍵字)時(shí)下隧，首先判斷在 B 樹中是否已存在奢人，如果存在則不插入；如果不存在淆院，則在對(duì)應(yīng)葉子結(jié)點(diǎn)中插入新的元素何乎，需要判斷是否會(huì)超出關(guān)鍵字個(gè)數(shù)限制(m-1)

插入步驟:

  1. 根據(jù)元素大小查找插入位置，肯定是最底層的葉子節(jié)點(diǎn)，將元素插入到該節(jié)點(diǎn)中
  2. 如果葉子節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)小于等于 m-1支救，說明未超出限制抢野，插入結(jié)束；否則進(jìn)入下一步
  3. 如果葉子節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)大于 m-1 個(gè)各墨，以結(jié)點(diǎn)中間的關(guān)鍵字為中心分裂成左右兩部分指孤，然后將這個(gè)中間的關(guān)鍵字插入到父結(jié)點(diǎn)中，這個(gè)關(guān)鍵字的左子樹指向分裂后的左半部分欲主，這個(gè)關(guān)鍵字的右子樹指向分裂后的右半部分邓厕。
  4. 然后將當(dāng)前結(jié)點(diǎn)指向父結(jié)點(diǎn)，如果插入剛才的中間關(guān)鍵字后父節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)也超出限制扁瓢，繼續(xù)進(jìn)行第 3 步详恼；否則結(jié)束插入

還是以上面的 2-3-4 樹(階數(shù) m = 4)為例，我們依次插入元素

  • 首先插入 1引几、2昧互、3，因?yàn)殛P(guān)鍵字個(gè)數(shù)均未超過 m-1伟桅，所以直接插入即可:

[圖片上傳失敗...(image-99915a-1545273869084)]

  • 當(dāng)插入 4 時(shí)敞掘，該節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)達(dá)到 m，需要分裂楣铁，這里可以選 3 (也可以選 2) 作為中間字玖雁，分裂后:

[圖片上傳失敗...(image-46b7f4-1545273869084)]

  • 繼續(xù)插入 5、7盖腕，對(duì)應(yīng) 4 所在的葉子節(jié)點(diǎn):

[圖片上傳失敗...(image-fe774e-1545273869084)]

  • 當(dāng)插入 8 時(shí)赫冬，也需要分裂，將中間字 5 上移至父節(jié)點(diǎn)溃列，4 成為 5 的左區(qū)間子樹劲厌，7 8 成為 5 的右區(qū)間子樹:

[圖片上傳失敗...(image-c479ba-1545273869084)]

之后的步驟類似，不再一一敘述

刪除

刪除操作是指刪除 B 樹中的某個(gè)節(jié)點(diǎn)中的指定關(guān)鍵字

刪除步驟:

  1. 如果當(dāng)前要?jiǎng)h除的關(guān)鍵字位于非葉子結(jié)點(diǎn) N 上听隐，則用后繼最小關(guān)鍵字(找前繼最大關(guān)鍵字也可以)覆蓋要?jiǎng)h除的關(guān)鍵字补鼻，然后在后繼關(guān)鍵字所在的子樹中刪除該后繼關(guān)鍵字。此后繼關(guān)鍵字一定位于葉子結(jié)點(diǎn)上雅任，這個(gè)過程和二叉搜索樹刪除結(jié)點(diǎn)的方式類似风范。刪除這個(gè)后繼關(guān)鍵字后進(jìn)入第 2 步，如果原本要?jiǎng)h除的關(guān)鍵字本身就位于葉子上同樣刪除關(guān)鍵字后進(jìn)入第二步
  2. 該結(jié)點(diǎn)(假設(shè)為 M)關(guān)鍵字個(gè)數(shù)大于等于 math.Ceil(m/2)-1椿访，結(jié)束刪除操作乌企，否則進(jìn)入第 3 步
  3. 此時(shí)結(jié)點(diǎn) M 關(guān)鍵字個(gè)數(shù)小于 math.Ceil(m/2)-1
    • 如果相鄰兄弟結(jié)點(diǎn)(左右都可以)關(guān)鍵字個(gè)數(shù)大于 math.Ceil(m/2)-1，則父結(jié)點(diǎn)中取一個(gè)臨近的關(guān)鍵字下移到 M成玫，兄弟結(jié)點(diǎn)中取一個(gè)臨近關(guān)鍵字上移至父節(jié)點(diǎn)，刪除操作結(jié)束；
    • 如果相鄰的兄弟節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)都不大于 math.Ceil(m/2)-1哭当，將父結(jié)點(diǎn)中臨近的關(guān)鍵字 key 下移至 M猪腕，合并 M 和它的兄弟節(jié)點(diǎn)形成一個(gè)新的結(jié)點(diǎn)。原父結(jié)點(diǎn)中的 key 的兩個(gè)孩子指針就變成一個(gè)孩子指針钦勘，指向這個(gè)新結(jié)點(diǎn)陋葡。然后當(dāng)前結(jié)點(diǎn)的指針指向父結(jié)點(diǎn)，重復(fù)第 2 步

以上面的 2-3-4 樹為例

[圖片上傳失敗...(image-5d676e-1545273869084)]

階數(shù)為 4彻采，節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)范圍應(yīng)該是 [1, 3]腐缤，即 math.Ceil(m/2)-1 = 1

  • 刪除關(guān)鍵字 2 或者 8，不影響節(jié)點(diǎn)

[圖片上傳失敗...(image-a2745-1545273869084)]

  • 刪除關(guān)鍵字 4肛响，該葉子節(jié)點(diǎn) X 關(guān)鍵字個(gè)數(shù)變?yōu)?0 小于范圍下界岭粤，同時(shí)左右兩個(gè)相鄰兄弟的關(guān)鍵字個(gè)數(shù)都不大于 1，需要合并節(jié)點(diǎn)特笋。
    • 第一步剃浇，將父節(jié)點(diǎn)的 5 下移到 X 上
    • 第二步，合并 X 和右兄弟節(jié)點(diǎn) 7 形成一個(gè)包含 5猎物、7 的新節(jié)點(diǎn)
    • 第三步虎囚，父節(jié)點(diǎn)中原本 5 的左右兩個(gè)孩子指針變?yōu)橐粋€(gè)并指向這個(gè)新節(jié)點(diǎn)

[圖片上傳失敗...(image-4c60-1545273869084)]

這里第一步也可以選擇下移 3，然后第二步跟左兄弟合并成 1蔫磨、3 節(jié)點(diǎn)

  • 繼續(xù)刪除 1淘讥，此時(shí)與上一個(gè)問題不同，該葉子節(jié)點(diǎn)的兄弟有富余的關(guān)鍵字堤如，我們只需要把父節(jié)點(diǎn)的臨近的一個(gè)關(guān)鍵字下移到該葉子節(jié)點(diǎn)代替刪除的元素蒲列，然后把兄弟節(jié)點(diǎn)的一個(gè)臨近關(guān)鍵字上移至父節(jié)點(diǎn)即可，這個(gè)操作有點(diǎn)類似紅黑樹的左旋操作

[圖片上傳失敗...(image-55823e-1545273869084)]

  • 現(xiàn)在嘗試刪除非葉子節(jié)點(diǎn) 5煤惩，用后繼最小關(guān)鍵字 7 代替 5嫉嘀，然后刪除 7 所在的葉子節(jié)點(diǎn)。
    • 此時(shí)會(huì)引起連鎖反應(yīng)魄揉，7 所在的葉子節(jié)點(diǎn)現(xiàn)在為空剪侮，而兄弟節(jié)點(diǎn)關(guān)鍵字又不大于 1，需要合并
    • 將關(guān)鍵字 7 又從父節(jié)點(diǎn)移至原來的葉子上洛退，合并成含 3瓣俯、7 的新節(jié)點(diǎn)，假設(shè)新節(jié)點(diǎn)為 N兵怯，父節(jié)點(diǎn)的孩子指針變?yōu)橐粋€(gè)并指向 N
    • 而父節(jié)點(diǎn)現(xiàn)在關(guān)鍵字是空的彩匕，而且其兄弟(N 的叔叔)關(guān)鍵字也不大于 1，也需要合并
    • 根節(jié)點(diǎn)取出關(guān)鍵字 9 下移到 N 的父節(jié)點(diǎn)上媒区，合并 N 的父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)驼仪，產(chǎn)生一個(gè)包含 9掸犬、15 的新節(jié)點(diǎn)，根節(jié)點(diǎn)的孩子指針減少一個(gè)且左子樹指向這個(gè)新節(jié)點(diǎn)

[圖片上傳失敗...(image-cefef5-1545273869084)]

刪除操作就演示到這绪爸，B 樹的內(nèi)容講完

B 樹動(dòng)態(tài)展示: https://www.cs.usfca.edu/~galles/visualization/BTree.html

B+ 樹 (B+ - Tree)

B+ 樹 是基于 B 樹的變體湾碎，查找性能更好

同為 m 階的 B+ 樹與 B 樹的不同點(diǎn):

  1. 所有非葉子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)最多有 m 個(gè)關(guān)鍵字奠货，最少有 \lceil\frac m2\rceil 個(gè)關(guān)鍵字(比 B 樹的限制多一個(gè))介褥，其中每個(gè)關(guān)鍵字對(duì)應(yīng)一棵子樹
  2. 所有的非葉子結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹根結(jié)點(diǎn)中最大(或最小)關(guān)鍵字递惋，不包含關(guān)鍵字?jǐn)?shù)據(jù)的指針(B 樹是包含這個(gè)指針的)
  3. 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息柔滔，及指向含這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小到大順序鏈接.(而 B 樹的全部關(guān)鍵字信息分散在各個(gè)節(jié)點(diǎn)中)

[圖片上傳失敗...(image-a828c6-1545273869084)]

如圖所示的是將之前的 2-3-4 樹的數(shù)據(jù)存到 B+ 樹結(jié)構(gòu)中的示意圖萍虽，葉子節(jié)點(diǎn)保存了所有關(guān)鍵字信息并且葉子節(jié)點(diǎn)之間也用指針連接起來(一個(gè)順序鏈表)睛廊，而所有非葉子節(jié)點(diǎn)只包含子樹根節(jié)點(diǎn)中對(duì)應(yīng)的最大關(guān)鍵字，其作用只是用于索引

B+ 樹還可以用另一種形式定義:

中間節(jié)點(diǎn)最多有 m-1 個(gè)關(guān)鍵字贩挣，最少有 \lceil\frac m2\rceil-1 個(gè)關(guān)鍵字喉前，與 B 樹相同；
但是非葉子節(jié)點(diǎn)的關(guān)鍵字是左子樹的最大關(guān)鍵字(或者右子樹的最小關(guān)鍵字)王财，與剛才的情形不同

比如同樣的數(shù)據(jù)此定義的 B+ 樹表現(xiàn)形式如下:

[圖片上傳失敗...(image-eba11d-1545273869084)]

這種形式中間節(jié)點(diǎn)占用更少卵迂，可能更常見一點(diǎn)，不過下面的講解是按第一種定義來

優(yōu)勢(shì)

B+ 樹比 B 樹更適合實(shí)際應(yīng)用中操作系統(tǒng)的文件索引和數(shù)據(jù)庫索引

  1. B+ 樹索引節(jié)點(diǎn)可以存儲(chǔ)更多的關(guān)鍵字绒净，磁盤 I/O 可以更少

數(shù)據(jù)庫中關(guān)鍵字可能只是某個(gè)數(shù)據(jù)列的索引信息(比如以 ID 列創(chuàng)建的索引)见咒，而索引指向的數(shù)據(jù)記錄(某個(gè) ID 對(duì)應(yīng)的數(shù)據(jù)行)我們稱作衛(wèi)星數(shù)據(jù)，推薦看下博文 數(shù)據(jù)庫的最簡單實(shí)現(xiàn) 和 MySQL索引背后的數(shù)據(jù)結(jié)構(gòu)及算法原理

B- 樹中間節(jié)點(diǎn)和葉子節(jié)點(diǎn)都會(huì)帶有關(guān)鍵字和衛(wèi)星數(shù)據(jù)的指針挂疆，B+ 樹中間節(jié)點(diǎn)只帶有關(guān)鍵字改览，而衛(wèi)星數(shù)據(jù)的指針均放在葉子節(jié)點(diǎn)中

因?yàn)闆]有衛(wèi)星數(shù)據(jù)的指針，所以 B+ 樹內(nèi)部結(jié)點(diǎn)相對(duì) B 樹占用空間更小缤言。如果把所有同一結(jié)點(diǎn)的關(guān)鍵字存放在同一盤塊中宝当，那么對(duì)于 B+ 樹來說盤塊所能容納的關(guān)鍵字?jǐn)?shù)量也就更多，一次性讀入內(nèi)存中時(shí)能查找的關(guān)鍵字也就更多胆萧。相對(duì)來說 IO 讀寫次數(shù)也就降低了庆揩，性能就提升了。

舉個(gè)例子跌穗，假設(shè)磁盤中的一個(gè)盤塊能容納 16 bytes订晌，而一個(gè)關(guān)鍵字占 2 bytes，一個(gè)衛(wèi)星數(shù)據(jù)指針占 2bytes蚌吸。對(duì)于一棵 9 階 B 樹來說锈拨，一個(gè)結(jié)點(diǎn)最多含 8 個(gè)關(guān)鍵字(8*4 bytes)，即一個(gè)內(nèi)部結(jié)點(diǎn)需要 2 個(gè)盤塊來存儲(chǔ)羹唠。而對(duì)于 B+ 樹來說奕枢，內(nèi)部結(jié)點(diǎn)不含衛(wèi)星數(shù)據(jù)的指針娄昆，所以一個(gè)內(nèi)部節(jié)點(diǎn)只需要 1 個(gè)盤塊。當(dāng)需要把內(nèi)部結(jié)點(diǎn)讀入內(nèi)存中的時(shí)候验辞，B 樹就比 B+ 樹多一次盤塊查找時(shí)間

  1. B+ 樹的查詢效率更加穩(wěn)定

由于非葉子節(jié)點(diǎn)并不是最終指向文件內(nèi)容的結(jié)點(diǎn)稿黄，而只是葉子結(jié)點(diǎn)中關(guān)鍵字的索引喊衫。所以任何關(guān)鍵字的查找必須走一條從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑跌造。所有關(guān)鍵字查詢的路徑長度相同，導(dǎo)致每一個(gè)數(shù)據(jù)的查詢效率相當(dāng)族购。而 B 樹查找一個(gè)文件時(shí)查找到的路徑長度是不一的壳贪。

  1. B+ 樹對(duì)范圍查詢操作更友好

如果是查找單一元素，B+ 樹的查找過程與 B 樹類似寝杖，只是每次查找都是從根查到葉

而進(jìn)行范圍查詢的操作時(shí)违施，B+ 樹只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷，而 B 樹的范圍查詢要通過中序遍歷瑟幕，效率比較低下

插入

B+ 樹的插入與 B 樹類似磕蒲，先尋找關(guān)鍵字對(duì)應(yīng)的位置插入，需要注意的是插入比當(dāng)前子樹的最大關(guān)鍵字還大的數(shù)時(shí)要修改祖先節(jié)點(diǎn)對(duì)應(yīng)的關(guān)鍵字只盹，因?yàn)?B+ 樹內(nèi)部結(jié)點(diǎn)存的是子樹的最大關(guān)鍵字

比如在上面給出的 B+ 樹中插入 105 這個(gè)元素辣往，因?yàn)?105 大于當(dāng)前子樹最大關(guān)鍵字 101，所以需要修改父節(jié)點(diǎn)和祖父節(jié)點(diǎn)的邊界關(guān)鍵字:

[圖片上傳失敗...(image-2d9c24-1545273869084)]

  • 如果插入元素的節(jié)點(diǎn)未超出上界限制殖卑，則結(jié)束站削；否則將節(jié)點(diǎn)分裂，中間節(jié)點(diǎn)上移到父節(jié)點(diǎn)中孵稽，再判斷父節(jié)點(diǎn)是否需要調(diào)整

比如剛才插入 105 的葉子節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)達(dá)到 4 個(gè)许起，需要分裂，這里分裂與 B 樹略有不同菩鲜。B 樹是把節(jié)點(diǎn)按中間節(jié)點(diǎn)分成三份园细，再把中間節(jié)點(diǎn)上移；而 B+ 樹是分成兩份接校，再把左半節(jié)點(diǎn)的最大關(guān)鍵字添加進(jìn)父節(jié)點(diǎn)

[圖片上傳失敗...(image-292e29-1545273869084)]

此時(shí)父節(jié)點(diǎn)也需要分裂

[圖片上傳失敗...(image-b07773-1545273869084)]

根節(jié)點(diǎn)未超出 4猛频，結(jié)束；假如此時(shí)根節(jié)點(diǎn)也超出上界了馅笙，需要把根節(jié)點(diǎn)也分裂伦乔，生成一個(gè)新的根節(jié)點(diǎn)，且新的根節(jié)點(diǎn)的關(guān)鍵字為左右子樹的最大關(guān)鍵字

刪除

B+ 樹的刪除與 B 樹也類似董习，找到要?jiǎng)h除的關(guān)鍵字烈和，如果是當(dāng)前子樹的最大關(guān)鍵字，刪除該關(guān)鍵字后還要修改祖先節(jié)點(diǎn)對(duì)應(yīng)的關(guān)鍵字皿淋；如果不是當(dāng)前子樹的最大關(guān)鍵字招刹，直接刪除恬试；

在上一張圖的基礎(chǔ)上刪除 8，這是葉子的最大關(guān)鍵字疯暑，所以需要修改父節(jié)點(diǎn)和祖父節(jié)點(diǎn)的邊界關(guān)鍵字:

[圖片上傳失敗...(image-c9f6ba-1545273869084)]

  • 如果刪除元素的節(jié)點(diǎn)未低于下界限制训柴，則結(jié)束；否則分兩種情況處理:
    • 如果兄弟節(jié)點(diǎn)有富余關(guān)鍵字妇拯，則從兄弟節(jié)點(diǎn)中移動(dòng)一個(gè)關(guān)鍵字到當(dāng)前節(jié)點(diǎn)幻馁，修改父節(jié)點(diǎn)對(duì)應(yīng)邊界關(guān)鍵字即可
    • 如果兄弟節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)都處于下界值，不能外借元素越锈，則合并當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)仗嗦，修改父節(jié)點(diǎn)的孩子指針以及邊界關(guān)鍵字，此時(shí)父節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)也少了一個(gè)甘凭，將當(dāng)前節(jié)點(diǎn)的指針指向父節(jié)點(diǎn)繼續(xù)判斷處理

我們繼續(xù)刪除 7稀拐，此時(shí)該葉子節(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)少于 1 需要調(diào)整，而兄弟節(jié)點(diǎn)有富余關(guān)鍵字丹弱，可以移動(dòng) 5 到當(dāng)前節(jié)點(diǎn)德撬，修改父節(jié)點(diǎn)和祖父節(jié)點(diǎn)的邊界關(guān)鍵字

[圖片上傳失敗...(image-53b83c-1545273869084)]

繼續(xù)刪除 5，兄弟節(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)為下界值 1躲胳，不能外借蜓洪，則合并當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)，并修改父節(jié)點(diǎn)指針及關(guān)鍵字泛鸟，相應(yīng)的祖父節(jié)點(diǎn)也需要修改邊界關(guān)鍵字

[圖片上傳失敗...(image-949cd8-1545273869084)]

B+ 樹動(dòng)態(tài)展示: https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

B* 樹 (B* - Tree)

B* 樹是 B+ 樹的變體蝠咆，在 B+ 樹的基礎(chǔ)上(所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針)北滥，B* 樹多了兩條性質(zhì):

  • 中間結(jié)點(diǎn)也增加了指向兄弟的指針刚操，即每一層節(jié)點(diǎn)都可以橫向遍歷
  • B* 樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為 \lceil\frac {2m}3\rceil个从，即塊的最低使用率為 2/3苏研，代替 B+ 樹的 1/2

下圖的數(shù)據(jù)與之前 B+ 樹的數(shù)據(jù)一樣，但分支結(jié)構(gòu)有所不同(因?yàn)橹虚g節(jié)點(diǎn)關(guān)鍵字范圍變?yōu)閇3, 4]脊另，不同于之前 B+ 樹的 [2, 4])济赎，而且第二層節(jié)點(diǎn)之間也用指針連接起來
[圖片上傳失敗...(image-3559f9-1545273869084)]

優(yōu)勢(shì)

B+ 樹節(jié)點(diǎn)滿時(shí)就會(huì)分裂鉴逞，而 B* 樹節(jié)點(diǎn)滿時(shí)會(huì)先檢查兄弟節(jié)點(diǎn)是否滿(因?yàn)槊總€(gè)節(jié)點(diǎn)都有指向兄弟的指針):

  • 如果兄弟節(jié)點(diǎn)未滿則向兄弟節(jié)點(diǎn)轉(zhuǎn)移關(guān)鍵字，然后修改原節(jié)點(diǎn)和兄弟結(jié)點(diǎn)的關(guān)鍵字以及會(huì)受最大關(guān)鍵字變動(dòng)影響的祖先的邊界關(guān)鍵字
  • 如果兄弟節(jié)點(diǎn)已滿司训，則從當(dāng)前節(jié)點(diǎn)和兄弟節(jié)點(diǎn)各拿出 1/3 的數(shù)據(jù)創(chuàng)建一個(gè)新的節(jié)點(diǎn)出來构捡，然后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針

B* 樹存有兄弟節(jié)點(diǎn)的指針，可以向兄弟節(jié)點(diǎn)轉(zhuǎn)移關(guān)鍵字的特性使得 B* 樹分解次數(shù)變得更少壳猜，節(jié)點(diǎn)空間使用率更高

因?yàn)闆]有找到相關(guān)的內(nèi)容勾徽，關(guān)于 B* 樹的插入刪除這里不再講解

總結(jié)

本文依次介紹了二叉樹 -> 二叉搜索樹 -> 平衡二叉搜索樹(紅黑樹) -> 平衡多路查找樹(B 類樹)，各有特點(diǎn)统扳，其中 B 類樹是介紹的重點(diǎn)喘帚，因?yàn)閷?shí)際運(yùn)用中索引結(jié)構(gòu)使用的是 B 類樹

因?yàn)闃涞纳厦鎺讓訒?huì)反復(fù)查詢畅姊，所以我們可以把樹的前幾層存在內(nèi)存中，而底層的數(shù)據(jù)存在外部磁盤里吹由，這樣效率更高

當(dāng)然 B 樹也存在弊端:

因?yàn)橐坏┐_定最大階數(shù)若未，后面的使用過程中就不可以修改關(guān)鍵字個(gè)數(shù)的范圍

那么除非完全重建數(shù)據(jù)庫，否則無法改變鍵值的最大長度倾鲫。這使得許多數(shù)據(jù)庫系統(tǒng)將人名截?cái)嗟?70 字符之內(nèi)

后面一篇我們會(huì)講解另一種 Mysql 的索引結(jié)構(gòu): 哈希索引粗合，可以動(dòng)態(tài)適應(yīng)任意長度的鍵值

Reference

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市级乍，隨后出現(xiàn)的幾起案子舌劳，更是在濱河造成了極大的恐慌，老刑警劉巖玫荣，帶你破解...
    沈念sama閱讀 218,941評(píng)論 6贊 508
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異大诸，居然都是意外死亡捅厂，警方通過查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,397評(píng)論 3贊 395
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門资柔，熙熙樓的掌柜王于貴愁眉苦臉地迎上來焙贷，“玉大人，你說我怎么就攤上這事贿堰≌奚郑” “怎么了？”我有些...
    開封第一講書人閱讀 165,345評(píng)論 0贊 356
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵羹与，是天一觀的道長故硅。 經(jīng)常有香客問我，道長纵搁，這世上最難降的妖魔是什么吃衅？ 我笑而不...
    開封第一講書人閱讀 58,851評(píng)論 1贊 295
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任，我火速辦了婚禮腾誉，結(jié)果婚禮上徘层，老公的妹妹穿的比我還像新娘。我一直安慰自己利职，他們只是感情好趣效，可當(dāng)我...
    茶點(diǎn)故事閱讀 67,868評(píng)論 6贊 392
  • 惡毒庶女頂嫁案：這布局不是一般人想出來的
    文/花漫 我一把揭開白布。 她就那樣靜靜地躺著猪贪，像睡著了一般跷敬。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上哮伟，一...
    開封第一講書人閱讀 51,688評(píng)論 1贊 305
  • 城市分裂傳說
    那天干花，我揣著相機(jī)與錄音妄帘，去河邊找鬼。 笑死池凄，一個(gè)胖子當(dāng)著我的面吹牛抡驼，可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播肿仑，決...
    沈念sama閱讀 40,414評(píng)論 3贊 418
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開眼致盟，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來了尤慰？” 一聲冷哼從身側(cè)響起馏锡，我...
    開封第一講書人閱讀 39,319評(píng)論 0贊 276
  • 萬榮殺人案實(shí)錄
    序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎伟端，沒想到半個(gè)月后杯道，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
    沈念sama閱讀 45,775評(píng)論 1贊 315
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡责蝠，尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,945評(píng)論 3贊 336
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年党巾，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片霜医。...
    茶點(diǎn)故事閱讀 40,096評(píng)論 1贊 350
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡齿拂，死狀恐怖，靈堂內(nèi)的尸體忽然破棺而出肴敛，到底是詐尸還是另有隱情署海，我是刑警寧澤，帶...
    沈念sama閱讀 35,789評(píng)論 5贊 346
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布医男，位于F島的核電站砸狞，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏昨登。R本人自食惡果不足惜趾代，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,437評(píng)論 3贊 331
  • 男人毒藥：我在死后第九天來索命
    文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望丰辣。 院中可真熱鬧撒强，春花似錦、人聲如沸笙什。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,993評(píng)論 0贊 22
  • 一樁弒父案，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽琐凭。三九已至芽隆，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背胚吁。 一陣腳步聲響...
    開封第一講書人閱讀 33,107評(píng)論 1贊 271
  • 情欲美人皮
    我被黑心中介騙來泰國打工牙躺， 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人腕扶。 一個(gè)月前我還...
    沈念sama閱讀 48,308評(píng)論 3贊 372
  • 代替公主和親
    正文 我出身青樓孽拷，卻偏偏與公主長得像，于是被迫代替她去往敵國和親半抱。 傳聞我的和親對(duì)象是個(gè)殘疾皇子脓恕，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,037評(píng)論 2贊 355

推薦閱讀更多精彩內(nèi)容

  • B樹的定義 一棵m階的B樹滿足下列條件： 樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外窿侈，其它每個(gè)結(jié)點(diǎn)至少有m...
    文檔隨手記閱讀 13,222評(píng)論 0贊 25
  • 目錄 1炼幔、什么是樹 2、相關(guān)術(shù)語 3史简、二叉樹 3.1乃秀、二叉樹的類型 3.2、二叉樹的性質(zhì) 3.3乘瓤、二叉樹的結(jié)構(gòu) 3...
    我哈啊哈啊哈閱讀 2,553評(píng)論 0贊 10
  • 樹(Tree)的基本概念樹是由結(jié)點(diǎn)或頂點(diǎn)和邊組成的(可能是非線性的)且不存在著任何環(huán)的一種數(shù)據(jù)結(jié)構(gòu)环形。沒有結(jié)點(diǎn)的樹稱...
    意識(shí)流丶閱讀 52,804評(píng)論 0贊 30
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系，并對(duì)這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算衙傀，而且確保經(jīng)過這...
    Winterfell_Z閱讀 5,817評(píng)論 0贊 13
  • 原文鏈接 B樹 1.前言： 動(dòng)態(tài)查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（...
    非典型程序員閱讀 1,162評(píng)論 0贊 3