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

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

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

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

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

圖片

B 樹

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

Hash Index（哈希索引）

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

Skiplist（跳表）

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

SSTable（Sorted String Table）

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

LSM 樹（Log-Structured Merge Tree）

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

Suffix Tree（后綴樹）

后綴樹通常用于存儲(chǔ)字符串列表。它也被稱為 Trie 的壓縮版本。后綴樹常用于字符串的搜索和匹配，比如容忍一定輸入錯(cuò)誤的字符搜索，正則表達(dá)式匹配，最長(zhǎng)子串問(wèn)題等。

Inverted Index（倒排索引）

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

R 樹

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