大家好，我是君哥。

我們知道，MySQL 的索引設(shè)計(jì)使用了 B+ 樹，而 PostgreSQL 使用了 B- 樹，

那 PostgreSQL 為什么不使用 B+ 樹做索引結(jié)構(gòu)呢？今天就來(lái)聊一聊這個(gè)話題。

B+ 樹和 B- 樹

B+ 樹

B+ 樹主鍵索引的葉子節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)，非葉子節(jié)點(diǎn)（索引節(jié)點(diǎn)）則存儲(chǔ) key 和指針。這樣存儲(chǔ)的優(yōu)勢(shì)是可以在索引節(jié)點(diǎn)通過(guò)二分查找快速找到數(shù)據(jù)所在頁(yè)，時(shí)間復(fù)雜度為 O(logmN),其中 N 是總的節(jié)點(diǎn)數(shù)量，m 是每個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)個(gè)數(shù)。找到數(shù)據(jù)頁(yè)后再去數(shù)據(jù)頁(yè)中找數(shù)據(jù)就很容易了。

圖片

B+ 樹的第二個(gè)特點(diǎn)是葉子節(jié)點(diǎn)用雙向鏈表串聯(lián)起來(lái)，這樣范圍查詢優(yōu)勢(shì)很大，時(shí)間復(fù)雜度為O(logmN+K)。

B- 樹

跟 B+ 樹不一樣的是，B- 樹所有節(jié)點(diǎn)都可以存儲(chǔ)數(shù)據(jù)，包括根節(jié)點(diǎn)，內(nèi)部節(jié)點(diǎn)，葉子節(jié)點(diǎn)。

圖片

隨機(jī)查詢：因?yàn)?B- 樹在非葉子節(jié)點(diǎn)也能存儲(chǔ)數(shù)據(jù)，B- 樹可能在非葉子節(jié)點(diǎn)提前終止查詢，查詢路徑更短。

范圍查詢：B- 樹查詢一個(gè)數(shù)據(jù)范圍時(shí)需要中序遍歷多個(gè)層級(jí)，這一點(diǎn)效率不如 B+ 樹。

PostgreSQL 索引

索引介紹

PostgreSQL 索引對(duì) B- 樹進(jìn)行了改造。改造后的索引結(jié)構(gòu)如下圖：

圖片

上圖的索引結(jié)構(gòu)中最頂層是元數(shù)據(jù)頁(yè)，存儲(chǔ)索引根節(jié)點(diǎn)頁(yè)相關(guān)信息。內(nèi)部節(jié)點(diǎn)位于根節(jié)點(diǎn)下面，只包含鍵值和指向子頁(yè)面的指針。葉子頁(yè)位于最下面一層，存儲(chǔ)所有指向?qū)嶋H表數(shù)據(jù)行（TIDs）的指針。

什么是 TID？PostgreSQL 采用堆表存儲(chǔ)，數(shù)據(jù)獨(dú)立于索引存儲(chǔ)在一個(gè)無(wú)序的結(jié)構(gòu)中。數(shù)據(jù)行插入時(shí)，數(shù)據(jù)庫(kù)會(huì)找到一個(gè)空閑的空間來(lái)存放它，并記錄一個(gè)唯一的物理地址，稱為 TID，由頁(yè)號(hào)和行指針組成。

因?yàn)?B- 樹的葉子節(jié)點(diǎn)只保存 TIDs，不保存真實(shí)數(shù)據(jù)，因此每個(gè)數(shù)據(jù)頁(yè)能保存更多的葉子節(jié)點(diǎn)。跟 B+ 樹相比，在相同數(shù)據(jù)量下，B- 樹高度更低。

PostgreSQL 索引中無(wú)論是內(nèi)部節(jié)點(diǎn)還是葉子節(jié)點(diǎn)，數(shù)據(jù)都以遞增順序存儲(chǔ)，同一層的數(shù)據(jù)頁(yè)由雙向鏈表連接。因此通過(guò)遍歷鏈表就可以獲取一個(gè)有序的數(shù)據(jù)集，范圍查詢并不需要中序遍歷。

PostgreSQL 索引頁(yè)格式如下，（下圖來(lái)自官網(wǎng)）:

圖片

下表對(duì)每個(gè)屬性進(jìn)行解釋：

再回到文章題目的問(wèn)題，雖然 PostgreSQL 的索引結(jié)構(gòu)在工程上被稱作 B-Tree，但其實(shí)它實(shí)現(xiàn)了 B+ 樹的功能，從功能上看，他其實(shí)也是一棵 B+ 樹。

三個(gè)優(yōu)化

Deduplication

在索引中，如果存在大量相同的鍵值（比如一個(gè)被頻繁更新的狀態(tài)標(biāo)志），PostgreSQL 會(huì)將這些重復(fù)的鍵值合并存儲(chǔ)，只保留一個(gè)鍵值和多個(gè)對(duì)應(yīng)的 TID 列表，這大大節(jié)省了空間，提高了緩存效率。

Index Only Scan

雖然葉子節(jié)點(diǎn)不保存完整數(shù)據(jù)，但葉子節(jié)點(diǎn)中除了存儲(chǔ)鍵值和 TID，也可以保存查詢中需要的某幾個(gè)字段值（非索引列值），類似于覆蓋索引。

這樣，對(duì)于只查詢索引列和包含列的語(yǔ)句，可以不用通過(guò) TID 去堆上查找數(shù)據(jù)，直接通過(guò)索引就獲取到查詢結(jié)果。

反向鍵索引

PostgreSQL 可以創(chuàng)建反向排序的索引，這對(duì)于緩解插入熱點(diǎn)（如遞增主鍵、時(shí)間等字段）問(wèn)題非常有效。創(chuàng)建索引的時(shí)候需要指定反向索引，例如下面 SQL 給員工編號(hào)（emp_id）創(chuàng)建一個(gè)反向鍵索引：

CREATE INDEX idx_emp_id ON tb_emploee(emp_id REVERSE);

總結(jié)

PostgreSQL 的索引結(jié)構(gòu)雖然叫 B- 樹，但其實(shí)它實(shí)現(xiàn)了 B+ 樹的功能，并且在索引上做了一些優(yōu)化，使索引效率更高。