本篇我們來總結(jié)一下數(shù)據(jù)結(jié)構(gòu)的特點，幫助大家更好的運用。

1、數(shù)組

數(shù)組使用下標查找十分迅速，但計算機內(nèi)存有限，故數(shù)組的長度有限，數(shù)組初始化就需要聲明數(shù)組的長度。實際應用當中的數(shù)據(jù)往往十分龐大；無序數(shù)組的查找最壞情況需要遍歷整個數(shù)組；后來人們提出了二分查找，二分查找要求數(shù)組的構(gòu)造一定有序，二分法查找解決了普通數(shù)組查找復雜度過高的問題。任何一種數(shù)組無法解決的問題就是插入、刪除操作比較復雜（插入、刪除需根據(jù)數(shù)組下標來操作），因此，在一個增刪查改比較頻繁的數(shù)據(jù)結(jié)構(gòu)中，數(shù)組不會被優(yōu)先考慮。

2、普通鏈表

普通鏈表由于它的結(jié)構(gòu)特點被證明根本不適合進行查找

3、哈希

哈希表是數(shù)組和鏈表的折中，同時它的設計依賴散列函數(shù)的設計，數(shù)組不能無限長、鏈表也不適合查找，所以也適合大規(guī)模的查找。

4、二叉查找樹

二叉查找樹因為可能退化成鏈表，同樣不適合進行查找

5、AVL樹

AVL樹是為了解決可能退化成鏈表問題，但是AVL樹的旋轉(zhuǎn)過程非常麻煩，因此插入和刪除很慢，也就是構(gòu)建AVL樹比較麻煩。

6、紅黑樹

紅黑樹是平衡二叉樹和AVL樹的折中，因此是比較合適的。集合類中的Map、關聯(lián)數(shù)組具有較高的查詢效率，它們的底層實現(xiàn)就是紅黑樹。

7、多路查找樹

多路查找樹是大規(guī)模數(shù)據(jù)存儲中，實現(xiàn)索引查詢這樣一個實際背景下，樹節(jié)點存儲的元素數(shù)量是有限的(如果元素數(shù)量非常多的話，查找就退化成節(jié)點內(nèi)部的線性查找了)，這樣導致二叉查找樹結(jié)構(gòu)由于樹的深度過大而造成磁盤I/O讀寫過于頻繁，進而導致查詢效率低下。

8、B樹

B樹適用于讀寫相對大的數(shù)據(jù)塊的存儲系統(tǒng)，例如磁盤。它的應用是文件系統(tǒng)及部分非關系型數(shù)據(jù)庫索引。

9、B+樹

B+樹在B樹基礎上，為葉子結(jié)點增加鏈表指針(B樹+葉子有序鏈表)，所有關鍵字都在葉子結(jié)點 中出現(xiàn)，非葉子結(jié)點作為葉子結(jié)點的索引；B+樹總是到葉子結(jié)點才命中。通常用于關系型數(shù)據(jù)庫(如Mysql)和操作系統(tǒng)的文件系統(tǒng)中。

10、B*樹

B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點再增加指向兄弟的指針, 在B+樹基礎上，為非葉子結(jié)點也增加鏈表指針，將結(jié)點的最低利用率從1/2提高到2/3。

11、R樹

R樹是用來做空間數(shù)據(jù)存儲的樹狀數(shù)據(jù)結(jié)構(gòu)。例如給地理位置，矩形和多邊形這類多維數(shù)據(jù)建立索引。

12、Trie樹

Trie樹是自然語言處理中最常用的數(shù)據(jù)結(jié)構(gòu)，很多字符串處理任務都會用到。Trie樹本身是一種有限狀態(tài)自動機，還有很多變體。什么模式匹配、正則表達式，都與這有關。