數(shù)據(jù)庫(kù)表是一組行/記錄。然而，這些行并不是以表的形式物理存儲(chǔ)的，它們存儲(chǔ)在塊上的數(shù)據(jù)頁(yè)中。要在這些數(shù)據(jù)頁(yè)中找到特定記錄需要掃描多個(gè)文件。為了改進(jìn)這一點(diǎn)，我們創(chuàng)建索引。索引是小型的引用表，用于根據(jù)索引值存儲(chǔ)對(duì)行的引用。

索引是一種使數(shù)據(jù)檢索更快的數(shù)據(jù)庫(kù)對(duì)象。 但是，索引的創(chuàng)建也需要時(shí)間，并且會(huì)占用額外的空間。因此，在選擇正確的索引創(chuàng)建策略時(shí)，我們必須審慎選擇。

RUM猜想

類似于CAP定理，RUM猜想指出 —— 我們無(wú)法設(shè)計(jì)一個(gè)存儲(chǔ)系統(tǒng)的訪問(wèn)方法，使其在以下三個(gè)方面都最優(yōu)：

讀、更新和內(nèi)存。

讀取、更新、內(nèi)存 — 以兩者優(yōu)化為代價(jià)的第三者。

• 讀取開銷： 定義為總讀取數(shù)據(jù)量（主要 + 輔助）與預(yù)期讀取的主要數(shù)據(jù)量之間的比率。通過(guò)讀取放大來(lái)衡量。
• 更新開銷： 定義為總寫入數(shù)據(jù)量（主要 + 輔助）與預(yù)期更新的主要數(shù)據(jù)量之間的比率。通過(guò)寫入放大來(lái)衡量。

根據(jù)上圖中的讀取和寫入模式，數(shù)據(jù)庫(kù)將分為以下5類：

• 平衡 — 讀取和寫入均勻分布。很少發(fā)生。
• 讀取優(yōu)化 — 寫入較少，讀取較多（分析工作負(fù)載）
• 寫入優(yōu)化 — 寫入較多，讀取較少（事務(wù)工作負(fù)載）
• 熱分區(qū)讀取 — 來(lái)自某些數(shù)據(jù)部分的讀取較多
• 熱分區(qū)寫入 — 向某些部分的寫入較多

索引類型

(1) 無(wú)索引

實(shí)現(xiàn)：Kafka（可以看作純粹是WAL）、數(shù)據(jù)倉(cāng)庫(kù)

(2) 主鍵索引

主鍵 = 分區(qū)鍵 + （可選）排序鍵

• 分區(qū)鍵 = “什么節(jié)點(diǎn)”
• 排序鍵 = 滿足唯一性約束的剩余內(nèi)容

有各種分區(qū)策略，其中一些如下：

• 哈希分區(qū)（也稱為“一致性哈?！保?/li>
• 范圍分區(qū)?隨機(jī)數(shù)

聚簇索引 — 物理數(shù)據(jù)組織

非聚簇索引 — 邏輯組織

(3) KV存儲(chǔ)（哈希表）

• 哈希分區(qū)在這里非常有意義
• 只能在RAM中進(jìn)行，這就是為什么我們?cè)赑ostgreSQL等數(shù)據(jù)庫(kù)中看不到它
• 實(shí)現(xiàn)：Memcache、Redis

(4) B樹 — 讀取優(yōu)化

• 實(shí)現(xiàn)：DynamoDB、PostgreSQL
• 變體：Bw-tree 等（查看 Alex Petrov 的《Database Internals》）
• 它是許多數(shù)據(jù)庫(kù)中的默認(rèn)索引。

(5) 位圖索引

用于OLAP的讀取和內(nèi)存優(yōu)化。

(6) LSM樹 — 寫入優(yōu)化

實(shí)現(xiàn)：Cassandra、Spanner

(7) 二級(jí)索引 — 更多讀取優(yōu)化

• 本地二級(jí)索引 — 這是“默認(rèn)”/“正常”的二級(jí)索引
• 全局二級(jí)索引 - 可能對(duì)于讀取重型的鍵范圍查詢和無(wú)法避免的散列收集最有意義
• 實(shí)現(xiàn)：DynamoDB，可能是Spanner

(8) 多維索引

• 連接索引
• R樹（實(shí)現(xiàn)：PostgreSQL）
• 四叉樹（實(shí)現(xiàn)：Elasticsearch）
• 地理哈希（實(shí)現(xiàn)：Redis）

(9) 倒排索引

實(shí)現(xiàn)：ElasticSearch、PostgreSQL、Redis

示例場(chǎng)景：Twitter 等社交媒體站點(diǎn)的文本搜索，google.com，GitHub

(10) 跳躍表

實(shí)現(xiàn)：Redis（僅）

示例場(chǎng)景：游戲排行榜

(11) 向量索引

實(shí)現(xiàn)：Pinecone、Facebook 的 Faiss、PlanetScale 的 MySQL 分支、Redis

示例場(chǎng)景：機(jī)器學(xué)習(xí)問(wèn)題

(12) 數(shù)據(jù)立方體和物化視圖

實(shí)現(xiàn)：數(shù)據(jù)倉(cāng)庫(kù)，支持OLAP的數(shù)據(jù)庫(kù)

(13) Count-min sketch

• 就RUM而言，以極端OLAP讀取延遲為代價(jià)換取精度
• 實(shí)現(xiàn)：Flink、AWS Firehose、Druid、Spark streams、Redis

對(duì)于分布式系統(tǒng)，還有其他有趣的權(quán)衡。其中之一是PACELC，它說(shuō)：如果是分區(qū)，選擇可用性和一致性之間的折衷，否則選擇延遲和一致性之間的折衷。有許多級(jí)別的一致性可供折衷選擇（以及隔離級(jí)別）。

(14) 一致性級(jí)別

• 強(qiáng)一致性
• 最終一致性
• 一致前綴
• 單調(diào)讀取