在創(chuàng)建索引時厚骗，通常采用的數(shù)據(jù)結構有：Hash示启、二叉搜索樹、紅黑樹领舰、B樹以及B+樹夫嗓。這里主要介紹這些數(shù)據(jù)結構的設計思想，不做底層實現(xiàn)研究冲秽。
-
Hash結構：通過一定的算法計算數(shù)據(jù)的Hash值舍咖，然后得到數(shù)據(jù)的存放位置，例如JAVA中的HashMap采用就是這種數(shù)據(jù)索引結構锉桑。
- 優(yōu)點：檢索時間快排霉，平均檢索時間為O(1)。
- 缺點：
- 因為Hash值是通過算法計算出來的民轴，存在Hash碰撞的幾率攻柠，比如HashMap對于Hash值相同的數(shù)據(jù)，會在Hash值所在桶創(chuàng)建一個鏈表后裸，用于存放相同Hash值的數(shù)據(jù)辙诞。
- 在數(shù)據(jù)量很大的情況下，內(nèi)存無法加載全部的數(shù)據(jù)索引轻抱。
-
二叉搜索樹：定義規(guī)則為“左邊節(jié)點值比根節(jié)點小，右邊節(jié)點值比根節(jié)點大旦部，并且左右子節(jié)點都是排序樹”祈搜。
- 優(yōu)點：可以解決大量數(shù)據(jù)索引無法一次加載進內(nèi)存中的問題，二叉搜索樹可以批量加載數(shù)據(jù)進內(nèi)存士八。
- 缺點：
- 檢索時間與樹的高度有關容燕，樹的高度越高，檢索次數(shù)及時間相對就會越久婚度。
- 極端情況下蘸秘，如果數(shù)據(jù)本身就是有序的，二叉搜索樹會退化成鏈表蝗茁，性能會急劇降低醋虏。
-
紅黑樹：紅黑樹是一種自平衡二叉樹，主要解決二叉搜索樹在極端情況下退化成鏈表的情況哮翘，在數(shù)據(jù)插入的時候同時調(diào)整整個樹颈嚼，使其節(jié)點盡量均勻分布，保證平衡性饭寺，目的在于降低樹的高度阻课，提高查詢效率叫挟。
- 優(yōu)點：解決二叉搜索樹的極端情況的退化問題。
-
缺點：檢索時間依舊與樹的高度有關限煞，當數(shù)據(jù)量很大時抹恳，樹的高度就會很高，檢索的次數(shù)就會比較多署驻，檢索的時間會比較久奋献，效率低。
image(圖片采自51CTO公眾號)
-
B樹：B樹是一種多路搜索樹硕舆，每個子節(jié)點可以擁有多于2個子節(jié)點秽荞，M路的B樹最多可擁有M個子節(jié)點。設計成多路抚官，其目的是為了降低樹的高度扬跋，降低查詢次數(shù)，提高查詢效率凌节。
- 雖然多路可以降低樹的高度钦听，但是如果設計成無限多路，就會退化成有序數(shù)組倍奢，一般B樹的使用場景是用于文件的索引朴上，這些索引會存放于硬盤中，有時內(nèi)存是無法一次性加載完卒煞，此時就無法進行查找痪宰。
-
如果全部在內(nèi)存中，紅黑樹的查找效率要高于B樹畔裕，但是涉及到磁盤操作衣撬，B樹要優(yōu)于紅黑樹，所以在JDK1.8版本的HashMap中扮饶，如果單個桶的鏈表長度多于8或全部桶的鏈表總長度多余64具练，會將鏈表轉(zhuǎn)換成紅黑樹。
Image
(圖片采自51CTO公眾號)
-
B+樹：B+樹是對于B樹進行優(yōu)化的多路搜索樹甜无，主要設計是將數(shù)據(jù)全部存放于葉子節(jié)點扛点，并將葉子節(jié)點用指針進行鏈表鏈接。
- 主要使用場景：常用于數(shù)據(jù)庫的索引岂丘。
- 數(shù)據(jù)庫的索引一般數(shù)據(jù)量不小陵究，同時又存放于磁盤中，采用多路搜索樹奥帘，可以降低樹的高度畔乙，同時在大數(shù)據(jù)量下可以分批載入內(nèi)存，提高查詢效率翩概。
- 不同于B樹的使用場景牲距，數(shù)據(jù)庫的查詢中返咱，我們一般查詢的數(shù)量不會是單條數(shù)據(jù)，例如列表常用查詢中的分頁查詢--查詢第1頁的10條數(shù)據(jù)牍鞠，此時如果采用B樹咖摹，需要進行樹的中序遍歷，可能需要跨層訪問难述。
-
而B+樹的所有數(shù)據(jù)全部存放于葉子節(jié)點上萤晴，且葉子節(jié)點之間采用指針進行鏈表鏈接，一次查詢多條時胁后，確定首尾位置店读，便可以方便的確定多條數(shù)據(jù)位置。
Image(圖片采自51CTO公眾號)
- 主要使用場景：常用于數(shù)據(jù)庫的索引岂丘。
