大家好，我是君哥。

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

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

B+ 樹和 B- 樹

B+ 樹

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

圖片

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

B- 樹

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

圖片

隨機查詢：因為 B- 樹在非葉子節(jié)點也能存儲數(shù)據(jù)，B- 樹可能在非葉子節(jié)點提前終止查詢，查詢路徑更短。

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

PostgreSQL 索引

索引介紹

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

圖片

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

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

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

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

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

圖片

下表對每個屬性進行解釋：

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

三個優(yōu)化

Deduplication

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

Index Only Scan

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

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

反向鍵索引

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

CREATE INDEX idx_emp_id ON tb_emploee(emp_id REVERSE);

總結(jié)

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