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

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

RUM猜想

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

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

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

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

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

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

索引類型

(1) 無索引

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

(2) 主鍵索引

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

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

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

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

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

非聚簇索引 — 邏輯組織

(3) KV存儲（哈希表）

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

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

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

(5) 位圖索引

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

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

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

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

• 本地二級索引 — 這是“默認(rèn)”/“正?！钡亩壦饕?/li>
• 全局二級索引 - 可能對于讀取重型的鍵范圍查詢和無法避免的散列收集最有意義
• 實(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

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

(10) 跳躍表

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

示例場景：游戲排行榜

(11) 向量索引

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

示例場景：機(jī)器學(xué)習(xí)問題

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

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

(13) Count-min sketch

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

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

(14) 一致性級別

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