今天我們來聊聊數據庫索引。
無論數據存儲于磁盤還是內存，我們都需要有一種高效的數據結構來訪問和獲取數據。
那么我們應該選用哪一種索引結構呢？我們需要考慮如下幾個因素：
- 數據存儲于內存還是磁盤？
- 數據格式和結構是怎樣的？是字符串，數字，還是地理坐標？
- 搜索時是否需要精確匹配？是否需要容忍一定的輸入錯誤？
- 系統是讀操作多還是寫操作多？
我們來看看 8 種常用的數據庫索引結構。
圖片
B 樹
B 樹/B+ 樹作為最流行的數據庫索引數據結構，是基于磁盤的解決方案，其讀/寫性能穩定。不同于傳統的二叉樹，B 樹的單個節點中可以存儲大量的鍵值，這樣樹的高度較低，可以加快搜索和插入元素的速度，減少磁盤的 I/O 操作。B 樹的時間復雜度為 O(logN)。
Hash Index（哈希索引）
Map 數據結構的常用實現。哈希值映射到存儲桶，該存儲桶存儲數據的偏移值。這樣我們可以根據鍵值很快地查找數據。
Skiplist（跳表）
一種常見的內存索引類型，在 redis SortedSet 中使用。跳表解決了鏈表搜索效率低下的問題。每個節點都包含幾個前向指針，因此我們不被遍歷過程中的步長所限制，可以跳過一些節點來加快搜索速度。
SSTable（Sorted String Table）
SSTable 是 Apache Cassandra 和其他 NoSQL 數據庫使用的一種持久性文件格式。它可以對 memtable 里的內存數據進行排序以便快速訪問，并將其存儲在磁盤上的持久有序、不可變的一組文件中。不可變意味著 SSTables 永遠不會被修改。它們稍后會合并到新的 SSTables 中，或者隨著數據的更新而被刪除。SSTable 與 LSM Tree 一起使用。與 B 樹相比，這種結構對于寫入量大、快速增長的超大數據集效率更高。
LSM 樹（Log-Structured Merge Tree）
LSM Tree 在 SSTable 的基礎上提供一整套存儲解決方案。它由兩層結構組成：memtable （內存）和 SSTable（磁盤）。新數據先寫入 memtable 中，如果 memtable 過大，那就會 flush 到磁盤的 SSTable 上。各個 SSTable 上會有重復的鍵值，在一段時間后會進行合并壓縮。我們可以看到，每個寫入請求實際上都只在內存中進行，所以 LSM Tree 的寫入吞吐量明顯高于 B Tree。
Suffix Tree（后綴樹）
后綴樹通常用于存儲字符串列表。它也被稱為 Trie 的壓縮版本。后綴樹常用于字符串的搜索和匹配，比如容忍一定輸入錯誤的字符搜索，正則表達式匹配，最長子串問題等。
Inverted Index（倒排索引）
用于高效的文檔索引，比如 Lucene。在倒排索引中，索引按單詞進行組織，每個單詞都指向包含該單詞的文檔列表。
R 樹
用于多維信息的搜索，包含地理坐標、矩形、多邊形等。我們可以借助這種索引來搜索附近的餐館，找到最近的加油站，檢索附近所有路段等。
