5、B+樹

(圖e)

B+數(shù)是B-樹的一種變形，它與B-樹的差別在于(圖e為3階B+樹)：

(1)有n棵子樹的節(jié)點(diǎn)含有n個關(guān)鍵字;

(2)所有的葉子節(jié)點(diǎn)包含了全部關(guān)鍵字的信息，及指向這些關(guān)鍵字記錄的指針，且葉子節(jié)點(diǎn)本身按關(guān)鍵字大小自小到大順序鏈接;

(3)所有非終端節(jié)點(diǎn)可以看成是索引部分，節(jié)點(diǎn)中僅含有其子樹(根節(jié)點(diǎn))中最大(或最小)關(guān)鍵字，所有B+樹更像一個索引順序表;

(4)對B+樹進(jìn)行查找運(yùn)算，一是從最小關(guān)鍵字起進(jìn)行順序查找，二是從根節(jié)點(diǎn)開始，進(jìn)行隨機(jī)查找。

6、字典樹(trie樹)

(圖f)

字典樹是一種以樹形結(jié)構(gòu)保存大量字符串。以便于字符串的統(tǒng)計和查找，經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。具有以下特點(diǎn)(圖f)：

(1)根節(jié)點(diǎn)為空;

(2)除根節(jié)點(diǎn)外，每個節(jié)點(diǎn)包含一個字符;

(3)從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對應(yīng)的字符串。

(4)每個字符串在建立字典樹的過程中都要加上一個區(qū)分的結(jié)束符，避免某個短字符串正好是某個長字符串的前綴而淹沒。

7、后綴樹

后綴樹則是一個字符串的所有后綴組成的字典樹。具體內(nèi)容再前幾章已講過。

8、廣義后綴樹

廣義后綴樹是好幾個字符串的的所有后綴組成的字典樹，同樣每個字符串的所有后綴都具有一個相同的結(jié)束符，不同字符串的結(jié)束符不同。

6.圖 (Graph)

圖是由結(jié)點(diǎn)的有窮集合V和邊的集合E組成。其中，為了與樹形結(jié)構(gòu)加以區(qū)別，在圖結(jié)構(gòu)中常常將結(jié)點(diǎn)稱為頂點(diǎn)，邊是頂點(diǎn)的有序偶對，若兩個頂點(diǎn)之間存在一條邊，就表示這兩個頂點(diǎn)具有相鄰關(guān)系。

1.圖的存儲結(jié)構(gòu)