二叉搜索樹(shù)，平衡樹(shù)，B，b-，b+,b*,紅黑樹(shù)

二叉搜索樹(shù)

? 1.所有非葉子結(jié)點(diǎn)至多擁有兩個(gè)兒子（Left和Right）；

? 2.所有結(jié)點(diǎn)存儲(chǔ)一個(gè)關(guān)鍵字；

? 3.非葉子結(jié)點(diǎn)的左指針指向小于其關(guān)鍵字的子樹(shù)，右指針指向大于其關(guān)鍵字的子樹(shù)；

? 如：

?

img

? 二叉樹(shù)的搜索，從根結(jié)點(diǎn)開(kāi)始，如果查詢(xún)的關(guān)鍵字與結(jié)點(diǎn)的關(guān)鍵字相等，那么就命中；

否則，如果查詢(xún)關(guān)鍵字比結(jié)點(diǎn)關(guān)鍵字小，就進(jìn)入左兒子；如果比結(jié)點(diǎn)關(guān)鍵字大，就進(jìn)入

右兒子；如果左兒子或右兒子的指針為空，則報(bào)告找不到相應(yīng)的關(guān)鍵字；

? 如果二叉樹(shù)的所有非葉子結(jié)點(diǎn)的左右子樹(shù)的結(jié)點(diǎn)數(shù)目均保持差不多（平衡），那么二叉樹(shù)

的搜索性能逼近二分查找；但它比連續(xù)內(nèi)存空間的二分查找的優(yōu)點(diǎn)是，改變二叉樹(shù)結(jié)構(gòu)

（插入與刪除結(jié)點(diǎn)）不需要移動(dòng)大段的內(nèi)存數(shù)據(jù)，甚至通常是常數(shù)開(kāi)銷(xiāo)；

? 如：

?

img

但二叉樹(shù)在經(jīng)過(guò)多次插入與刪除后，有可能導(dǎo)致不同的結(jié)構(gòu)：

img

右邊也是一個(gè)二叉樹(shù)，但它的搜索性能已經(jīng)是線性的了；同樣的關(guān)鍵字集合有可能導(dǎo)致不同的

樹(shù)結(jié)構(gòu)索引；所以，使用二叉樹(shù)還要考慮盡可能讓二叉樹(shù)保持左圖的結(jié)構(gòu)，和避免右圖的結(jié)構(gòu)，也就

是所謂的“平衡”問(wèn)題；

? 實(shí)際使用的二叉樹(shù)都是在原二叉樹(shù)的基礎(chǔ)上加上平衡算法，即“平衡二叉樹(shù)”；如何保持二叉樹(shù)

結(jié)點(diǎn)分布均勻的平衡算法是平衡二叉樹(shù)的關(guān)鍵；

平衡二叉樹(shù)

AVL-自平衡二叉查找樹(shù)

平衡二叉搜索樹(shù)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。常用算法有紅黑樹(shù)、AVL、Treap、伸展樹(shù)等。在平衡二叉搜索樹(shù)中，我們可以看到，其高度一般都良好地維持在O（log2n），大大降低了操作的時(shí)間復(fù)雜度。

調(diào)整平衡的基本思想：
當(dāng)在二叉排序樹(shù)中插入一個(gè)節(jié)點(diǎn)時(shí)，首先檢查是否因插入而破壞了平衡，若破壞，則找出其中的最小不平衡二叉樹(shù)，在保持二叉排序樹(shù)特性的情況下，調(diào)整最小不平衡子樹(shù)中節(jié)點(diǎn)之間的關(guān)系，以達(dá)到新的平衡。
所謂最小不平衡子樹(shù)，指離插入節(jié)點(diǎn)最近且以平衡因子的絕對(duì)值大于1的節(jié)點(diǎn)作為根的子樹(shù)。

先插入指定節(jié)點(diǎn)，記錄下當(dāng)前節(jié)點(diǎn)的信息，LH，EH或者RH。
\1. 若左子樹(shù)高LH，查看其左子樹(shù)根節(jié)點(diǎn)的信息，若是LH，則一次右旋；若是RH，則一次左旋+一次右旋
\2. 若右子樹(shù)高RH，查看右子樹(shù)根節(jié)點(diǎn)的信息，若是RH，則一次左旋；若是LH，則一次右旋+一次左旋
\3. 調(diào)整改變的節(jié)點(diǎn)信息

追求絕對(duì)的高度平衡，隨著樹(shù)的高度的增加，動(dòng)態(tài)插入和刪除的代價(jià)也隨之增加。

具體旋轉(zhuǎn)策略見(jiàn)http://blog.csdn.net/liyong199012/article/details/29219261

B樹(shù)

1、根結(jié)點(diǎn)至少有兩個(gè)子女；
2、每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：m/2 - 1 <= j <= m - 1；
3、除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括葉子結(jié)點(diǎn)）的度數(shù)正好是關(guān)鍵字總數(shù)加1，故內(nèi)部子樹(shù)個(gè)數(shù) k 滿足：m/2<= k <= m ；
4、所有的葉子結(jié)點(diǎn)都位于同一層。

這里寫(xiě)圖片描述

B-樹(shù)

B-樹(shù)

這里寫(xiě)圖片描述

1. 樹(shù)中每個(gè)結(jié)點(diǎn)至多有m個(gè)孩子；
2. 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外，其它每個(gè)結(jié)點(diǎn)至少有[m/2]個(gè)孩子；
3. 若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有2個(gè)孩子；
4. 所有葉子結(jié)點(diǎn)都出現(xiàn)在同一層，葉子結(jié)點(diǎn)不包含任何關(guān)鍵字信息(可以看做是外部接點(diǎn)或查詢(xún)失敗的接點(diǎn)，實(shí)際上這些結(jié)點(diǎn)不存在，指向這些結(jié)點(diǎn)的指針都為null)；
5. 每個(gè)非終端結(jié)點(diǎn)中包含有n個(gè)關(guān)鍵字信息： (n，A0，K1，A1，K2，A2，……，Kn，An)。其中，
   a) Ki (i=1…n)為關(guān)鍵字，且關(guān)鍵字按順序排序Ki < K(i-1)。
   b) Ai為指向子樹(shù)根的接點(diǎn)，且指針A(i-1)指向子樹(shù)種所有結(jié)點(diǎn)的關(guān)鍵字均小于Ki，但都大于K(i-1)。
   c) 關(guān)鍵字的個(gè)數(shù)n必須滿足： [m/2]-1 <= n <= m-1
   建立
   由于B~樹(shù)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)必須>=[m/2]-1。因此和平衡二叉樹(shù)不同，每一次插入一個(gè)關(guān)鍵字并不是在樹(shù)中添加一個(gè)結(jié)點(diǎn)，而是首先在最低層的某個(gè)非終端結(jié)點(diǎn)中添加一個(gè)關(guān)鍵字，若該結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)不超過(guò)m-1，則插入完成。否則，要產(chǎn)生結(jié)點(diǎn)的”分裂” 。
   外存
   我們現(xiàn)在把整棵樹(shù)構(gòu)造在磁盤(pán)中，假如每個(gè)盤(pán)塊可以正好存放一個(gè)B~樹(shù)的結(jié)點(diǎn)（正好存放2個(gè)文件名）。那么一個(gè)BTNode結(jié)點(diǎn)就代表一個(gè)盤(pán)塊，而子樹(shù)指針就是存放另外一個(gè)盤(pán)塊 （詳細(xì)見(jiàn)《外部存儲(chǔ)器—磁盤(pán) 》）的地址。
   現(xiàn)在我們模擬查找文件29的過(guò)程：
   (1) 根據(jù)根結(jié)點(diǎn)指針找到文件目錄的根磁盤(pán)塊1，將其中的信息導(dǎo)入內(nèi)存。【磁盤(pán)IO操作1次】
   (2) 此時(shí)內(nèi)存中有兩個(gè)文件名17，35和三個(gè)存儲(chǔ)其他磁盤(pán)頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)17<29<35，因此我們找到指針p2。
   (3) 根據(jù)p2指針，我們定位到磁盤(pán)塊3，并將其中的信息導(dǎo)入內(nèi)存。【磁盤(pán)IO操作2次】
   (4) 此時(shí)內(nèi)存中有兩個(gè)文件名26，30和三個(gè)存儲(chǔ)其他磁盤(pán)頁(yè)面地址的數(shù)據(jù)。根據(jù)算法我們發(fā)現(xiàn)26<29<30，因此我們找到指針p2。
   (5) 根據(jù)p2指針，我們定位到磁盤(pán)塊8，并將其中的信息導(dǎo)入內(nèi)存?！敬疟P(pán)IO操作3次】
   (6) 此時(shí)內(nèi)存中有兩個(gè)文件名28，29。根據(jù)算法我們查找到文件29，并定位了該文件內(nèi)存的磁盤(pán)地址。

  分析一下上面的過(guò)程，我們發(fā)現(xiàn)需要3次磁盤(pán)IO操作和3次內(nèi)存查找操作。關(guān)于內(nèi)存中的文件名查找，由于是一個(gè)有序表結(jié)構(gòu)，可以利用折半查找提高效率。至于3次磁盤(pán)IO操作時(shí)影響整個(gè)B~樹(shù)查找效率的決定因素。
  當(dāng)然，如果我們使用平衡二叉樹(shù)的磁盤(pán)存儲(chǔ)結(jié)構(gòu)來(lái)進(jìn)行查找，磁盤(pán)IO操作最少4次，最多5次。而且文件越多，B~樹(shù)比平衡二叉樹(shù)所用的磁盤(pán)IO操作次數(shù)將越少，效率也越高。

B+樹(shù)

B+ 樹(shù)是一種樹(shù)數(shù)據(jù)結(jié)構(gòu)，是一個(gè)n叉樹(shù)，每個(gè)節(jié)點(diǎn)通常有多個(gè)孩子，一顆B+樹(shù)包含根節(jié)點(diǎn)、內(nèi)部節(jié)點(diǎn)和葉子節(jié)點(diǎn)。根節(jié)點(diǎn)可能是一個(gè)葉子節(jié)點(diǎn)，也可能是一個(gè)包含兩個(gè)或兩個(gè)以上孩子節(jié)點(diǎn)的節(jié)點(diǎn)。
B+ 樹(shù)通常用于數(shù)據(jù)庫(kù)和操作系統(tǒng)的文件系統(tǒng)中。
NTFS, ReiserFS, NSS, XFS, JFS, ReFS 和BFS等文件系統(tǒng)都在使用B+樹(shù)作為元數(shù)據(jù)索引。
B+ 樹(shù)的特點(diǎn)是能夠保持?jǐn)?shù)據(jù)穩(wěn)定有序，其插入與修改擁有較穩(wěn)定的對(duì)數(shù)時(shí)間復(fù)雜度。
B+ 樹(shù)元素自底向上插入。

這里寫(xiě)圖片描述

所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。(而B(niǎo) 樹(shù)的葉子節(jié)點(diǎn)并沒(méi)有包括全部需要查找的信息)
所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。(而B(niǎo) 樹(shù)的非終節(jié)點(diǎn)也包含需要查找的有效信息)

1) 有n棵子樹(shù)的結(jié)點(diǎn)中含有n個(gè)關(guān)鍵字；  (B~樹(shù)是n棵子樹(shù)有n+1個(gè)關(guān)鍵字)
2) 所有的葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字的信息，及指向含有這些關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字的大小自小而大的順序鏈接。 (B~樹(shù)的葉子節(jié)點(diǎn)并沒(méi)有包括全部需要查找的信息)
3) 所有的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中僅含有其子樹(shù)根結(jié)點(diǎn)中最大（或最?。╆P(guān)鍵字。 (B~樹(shù)的非終節(jié)點(diǎn)也包含需要查找的有效信息)

B+樹(shù)的有效內(nèi)容均在葉子節(jié)點(diǎn)，B-樹(shù)的有效內(nèi)容不全在葉子節(jié)點(diǎn)上
B+樹(shù)的頭指針有兩個(gè)，一個(gè)指向根節(jié)點(diǎn)，另一個(gè)指向關(guān)鍵字最小的元素，因此B+樹(shù)有兩種遍歷的方式：
1.從根節(jié)點(diǎn)開(kāi)始隨機(jī)查詢(xún)
2.從最小關(guān)鍵詞順序查詢(xún)

B*樹(shù)

這里寫(xiě)圖片描述

在非根節(jié)點(diǎn)和葉子節(jié)點(diǎn)，增加了指向兄弟節(jié)點(diǎn)的指針。

B樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)M，即塊的最低使用率為2/3

（代替B+樹(shù)的1/2）；

? B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)

復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父

結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針；

? B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分

數(shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字

（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之

間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針；

? 所以，B*樹(shù)分配新結(jié)點(diǎn)的概率比B+樹(shù)要低，空間使用率更高；

紅黑樹(shù)

紅黑樹(shù)（Red Black Tree） 是一種自平衡二叉查找樹(shù)
紅黑樹(shù)和AVL樹(shù)類(lèi)似，都是在進(jìn)行插入和刪除操作時(shí)通過(guò)特定操作保持二叉查找樹(shù)的平衡，從而獲得較高的查找性能。
二叉平衡樹(shù)的嚴(yán)格平衡策略以犧牲建立查找結(jié)構(gòu)(插入，刪除操作)的代價(jià)，換來(lái)了穩(wěn)定的O(logN) 的查找時(shí)間復(fù)雜度
它雖然是復(fù)雜的，但它的最壞情況運(yùn)行時(shí)間也是非常良好的，并且在實(shí)踐中是高效的： 它可以在O(log n)時(shí)間內(nèi)做查找，插入和刪除，這里的n 是樹(shù)中元素的數(shù)目。

(1) 每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。
(2) 根節(jié)點(diǎn)是黑色。
(3) 每個(gè)葉子節(jié)點(diǎn)是黑色。 [注意：這里葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn)！]
(4) 如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的。
(5) 從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。12345

RBT 的操作代價(jià)分析：
(1) 查找代價(jià)：由于紅黑樹(shù)的性質(zhì)(最長(zhǎng)路徑長(zhǎng)度不超過(guò)最短路徑長(zhǎng)度的2倍)，可以說(shuō)明紅黑樹(shù)雖然不像AVL一樣是嚴(yán)格平衡的，但平衡性能還是要比BST要好。其查找代價(jià)基本維持在O(logN)左右，但在最差情況下(最長(zhǎng)路徑是最短路徑的2倍少1)，比AVL要略遜色一點(diǎn)。
(2) 插入代價(jià)：RBT插入結(jié)點(diǎn)時(shí)，需要旋轉(zhuǎn)操作和變色操作。但由于只需要保證RBT基本平衡就可以了。因此插入結(jié)點(diǎn)最多只需要2次旋轉(zhuǎn)，這一點(diǎn)和AVL的插入操作一樣。雖然變色操作需要O(logN)，但是變色操作十分簡(jiǎn)單，代價(jià)很小。
(3) 刪除代價(jià)：RBT的刪除操作代價(jià)要比AVL要好的多，刪除一個(gè)結(jié)點(diǎn)最多只需要3次旋轉(zhuǎn)操作。
RBT 效率總結(jié) : 查找 效率最好情況下時(shí)間復(fù)雜度為O(logN)，但在最壞情況下比AVL要差一些，但也遠(yuǎn)遠(yuǎn)好于BST。
插入和刪除操作改變樹(shù)的平衡性的概率要遠(yuǎn)遠(yuǎn)小于AVL（RBT不是高度平衡的）。因此需要的旋轉(zhuǎn)操作的可能性要小，而且一旦需要旋轉(zhuǎn)，插入一個(gè)結(jié)點(diǎn)最多只需要旋轉(zhuǎn)2次，刪除最多只需要旋轉(zhuǎn)3次(小于AVL的刪除操作所需要的旋轉(zhuǎn)次數(shù))。雖然變色操作的時(shí)間復(fù)雜度在O(logN)，但是實(shí)際上，這種操作由于簡(jiǎn)單所需要的代價(jià)很小。

紅黑樹(shù)能夠以O(shè)(log2(N))的時(shí)間復(fù)雜度進(jìn)行搜索、插入、刪除操作。此外,任何不平衡都會(huì)在3次旋轉(zhuǎn)之內(nèi)解決。這一點(diǎn)是AVL所不具備的。

插入操作：
1.插入根節(jié)點(diǎn)（不需要操作）
2.父節(jié)點(diǎn)為黑色(不需要操作)
3.父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)為紅色，祖父節(jié)點(diǎn)為黑色，只需要變色，將祖父節(jié)點(diǎn)遞歸檢查（原本檢查自己）
4.父節(jié)點(diǎn)為紅色，兄弟節(jié)點(diǎn)為黑色，祖父節(jié)點(diǎn)為紅色，先兩次旋轉(zhuǎn)再調(diào)整顏色（左旋+右旋）12345
刪除操作：
1.刪除只有一個(gè)新的根節(jié)點(diǎn)（直接刪除）
2.父節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)為紅色（先旋轉(zhuǎn)成左左，再刪除）
3.父節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)為黑色（先將兄弟節(jié)點(diǎn)換成紅色，變成情況2）
4.父節(jié)點(diǎn)為紅色，自己和兄弟節(jié)點(diǎn)為黑色（將父節(jié)點(diǎn)變成黑色，兄弟節(jié)點(diǎn)變成紅色，變成情況2）
5.兄弟節(jié)點(diǎn)為黑色，兄弟節(jié)點(diǎn)左子樹(shù)根節(jié)點(diǎn)為紅色（交換顏色，旋轉(zhuǎn)成為左左）
6.情況2和情況5，調(diào)整性質(zhì)5（將N刪掉，用子節(jié)點(diǎn)頂替，若子節(jié)點(diǎn)為紅色，則重繪為黑色）1234567

這里寫(xiě)圖片描述

實(shí)現(xiàn)：http://www.cnblogs.com/skywang12345/p/3624343.html

應(yīng)用

AVL樹(shù)：平衡二叉樹(shù)，一般是用平衡因子差值決定并通過(guò)旋轉(zhuǎn)來(lái)實(shí)現(xiàn)，左右子樹(shù)樹(shù)高差不超過(guò)1，那么和紅黑樹(shù)比較它是嚴(yán)格的平衡二叉樹(shù)，平衡條件非常嚴(yán)格（樹(shù)高差只有1），只要插入或刪除不滿足上面的條件就要通過(guò)旋轉(zhuǎn)來(lái)保持平衡。由于旋轉(zhuǎn)是非常耗費(fèi)時(shí)間的。我們可以推出AVL樹(shù)適合用于插入刪除次數(shù)比較少，但查找多的情況。

應(yīng)用相對(duì)其他數(shù)據(jù)結(jié)構(gòu)比較少。windows對(duì)進(jìn)程地址空間的管理用到了AVL樹(shù)。

? 紅黑樹(shù)：平衡二叉樹(shù)，通過(guò)對(duì)任何一條從根到葉子的簡(jiǎn)單路徑上各個(gè)節(jié)點(diǎn)的顏色進(jìn)行約束，確保沒(méi)有一條路徑會(huì)比其他路徑長(zhǎng)2倍，因而是近似平衡的。所以相對(duì)于嚴(yán)格要求平衡的AVL樹(shù)來(lái)說(shuō)，它的旋轉(zhuǎn)保持平衡次數(shù)較少。用于搜索時(shí)，插入刪除次數(shù)多的情況下我們就用紅黑樹(shù)來(lái)取代AVL。

紅黑樹(shù)應(yīng)用比較廣泛：

· 廣泛用在C++的STL中。map和set都是用紅黑樹(shù)實(shí)現(xiàn)的。

· 著名的linux進(jìn)程調(diào)度Completely Fair Scheduler,用紅黑樹(shù)管理進(jìn)程控制塊。

· epoll在內(nèi)核中的實(shí)現(xiàn)，用紅黑樹(shù)管理事件塊

· nginx中，用紅黑樹(shù)管理timer等

· Java的TreeMap實(shí)現(xiàn)

? B樹(shù)，B+樹(shù)：它們特點(diǎn)是一樣的，是多路查找樹(shù)，一般用于數(shù)據(jù)庫(kù)中做索引，因?yàn)樗鼈兎种Ф鄬訑?shù)少，因?yàn)榇疟P(pán)IO是非常耗時(shí)的，而像大量數(shù)據(jù)存儲(chǔ)在磁盤(pán)中所以我們要有效的減少磁盤(pán)IO次數(shù)避免磁盤(pán)頻繁的查找。
B+樹(shù)是B樹(shù)的變種樹(shù)，有n棵子樹(shù)的節(jié)點(diǎn)中含有n個(gè)關(guān)鍵字，每個(gè)關(guān)鍵字不保存數(shù)據(jù)，只用來(lái)索引，數(shù)據(jù)都保存在葉子節(jié)點(diǎn)。是為文件系統(tǒng)而生的。

? B+樹(shù)相對(duì)B樹(shù)磁盤(pán)讀寫(xiě)代價(jià)更低：因?yàn)锽+樹(shù)非葉子結(jié)點(diǎn)只存儲(chǔ)鍵值，單個(gè)節(jié)點(diǎn)占空間小，索引塊能夠存儲(chǔ)更多的節(jié)點(diǎn)，從磁盤(pán)讀索引時(shí)所需的索引塊更少，所以索引查找時(shí)I/O次數(shù)較B-Tree索引少，效率更高。而且B+Tree在葉子節(jié)點(diǎn)存放的記錄以鏈表的形式鏈接，范圍查找或遍歷效率更高。Mysql InnoDB用的就是B+Tree索引。

Trie樹(shù)：
? 又名單詞查找樹(shù)，一種樹(shù)形結(jié)構(gòu)，常用來(lái)操作字符串。它是不同字符串的相同前綴只保存一份。
相對(duì)直接保存字符串肯定是節(jié)省空間的，但是它保存大量字符串時(shí)會(huì)很耗費(fèi)內(nèi)存（是內(nèi)存）。
類(lèi)似的有：前綴樹(shù)(prefix tree)，后綴樹(shù)(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解決耗費(fèi)內(nèi)存問(wèn)題），以及前面說(shuō)的double array trie。
前綴樹(shù)：字符串快速檢索，字符串排序，最長(zhǎng)公共前綴，自動(dòng)匹配前綴顯示后綴。
后綴樹(shù)：查找字符串s1在s2中，字符串s1在s2中出現(xiàn)的次數(shù)，字符串s1,s2最長(zhǎng)公共部分，最長(zhǎng)回文串。

trie 樹(shù)的一個(gè)典型應(yīng)用是前綴匹配，比如下面這個(gè)很常見(jiàn)的場(chǎng)景，在我們輸入時(shí)，搜索引擎會(huì)給予提示。

img

還有比如IP選路，也是前綴匹配，一定程度會(huì)用到trie。