今天我們來聊聊數(shù)據(jù)庫索引。

無論數(shù)據(jù)存儲于磁盤還是內(nèi)存，我們都需要有一種高效的數(shù)據(jù)結(jié)構(gòu)來訪問和獲取數(shù)據(jù)。

那么我們應該選用哪一種索引結(jié)構(gòu)呢？我們需要考慮如下幾個因素：

• 數(shù)據(jù)存儲于內(nèi)存還是磁盤？
• 數(shù)據(jù)格式和結(jié)構(gòu)是怎樣的？是字符串，數(shù)字，還是地理坐標？
• 搜索時是否需要精確匹配？是否需要容忍一定的輸入錯誤？
• 系統(tǒng)是讀操作多還是寫操作多？

我們來看看 8 種常用的數(shù)據(jù)庫索引結(jié)構(gòu)。

圖片

B 樹

B 樹/B+ 樹作為最流行的數(shù)據(jù)庫索引數(shù)據(jù)結(jié)構(gòu)，是基于磁盤的解決方案，其讀/寫性能穩(wěn)定。不同于傳統(tǒng)的二叉樹，B 樹的單個節(jié)點中可以存儲大量的鍵值，這樣樹的高度較低，可以加快搜索和插入元素的速度，減少磁盤的 I/O 操作。B 樹的時間復雜度為 O(logN)。

Hash Index（哈希索引）

Map 數(shù)據(jù)結(jié)構(gòu)的常用實現(xiàn)。哈希值映射到存儲桶，該存儲桶存儲數(shù)據(jù)的偏移值。這樣我們可以根據(jù)鍵值很快地查找數(shù)據(jù)。

Skiplist（跳表）

一種常見的內(nèi)存索引類型，在 Redis SortedSet 中使用。跳表解決了鏈表搜索效率低下的問題。每個節(jié)點都包含幾個前向指針，因此我們不被遍歷過程中的步長所限制，可以跳過一些節(jié)點來加快搜索速度。

SSTable（Sorted String Table）

SSTable 是 Apache Cassandra 和其他 NoSQL 數(shù)據(jù)庫使用的一種持久性文件格式。它可以對 memtable 里的內(nèi)存數(shù)據(jù)進行排序以便快速訪問，并將其存儲在磁盤上的持久有序、不可變的一組文件中。不可變意味著 SSTables 永遠不會被修改。它們稍后會合并到新的 SSTables 中，或者隨著數(shù)據(jù)的更新而被刪除。SSTable 與 LSM Tree 一起使用。與 B 樹相比，這種結(jié)構(gòu)對于寫入量大、快速增長的超大數(shù)據(jù)集效率更高。

LSM 樹（Log-Structured Merge Tree）

LSM Tree 在 SSTable 的基礎(chǔ)上提供一整套存儲解決方案。它由兩層結(jié)構(gòu)組成：memtable （內(nèi)存）和 SSTable（磁盤）。新數(shù)據(jù)先寫入 memtable 中，如果 memtable 過大，那就會 flush 到磁盤的 SSTable 上。各個 SSTable 上會有重復的鍵值，在一段時間后會進行合并壓縮。我們可以看到，每個寫入請求實際上都只在內(nèi)存中進行，所以 LSM Tree 的寫入吞吐量明顯高于 B Tree。

Suffix Tree（后綴樹）

后綴樹通常用于存儲字符串列表。它也被稱為 Trie 的壓縮版本。后綴樹常用于字符串的搜索和匹配，比如容忍一定輸入錯誤的字符搜索，正則表達式匹配，最長子串問題等。

Inverted Index（倒排索引）

用于高效的文檔索引，比如 Lucene。在倒排索引中，索引按單詞進行組織，每個單詞都指向包含該單詞的文檔列表。

R 樹

用于多維信息的搜索，包含地理坐標、矩形、多邊形等。我們可以借助這種索引來搜索附近的餐館，找到最近的加油站，檢索附近所有路段等。