?概覽數(shù)據(jù)庫索引創(chuàng)建
數(shù)據(jù)庫表是一組行/記錄。然而,這些行并不是以表的形式物理存儲的,它們存儲在塊上的數(shù)據(jù)頁中。要在這些數(shù)據(jù)頁中找到特定記錄需要掃描多個文件。為了改進這一點,我們創(chuàng)建索引。索引是小型的引用表,用于根據(jù)索引值存儲對行的引用。
索引是一種使數(shù)據(jù)檢索更快的數(shù)據(jù)庫對象。 但是,索引的創(chuàng)建也需要時間,并且會占用額外的空間。因此,在選擇正確的索引創(chuàng)建策略時,我們必須審慎選擇。
RUM猜想
類似于CAP定理,RUM猜想指出 —— 我們無法設計一個存儲系統(tǒng)的訪問方法,使其在以下三個方面都最優(yōu):
讀、更新和內(nèi)存。
讀取、更新、內(nèi)存 — 以兩者優(yōu)化為代價的第三者。
- 讀取開銷: 定義為總讀取數(shù)據(jù)量(主要 + 輔助)與預期讀取的主要數(shù)據(jù)量之間的比率。通過讀取放大來衡量。
- 更新開銷: 定義為總寫入數(shù)據(jù)量(主要 + 輔助)與預期更新的主要數(shù)據(jù)量之間的比率。通過寫入放大來衡量。
根據(jù)上圖中的讀取和寫入模式,數(shù)據(jù)庫將分為以下5類:
- 平衡 — 讀取和寫入均勻分布。很少發(fā)生。
- 讀取優(yōu)化 — 寫入較少,讀取較多(分析工作負載)
- 寫入優(yōu)化 — 寫入較多,讀取較少(事務工作負載)
- 熱分區(qū)讀取 — 來自某些數(shù)據(jù)部分的讀取較多
- 熱分區(qū)寫入 — 向某些部分的寫入較多
索引類型
(1) 無索引
實現(xiàn):Kafka(可以看作純粹是WAL)、數(shù)據(jù)倉庫
(2) 主鍵索引
主鍵 = 分區(qū)鍵 + (可選)排序鍵
- 分區(qū)鍵 = “什么節(jié)點”
- 排序鍵 = 滿足唯一性約束的剩余內(nèi)容
有各種分區(qū)策略,其中一些如下:
- 哈希分區(qū)(也稱為“一致性哈希”)
- 范圍分區(qū)?隨機數(shù)
聚簇索引 — 物理數(shù)據(jù)組織
非聚簇索引 — 邏輯組織
(3) KV存儲(哈希表)
- 哈希分區(qū)在這里非常有意義
- 只能在RAM中進行,這就是為什么我們在PostgreSQL等數(shù)據(jù)庫中看不到它
- 實現(xiàn):Memcache、Redis
(4) B樹 — 讀取優(yōu)化
- 實現(xiàn):DynamoDB、PostgreSQL
- 變體:Bw-tree 等(查看 Alex Petrov 的《Database Internals》)
- 它是許多數(shù)據(jù)庫中的默認索引。
(5) 位圖索引
用于OLAP的讀取和內(nèi)存優(yōu)化。
(6) LSM樹 — 寫入優(yōu)化
實現(xiàn):Cassandra、Spanner
(7) 二級索引 — 更多讀取優(yōu)化
- 本地二級索引 — 這是“默認”/“正?!钡亩壦饕?/li>
- 全局二級索引 - 可能對于讀取重型的鍵范圍查詢和無法避免的散列收集最有意義
- 實現(xiàn):DynamoDB,可能是Spanner
(8) 多維索引
- 連接索引
- R樹(實現(xiàn):PostgreSQL)
- 四叉樹(實現(xiàn):Elasticsearch)
- 地理哈希(實現(xiàn):Redis)
(9) 倒排索引
實現(xiàn):ElasticSearch、PostgreSQL、Redis
示例場景:Twitter 等社交媒體站點的文本搜索,google.com,GitHub
(10) 跳躍表
實現(xiàn):Redis(僅)
示例場景:游戲排行榜
(11) 向量索引
實現(xiàn):Pinecone、Facebook 的 Faiss、PlanetScale 的 MySQL 分支、Redis
示例場景:機器學習問題
(12) 數(shù)據(jù)立方體和物化視圖
實現(xiàn):數(shù)據(jù)倉庫,支持OLAP的數(shù)據(jù)庫
(13) Count-min sketch
- 就RUM而言,以極端OLAP讀取延遲為代價換取精度
- 實現(xiàn):Flink、AWS Firehose、Druid、Spark streams、Redis
對于分布式系統(tǒng),還有其他有趣的權衡。其中之一是PACELC,它說:如果是分區(qū),選擇可用性和一致性之間的折衷,否則選擇延遲和一致性之間的折衷。有許多級別的一致性可供折衷選擇(以及隔離級別)。
(14) 一致性級別
- 強一致性
- 最終一致性
- 一致前綴
- 單調讀取