常見的索引方式
如果沒有索引,對於無序的資料,我們查詢資料就只能依靠遍歷,演算法時間複雜度為O(N);對於有序的資料,可以使用二分查詢, 時間複雜度為O(lgN),但是此處的有序還有一個要求,就是資料是空間連續的,即如果是使用連結串列儲存,即便是有序也無法使用 二分查詢。
現實世界中,資料的出現總是無序的,對於無序的資料,常有這麼幾個資料結構來構建索引:
-
Hash table:ofollow,noindex" target="_blank">https://en.wikipedia.org/wiki/Hash_table 雜湊表,教科書上有,太經典了,不說了。其優點是查詢速度非常快,缺點是無序,因此無法藉助雜湊表進行範圍查詢。現實 中的例子是:Redis中的KV。
-
LSM Tree:https://en.wikipedia.org/wiki/Log-structured_merge-tree 對於機械硬碟來說,隨機讀寫非常耗時,但是順序讀寫非常的快。LSM Tree就特別適合處理這種情況。首先,在記憶體中會維護一個 表(比如雜湊表,或者跳躍表)來實現KV,每次寫入之前,都會先追加到硬碟上的一個Append Only的日誌檔案。然後週期性的合併 老的Append Only的檔案。Append Only的日誌檔案每達到一定大小之後,就寫入到一個新的檔案,老的檔案會進行合併&排序。此後 查詢起來就很快了,先從記憶體中的資料查詢,沒找到就從日誌檔案裡從新到舊查詢,因為檔案都是有序的,所以可以使用二分查詢。
-
B-Tree:https://en.wikipedia.org/wiki/B-tree B-Tree,通過控制樹的高度,當節點儲存的資料很多時,每下降一層,就可以過濾掉很多資料。當保證節點所儲存的資料是有序的 這個特性時,B-Tree就可以進行範圍查找了。查詢時間複雜度為O(lgN)。現實中的例子是常見的關係型資料庫中的索引實現。