5、B+樹

(圖e)

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

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

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

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

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

6、字典樹(trie樹)

(圖f)

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

(1)根節(jié)點為空;

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

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

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

7、后綴樹

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

8、廣義后綴樹

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

6.圖 (Graph)

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

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