我們知道，MySQL 的索引設計使用了 B+Tree，而 PostgreSQL 使用了 B-Tree，
那 PostgreSQL 為什么不使用 B+Tree 做索引結構呢？今天就來聊一聊這個話題。

B+TreeB+Tree

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

B+Tree的第二個特點是葉子節點用雙向鏈表串聯起來，這樣范圍查詢優勢很大，時間復雜度為O(logmN+K)。

B-Tree跟

B+Tree不一樣的是，B-tree所有節點都可以存儲數據，包括根節點，內部節點，葉子節點。

隨機查詢：因為 B-Tree在非葉子節點也能存儲數據，B-Tree可能在非葉子節點提前終止查詢，查詢路徑更短。

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

索引介紹

PostgreSQL 索引對 B-Tree 進行了改造。改造后的索引結構如下圖：

上圖的索引結構中最頂層是元數據頁，存儲索引根節點頁相關信息。內部節點位于根節點下面，只包含鍵值和指向子頁面的指針。葉子頁位于最下面一層，存儲所有指向實際表數據行（TIDs）的指針。

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

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

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

PostgreSQL 索引頁格式如下，（下圖來自官網）:

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

三個優化

Deduplication

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

Index Only Scan

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

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

反向鍵索引

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

CREATE INDEX idx_emp_id ON tb_emploee(emp_id REVERSE);

PostgreSQL 的索引結構雖然叫 B-Tree，但其實它實現了 B+Tree的功能，并且在索引上做了一些優化，使索引效率更高。