摘要：切記，紅黑樹在旋轉(zhuǎn)和顏色變換的過程中，必須遵守紅黑樹的幾條規(guī)則。樹的外部存儲磁盤布局計算機中的機械磁盤是由磁頭和圓盤組成，每個圓盤上劃分為多個磁道，每個磁道又劃分為多個扇區(qū)。

根
????樹最頂端的節(jié)點稱為“根”，一棵樹只有一個根

父節(jié)點
????每個節(jié)點(除了根)都恰好有一條邊向上連接到另外一個節(jié)點，上面這個節(jié)點就稱為下面節(jié)點的“父節(jié)點”

子節(jié)點
????每個節(jié)點都可能有一條或者多條邊向下連接到其它節(jié)點，下面的這些節(jié)點就稱為它的“子節(jié)點”

葉節(jié)點
????沒有子節(jié)點的節(jié)點稱為“葉子節(jié)點”或者簡稱為“葉節(jié)點”

子樹
????每個節(jié)點可以作為“子樹”的根，它和它所有的子節(jié)點構(gòu)成了這棵樹的子樹

路徑
????設想順著連接節(jié)點的邊從一個節(jié)點走到另一個節(jié)點，所經(jīng)過節(jié)點的順序排列就稱為“路徑”

????如果一棵樹中每個節(jié)點最多只能有兩個子節(jié)點，這樣的樹就稱為“二叉樹”，二叉樹每個節(jié)點的兩個子節(jié)點稱為“左子節(jié)點”和“右子節(jié)點”。

????如果我們給二叉樹加一個額外的條件，就可以得到一種被稱作二叉搜索樹(binary search tree)的特殊二叉樹。二叉搜索樹要求：每個節(jié)點都不比它左子樹的任意元素小，而且不比它的右子樹的任意元素大。(如果我們假設樹中沒有重復的元素，那么上述要求可以寫成：每個節(jié)點比它左子樹的任意節(jié)點大，而且比它右子樹的任意節(jié)點小)

????平衡二叉樹（Balanced Binary Tree）具有以下性質(zhì)：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。

????二叉搜索樹可以方便的實現(xiàn)搜索算法。在搜索元素x的時候，我們可以將x和根節(jié)點比較:

如果x等于根節(jié)點，那么找到x，停止搜索 (終止條件)

如果x小于根節(jié)點，那么搜索左子樹

如果x大于根節(jié)點，那么搜索右子樹

????當二叉搜索樹平衡時達到最高搜索效率，時間復雜度為O(logN)；當二叉搜索樹單調(diào)插入數(shù)據(jù)時，搜索效率最低，此時二叉搜索樹相當于鏈表，時間復雜度為O(N)

????二叉搜索樹的查找代碼如下(僅考慮數(shù)據(jù)不重復的情況)：

public Node find(int key) {
    Node current = root;
    while (current.data != key) {
        if (key < current.data) {
            current = current.left;
        } else {
            current = current.right;
        }
        if (current == null) {
            return null;
        }
    }
    return current;
} 

????二叉搜索樹的插入相對簡單，二叉查找樹的插入過程如下：

若當前的二叉搜索樹為空，則插入的元素為根節(jié)點

若插入的元素值小于根節(jié)點值，則將元素插入到左子樹中

若插入的元素值不小于根節(jié)點值，則將元素插入到右子樹中

????二叉搜索樹的插入代碼如下(僅考慮數(shù)據(jù)不重復的情況)：

public void insert(int key, double data) {
    Node newNode = new Node();
    newNode.key = key;
    newNode.data = data;
    if (root == null) {
        root = newNode;
    } else {
        Node current = root;
        Node parent;
        while (true) {
            parent = current;
            if (key < current.key) {
                current = current.left;
                if (current == null) {
                    parent.left = newNode;
                    return;
                }
            } else {
                current = current.right;
                if (current == null) {
                    parent.right = newNode;
                    return;
                }
            }
        }
    }
}

????二叉搜索樹刪除過程也分為三種情況：

待刪除節(jié)點是葉節(jié)點，此時只要刪除該節(jié)點，并修改其父節(jié)點的指針指向null即可

待刪除節(jié)點只有一個子節(jié)點，此時只要將父節(jié)點的指針指向該節(jié)點的子樹即可

待刪除節(jié)點有兩個子節(jié)點，此時需要找到該節(jié)點的后繼節(jié)點，用后繼節(jié)點來代替它

????一個節(jié)點的后繼節(jié)點即所有比該節(jié)點大的節(jié)點集合中最小的那個節(jié)點。為此可以查找該節(jié)點的右子樹的最左節(jié)點即可，如圖：

????查找后繼節(jié)點代碼如下：

private Node getSuccessor(Node delNode) {
    Node successorParent = delNode;
    Node successor = delNode;
    Node current = delNode.right;
    while (current != null) {
        successorParent = successor;
        successor = current;
        current = current.left;
    }
    // 節(jié)點移位，參照/docs/二叉搜索樹后繼節(jié)點
    if (successor != delNode.right) {
        successorParent.left = successor.right;
        successor.right = delNode.right;
    }
    return successor;
}

????待刪除節(jié)點有兩個子節(jié)點的刪除過程如圖：

????刪除節(jié)點的代碼如下：

public void delete(int key) {
    Node current = root;
    Node parent = root;
    boolean isLeftChild = true;
    while (current.data != key) {
        parent = current;
        if (key < current.data) {
            isLeftChild = true;
            current = current.left;
        } else {
            isLeftChild = false;
            current = current.right;
        }
        if (current == null) {
            // 未找到待刪除的節(jié)點
            return;
        }
    }

    // 沒有子節(jié)點
    if (current.left == null && current.right == null) {
        if (current == root) {
            root = null;
        } else if (isLeftChild) {
            parent.left = null;
        } else {
            parent.right = null;
        }
    } else if (current.right == null) {
        // 只有左節(jié)點
        if (current == root) {
            root = current.left;
        } else if (isLeftChild) {
            parent.left = current.left;
        } else {
            parent.right = current.left;
        }
    } else if (current.left == null) {
        if (current == root) {
            root = current.right;
        } else if (isLeftChild) {
            parent.left = current.right;
        } else {
            parent.right = current.right;
        }
    } else {
        // 兩個節(jié)點
        Node successor = getSuccessor(current);
        if (current == root) {
            root = successor;
        } else if (isLeftChild) {
            parent.left = successor;
        } else {
            parent.right = successor;
        }
        successor.left = current.left;
    }
}

????紅黑樹（英語：Red–black tree）是平衡二叉搜索樹的一種實現(xiàn)方式，是在計算機科學中用到的一種數(shù)據(jù)結(jié)構(gòu)，典型的用途是實現(xiàn)關(guān)聯(lián)數(shù)組。

????紅黑樹必須滿足以下的規(guī)則：

每一個節(jié)點不是紅色就是黑色

根總是黑色的

如果節(jié)點是紅色的，則它的子節(jié)點必須是黑色的(反之倒不一定必須為真)

該樹是完美黑色平衡的，即任意空鏈接到根結(jié)點的路徑上的黑鏈接數(shù)量相同

如果一個黑色節(jié)點下面有一個紅色節(jié)點和一個黑色節(jié)點，那么紅色節(jié)點只能是左節(jié)點

????旋轉(zhuǎn)又分為左旋和右旋。通常左旋操作用于將一個向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接。

????左旋如圖所示：

代碼如下：

private Node rotateLeft(Node node) {
    Node x = node.right;
    node.right = x.left;
    x.left = node;
    x.color = x.left.color;
    x.left.color = RED;
    return x;
}

????右旋如圖所示：

代碼如下：

private Node rotateRight(Node node) {
    Node x = node.left;
    node.left = x.right;
    x.right = node;
    x.color = x.right.color;
    x.right.color = RED;
    return x;
}

????在插入數(shù)據(jù)過程中，遇到一個黑色節(jié)點下面帶有兩個紅色的子節(jié)點就要進行顏色變換。顏色變換規(guī)則如下：兩個紅色子節(jié)點變?yōu)楹谏谏腹?jié)點通常變?yōu)榧t色，如果父節(jié)點是根節(jié)點的話，則父節(jié)點繼續(xù)保持為黑色。

代碼如下：

private void flipColors(Node node) {
    node.color = !node.color;
    node.left.color = !node.left.color;
    node.right.color = !node.right.color;
}

????紅黑樹在插入時，跟二叉搜索樹的插入規(guī)則是一致的，唯一不同的是，紅黑樹要保持自身的平衡，而這可以通過旋轉(zhuǎn)和顏色變換做到。切記，紅黑樹在旋轉(zhuǎn)和顏色變換的過程中，必須遵守紅黑樹的幾條規(guī)則。

代碼如下：

public void insert(int key) {
    root = insert(root, key);
    // 根節(jié)點只能是黑色
    root.color = BLACK;
}

private Node insert(Node node, int key) {
    if (node == null) {
        return new Node(key, RED);
    }

    if (key < node.key) {
        node.left = insert(node.left, key);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
    } else {
        node.key = key;
    }

    // 如果一個黑色節(jié)點下面的兩個節(jié)點一個黑色，一個紅色，則紅色節(jié)點只能是左節(jié)點
    if (isRed(node.right) && !isRed(node.left)) {
        node = rotateLeft(node);
    }

    // 紅色節(jié)點下面不能有紅色節(jié)點
    if (isRed(node.left) && isRed(node.left.left)) {
        node = rotateRight(node);
    }

    // 當一個黑色節(jié)點下有兩個紅色節(jié)點，則要進行顏色變換
    if (isRed(node.left) && isRed(node.right)) {
        flipColors(node);
    }
    return node;
}

????紅黑樹的查找跟二叉搜索樹的查找過程是完全一致的
????紅黑樹的刪除過程過于復雜，以致于很多程序員用不同的方法去規(guī)避它，其中一種方法是：為已刪除的節(jié)點做標記而不實際刪除它。這里不做進一步的討論。

????紅黑樹的詳細實現(xiàn)可以參考：紅黑樹完整代碼Java實現(xiàn)

????2-3-4樹是一種多叉樹，名字中的2、3和4的含義是指一個節(jié)點可能含有的子節(jié)點的個數(shù)。2-3-4樹性質(zhì)如下：

任一節(jié)點只能是 2 度節(jié)點、3 度節(jié)點或 4 度節(jié)點，不存在元素數(shù)為 0 的節(jié)點(2度節(jié)點和3度節(jié)點是指該節(jié)點有2個或者3個子節(jié)點)

所有葉子節(jié)點都擁有相同的深度（depth）

元素始終保持排序順序

????2-3-4樹結(jié)構(gòu)圖如下：

????為了方便起見，用從0到2的數(shù)字給數(shù)據(jù)項編號，用0到3給子節(jié)點鏈編號。節(jié)點中的數(shù)據(jù)項按照關(guān)鍵字升序排列，習慣上從左到右升序。還加上以下幾點：

根是child0的子樹的所有子節(jié)點的關(guān)鍵字值小于key0

根是child1的子樹的所有子節(jié)點的關(guān)鍵字值大于key0并且小于key1

根是child2的子樹的所有子節(jié)點的關(guān)鍵字值大于key1并且小于key2

根是child3的子樹的所有子節(jié)點的關(guān)鍵字值大于key2

????如圖：

????2-3-4樹依靠節(jié)點分裂來保持自身的平衡性。2-3-4樹分裂的規(guī)則是自頂向下的，如果根節(jié)點或者待插入的節(jié)點中數(shù)據(jù)項已滿，就要進行分裂，分裂規(guī)則如下：

創(chuàng)建一個空節(jié)點，它是要分裂節(jié)點的兄弟，在要分裂節(jié)點的右邊

待分裂節(jié)點右邊的數(shù)據(jù)項移到右邊節(jié)點中，左邊的數(shù)據(jù)項保留在原有節(jié)點中，中間的數(shù)據(jù)項上升到父節(jié)點中

????如圖：

????2-3樹也是一種多叉樹，與2-3-4樹類似，現(xiàn)在在很多應用程序中還在應用，一些用于2-3樹的技術(shù)會在B-樹中應用。

????2-3樹比2-3-4樹少一個數(shù)據(jù)項和一個子節(jié)點。節(jié)點可以保存1個或者2個數(shù)據(jù)項，可以有0個、1個、2個或者3個子節(jié)點。其它方面，父節(jié)點和子節(jié)點的關(guān)鍵字值的排列順序和2-3-4樹是一樣的。

????2-3樹節(jié)點分裂和2-4樹節(jié)點分裂有很大的不同。2-3樹節(jié)點分裂是自底向上的(即若插入數(shù)據(jù)時根節(jié)點數(shù)據(jù)項已滿，不進行分裂，只有待插入的節(jié)點數(shù)據(jù)項滿時才進行分裂)，而且2-3樹節(jié)點分裂必須用到新數(shù)據(jù)項。

????計算機中的機械磁盤是由磁頭和圓盤組成，每個圓盤上劃分為多個磁道，每個磁道又劃分為多個扇區(qū)。

????磁盤的結(jié)構(gòu)圖如下：

????系統(tǒng)將文件存儲到磁盤上時，按柱面、磁頭、扇區(qū)的方式進行，即最先是第1磁道的第一磁頭（也就是第1盤面的第1磁道）下的所有扇區(qū)，然后，是同一柱面的下一磁頭，……，一個柱面存儲滿后就推進到下一個柱面，直到把文件內(nèi)容全部寫入磁盤。

????系統(tǒng)也以相同的順序讀出數(shù)據(jù)。讀出數(shù)據(jù)時通過告訴磁盤控制器要讀出扇區(qū)所在的柱面號、磁頭號和扇區(qū)號（物理地址的三個組成部分）進行（目前多是通過LBA線性尋址的方式定位）。

????由于存儲介質(zhì)的特性，磁盤本身存取就比主存慢很多，再加上機械運動耗費（磁盤旋轉(zhuǎn)和磁頭移動），磁盤的存取速度往往是主存的幾百分之一，因此為了提高效率，要盡量減少磁盤I/O。為了達到這個目的，磁盤往往不是嚴格按需讀取，而是每次都會預讀，即使只需要一個字節(jié)，磁盤也會從這個位置開始，順序向后讀取一定長度的數(shù)據(jù)放入內(nèi)存。

????預讀的長度一般為頁（page）的整倍數(shù)。頁是計算機管理存儲器的邏輯塊，硬件及操作系統(tǒng)往往將主存和磁盤存儲區(qū)分割為連續(xù)的大小相等的塊，每個存儲塊稱為一頁（在許多操作系統(tǒng)中，頁得大小通常為4k），主存和磁盤以頁為單位交換數(shù)據(jù)。當程序要讀取的數(shù)據(jù)不在主存中時，會觸發(fā)一個缺頁異常，此時系統(tǒng)會向磁盤發(fā)出讀盤信號，磁盤會找到數(shù)據(jù)的起始位置并向后連續(xù)讀取一頁或幾頁載入內(nèi)存中，然后異常返回，程序繼續(xù)運行（詳情請參考頁面置換算法以及虛擬內(nèi)存）。

每個扇區(qū)的弧長是一樣的嗎？

????目前大多數(shù)教程中給出的圖片都是老式的機械磁盤的組成。在老式機械磁盤中，每個磁道的扇區(qū)弧長是不一樣的。越靠內(nèi)的磁道密度越大，存儲的數(shù)據(jù)也就越多；越靠外的磁道密度越小，存儲的數(shù)據(jù)也就越少。所以，雖然內(nèi)外磁道的扇區(qū)弧長不一樣，由于密度的原因，每個扇區(qū)存儲的數(shù)據(jù)量仍然是一樣的，都是512B。在新式磁盤中，內(nèi)外磁道的扇區(qū)密度都是相同的，所以新式磁盤每個扇區(qū)的弧長都是一樣的。

????2-3樹和2-3-4樹是B樹的一種特例，B樹的操作與2-3樹和2-3-4樹大致相同，此處不在過多介紹。

????前面已經(jīng)簡單介紹過，磁盤控制器每次預讀幾個文件塊的內(nèi)容，所以對于磁盤讀寫來說，當需要的數(shù)據(jù)都在一個文件塊中時，磁盤讀寫次數(shù)最少，此時效率是最高的。而B樹設計將每個節(jié)點的數(shù)據(jù)項剛好填滿一個文件塊.

????假設這樣一種極端情況，如果每個文件塊中只有一條記錄是我們需要的。那么當我們獲取第二條記錄時又要重新從磁盤加載新的文件塊。此時由于磁盤讀取次數(shù)增多，導致程序的性能大大下降。

????B+樹是B-樹的變形。B+樹與B樹的區(qū)別在于：

B+樹非葉子節(jié)點只保存索引，數(shù)據(jù)全部保存在葉子節(jié)點上

B+樹的所有的葉子節(jié)點組成了一張鏈表，便于數(shù)據(jù)遍歷

對于有M個數(shù)據(jù)項的B+樹，最多只會有M的子節(jié)點

如圖：

????基于上文對2-3-4樹和2-3樹的討論，傳統(tǒng)的B+樹也是按照50%的分裂方式，這樣節(jié)點分裂后，新的節(jié)點中只有原來一半的數(shù)據(jù)量，不但浪費了空間，還造成節(jié)點的增多，從而加重磁盤IO的次數(shù)。在目前絕大部分關(guān)系型數(shù)據(jù)庫中，都針對B+樹索引的遞增/遞減插入進行了優(yōu)化，新的分裂策略在插入新數(shù)據(jù)時，不移動原有頁面的任何記錄，只是將新插入的記錄寫到新頁面之中，這樣原有頁面的利用率仍然是100%。

????所以對于MySQL數(shù)據(jù)庫來說，使用自增主鍵插入數(shù)據(jù)時就會形成一個緊湊的索引結(jié)構(gòu)，近似順序填滿。由于每次插入時也不需要移動已有數(shù)據(jù)，因此效率很高，也不會增加很多開銷在維護索引上。

如圖：

從MySQL Bug#67718淺談B+樹索引的分裂優(yōu)化

紅黑樹完整代碼Java實現(xiàn)

硬盤的讀寫原理

Java數(shù)據(jù)結(jié)構(gòu)和算法 [美]Robert Lafore著

算法導論 [美]Thomas H.Cormen，[美]Charles E.Leiserson，[美]Ronald L.Rivest，[美]Clifford Stein 著