上篇有提到加上 Index 能讓搜尋變快，但能變快的原因是什麼呢？這是因為在 PostgreSQL 中在欄位加上 Index 後，會將該欄的資料長成 B-Tree 的樣子。使用 B-Tree 的資料結構，就能比原本依序單筆尋找還要快速。

為什麼不用 Binary Tree？

你可能會想說，為什麼不是使用 Binary Tree 就好？Binary Tree 不是也很快嗎？

但是因為在資料庫中的筆數可能太多了，使用 Binary Tree 有一個致命的缺點，就是筆數多時，會讓 Binary Tree 的階層無比巨大，導致搜尋時間變慢許多。

B-Tree 的特性

而 B-Tree 的特點，就是一個 node 可以存多個 value，這樣可以讓樹的階層減少，增加搜尋的速度。以下面這張圖為例，當要尋找某個數字時，會根據數值範圍決定該往哪個 child node 走：

網頁連結： https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree 在 PostgreSQL 的實作

不過在 PostgreSQL 中，B-Tree 的 node 是用 page 的概念來實作，這個 page 有固定的大小。所以每個 node 並沒有固定有幾個 value，而是取決於 page 的大小。

PostgreSQL B-Tree indexes are multi-level tree structures, where each level of the tree can be used as a doubly-linked list of pages.

要怎麼看得到上面描述的東西呢？

查看 Page 大小

在 PostgreSQL 中，每個 Page 的大小預設為 8192 bytes（8 KB），可以用以下 SQL 查看：

SHOW block_size 

這代表 B-Tree 的一個節點（Node）最多可以存放 8 KB 的資料。

使用 pageinspect 來檢視 B-Tree

如果想要看到更多關於 B-Tree 的資訊，可以用 pageinspect 的 extension 來查看。

1. 安裝 pageinspect

CREATE EXTENSION IF NOT EXISTS pageinspect;

2. 檢視 B-Tree Metadata

我們可以透過 bt_metap 來查看某個 Index 的 B-Tree 結構：

SELECT * FROM bt_metap('your_index_name');

從 level 就可以得知目前這個 B-Tree 有幾層。

查看特定 Page 的 Index Tuples

如果想要看到特定 page 內的資訊，可以使用：

SELECT * FROM bt_page_items('your_index_name', 1); -- page 1

• itemoffset：Index 的順序
• ctid：該筆資料對應原始 table 內的位址（block_number, row_number）
• data：Index 儲存的值（raw binary）

這裡也可以發現，page 內的資訊是用 tuple 的資料結構儲存原始資料的位址，如同官方文件上寫的：

Each leaf page contains tuples that point to table rows.

檢視 Index 的使用狀況

我們還可以透過 pg_stat_all_indexes 來查看 Index 是否有被查詢使用：

SELECT * FROM pg_stat_all_indexes WHERE relname = 'your_table_name';

• idx_scan：表示該 Index 被用來查詢的次數。
• idx_tup_read：透過該 Index 讀取的 Tuple 數量。
• idx_tup_fetch：透過該 Index 取得的 Tuple 數量。

如果 idx_scan 為 0 或是很小，代表這個 Index 可能沒有被有效使用，可能就要檢查是否需要調整設定。

Hash Index

在 PostgreSQL 中其實有另外一個 Hash Index，可以用來快速比對兩個值是否相同。他是透過雜湊函數（hash function）轉換成一組固定的雜湊值。這個雜湊值會用來決定資料應該放在哪裡，存放的位置為雜湊桶頁面 （bucket page）。當我們需要比對兩個值是否相同的時候，資料庫會將查詢值進行相同的雜湊計算，並直接跳到對應的 bucket page 尋找資料。

不過 Hash Index 比較少被使用是因為他只支援等值查詢（=），但是等值查詢在 B-tree 中也能使用，所以大部分的情況還是都會選擇直接使用 B-tree Index。

重點回顧

1. 在 PostgreSQL 中在欄位加上 Index 後，會使用 B-Tree 的資料結構，利用空間換取時間的方式，讓搜尋變快。
2. PostgreSQL 透過 Page 概念來實作 B-Tree，每個 Page 大小為 8 KB。
3. 使用 pageinspect ，可以檢視 Index 內部結構。
4. 透過 pg_stat_all_indexes 可以查看 Index 是否有被有效使用，避免不必要的 Index 設定。

參考資料

https://www.postgresql.org/docs/current/btree.html#BTREE-IMPLEMENTATION