PostgreSQL技術大講堂 - 第28講：索引內部結構
最新學訊：近期OCP認證正在報名中，因考試人員較多請盡快報名獲取最近考試時間，報名費用請聯系在線老師，甲骨文官方認證，報名從速！
我要咨詢
PostgreSQL從小白到專家，是從入門逐漸能力提升的一個系列教程，內容包括對PG基礎的認知、包括安裝使用、包括角色權限、包括維護管理、、等內容，希望對熱愛PG、學習PG的同學們有幫助，歡迎持續關注CUUG PG技術大講堂。
第28講：索引內部結構
內容1 : PG數據庫眾多開放特性概述
內容2 : 索引結構與生長
內容3 : Autovacuum自動維護索引
內容4：btree、hash索引應用場景
PostgreSQL 開放特性概述
開放的數據類型接口，使得PG支持超級豐富的數據類型，除了傳統數據庫支持的類型，還支持GIS，JSON，RANGE，IP，ISBN，圖像特征值，化學，DNA等等擴展的類型，用戶還可以根據實際業務擴展更多的類型。
開放的操作符接口，使得PG不僅僅支持常見的類型操作符，還支持擴展的操作符，例如 距離符，邏輯并、交、差符號，圖像相似符號，幾何計算符號等等擴展的符號，用戶還可以根據實際業務擴展更多的操作符。
開放的外部數據源接口，使得PG支持豐富的外部數據源，例如可以通過FDW讀寫MySQL, redis, mongo, oracle, sqlserver, hive, www, hbase, ldap, 等等只要你能想到的數據源都可以通過FDW接口讀寫。
開放的語言接口，使得PG支持幾乎地球上所有的編程語言作為數據庫的函數、存儲過程語言，例如plpython , plperl , pljava , plR , plCUDA , plshell等等。用戶可以通過language handler擴展PG的語言支持。
開放的索引接口，使得PG支持非常豐富的索引方法，例如btree , hash , gin , gist , sp-gist , brin , bloom , rum , zombodb , bitmap (greenplum extend)，用戶可以根據不同的數據類型，以及查詢的場景，選擇不同的索引。
PG內部還支持BitmapAnd, BitmapOr的優化方法，可以合并多個索引的掃描操作，從而提升多個索引數據訪問的效率。
索引結構
· PostgreSQL索引結構
meta page和root page是一定有的，meta page需要一個頁來存儲，表示指向root page的page id。
隨著記錄數的增加，一個root page可能存不下所有的heap item，就會有leaf page，甚至branch page，甚至多層的branch page。
一共有幾層branch 和 leaf，可以用btree page元數據的 level 來表示。
Btree索引
· Btree索引
索引工具介紹
· 如何訪問索引結構
1、create extension pageinspect
2、查看meta塊
select * from bt_metap('tab1_pkey');
3、查看root page的stats
select * from bt_page_stats('tab1_pkey',1);
4、查看root(leaf)頁里面的內容：
select * from bt_page_items('tab1_pkey',1);
5、根據ctid來訪問表：
select * from tab1 where ctid='(0,1)';
Btree索引
· 一層結構
有1層(0)結構，包括meta page, root page
1、環境準備：
postgres=# create extension pageinspect;
postgres=# create table tab1(id int primary key, info text);
CREATE TABLE
postgres=# insert into tab1 select generate_series(1,100), md5(random()::text);
INSERT 0 100
postgres=# vacuum analyze tab1;
VACUUM
2、查看meta塊
indx=# select * from bt_metap('tab1_pkey');
magic | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples
--------+---------+------+-------+----------+-----------+-------------+-------------------------
340322 | 4 | 1 | 0 | 1 | 0 | 0 | 100
此時level 0，root塊為1。
3、根據root page id = 1，查看root page的stats
ndx=# select * from bt_page_stats('tab1_pkey',1);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
1 | l | 100 | 0 | 16 | 8192 | 6148 | 0 | 0 | 0 | 3
(1 row)
此時：btpo=0，說明處于第0層。
btpo_flags=3，說明它既是leaf又是root頁。即：root_page(2)+leaf_page(1)=3
注：
meta page
root page ：表示為btpo_flags=2
branch page ：表示為btpo_flags=0
leaf page ：表示為btpo_flags=1
4、查看root(leaf)頁里面的內容：
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (0,1) | 16 | f | f | 01 00 00 00 00 00 00 00
2 | (0,2) | 16 | f | f | 02 00 00 00 00 00 00 00
3 | (0,3) | 16 | f | f | 03 00 00 00 00 00 00 00
4 | (0,4) | 16 | f | f | 04 00 00 00 00 00 00 00
5 | (0,5) | 16 | f | f | 05 00 00 00 00 00 00 00
此時ctid就是指向表的行id，類似于oracle的rowid，PG中為tid。
data就是索引列的值，16進制。
5、根據ctid來訪問表：
indx=# select * from tab1 where ctid='(0,1)';
id | info
----+----------------------------------
1 | 7c3402d464509541c0d788e1afe2c90f
6、查看表的數據來驗證：
indx=# select * from tab1 limit 2;
id | info
----+----------------------------------
1 | 7c3402d464509541c0d788e1afe2c90f
2 | f19de3e3255b9f1f676584fd50ad73d9
· 二層結構
有2層(0，1)結構，包括meta page, root page, leaf page
準備工作：
繼續往表中插入數據，讓索引生長。
insert into tab1 select generate_series(101,10000), md5(random()::text) ;
1、查看meta數據：
indx=# select * from bt_metap('tab1_pkey');
magic | version | root | level | fastroot | fastlevel | oldest_xact | last_cleanup_num_tuples
--------+---------+------+-------+----------+-----------+-------------+-------------------------
340322 | 4 | 3 | 1 | 3 | 1 | 0 | -1
root塊在第3塊。
2、根據root page id 查看root page的stats：
indx=# select * from bt_page_stats('tab1_pkey',3);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
3 | r | 28 | 0 | 15 | 8192 | 7596 | 0 | 0 | 1 | 2
3、查看root page存儲的 leaf page items (指向leaf page)：
indx=# select * from bt_page_items('tab1_pkey',3);
itemoffset | ctid | itemlen | nulls | vars | data
------------+--------+---------+-------+------+-------------------------
1 | (1,0) | 8 | f | f |
2 | (2,1) | 16 | f | f | 6f 01 00 00 00 00 00 00
3 | (4,1) | 16 | f | f | dd 02 00 00 00 00 00 00
一共28個葉塊。data存儲的是這個leaf page存儲的最小值。
4、查看第一個葉塊統計：
indx=# select * from bt_page_stats('tab1_pkey',1);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
1 | l | 367 | 0 | 16 | 8192 | 808 | 0 | 2 | 0 | 1
btpo=0，說明是最底層，btpo_flags=1，即葉塊。
5、查看其它葉塊統計，當查詢到第30塊時，顯示超出塊的范圍。
indx=# select * from bt_page_stats('tab1_pkey',29);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
29 | l | 118 | 0 | 16 | 8192 | 5788 | 28 | 0 | 0 | 1
6、查看第一個葉塊的內容：
indx=# select * from bt_page_items('tab1_pkey',1);
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (3,1) | 16 | f | f | 6f 01 00 00 00 00 00 00
2 | (0,1) | 16 | f | f | 01 00 00 00 00 00 00 00
3 | (0,2) | 16 | f | f | 02 00 00 00 00 00 00 00
7、根據CTID查看表中的行數據：
select * from t_btree where ctid='(0,1)';
id | info
----+----------------------------------
1 | 9892a864978b60abb3a30e9c23298967
· 三層結構
記錄數超過1層結構的索引所能夠存儲的記錄數時，會分裂為2層結構，除了meta page和root page，還可能包含1層branch page以及1層leaf page。
1、繼續往tab1表插入新數據，導致btree增長一層：
insert into tab1 select generate_series(10001,100000), md5(random()::text) ;
postgres=# vacuum analyze tab1;
2、查看meta page，可以看到root page id = 412, 索引的level=2，即包括1級 branch 和 1級 leaf。
postgres=# select * from bt_metap('tab1_pkey');
magic | version | root | level | fastroot | fastlevel
--------+---------+------+-------+----------+-----------
340322 | 2 | 412 | 2 | 412 | 2
3、根據root page id 查看root page的stats
indx=# select * from bt_page_stats('tab1_pkey', 412);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
412 | r | 11 | 0 | 15 | 8192 | 7936 | 0 | 0 | 2 | 2
btpo = 2 當前在第二層，另外還表示下層是1。
btpo_flags = 2 說明是root page
4、查看root page存儲的 branch page items (指向branch page)
postgres=# select * from bt_page_items('tab1_pkey', 412);
itemoffset | ctid | itemlen | nulls | vars | data
------------+----------+---------+-------+------+-------------------------
1 | (3,1) | 8 | f | f |
2 | (2577,1) | 16 | f | f | e1 78 0b 00 00 00 00 00
3 | (1210,1) | 16 | f | f | ec 3a 18 00 00 00 00 00
4 | (2316,1) | 16 | f | f | de 09 25 00 00 00 00 00
5、根據branch page id查看stats
indx=# select * from bt_page_stats('tab1_pkey', 3);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
3 | i | 316 | 0 | 15 | 8192 | 1836 | 0 | 2247 | 1 | 0
6、查看branch page存儲的 leaf page ctid (指向leaf page)
indx=# indx=# select * from bt_page_items('tab1_pkey', 3);
itemoffset | ctid | itemlen | nulls | vars | data
------------+----------+---------+-------+------+-------------------------
1 | (1748,1) | 16 | f | f | 32 56 0c 00 00 00 00 00
2 | (1,0) | 8 | f | f |
3 | (3519,1) | 16 | f | f | 47 08 00 00 00 00 00 00
只要不是最右邊的頁，第一條都代表右頁的起始item。
第二條才是當前頁的起始ctid
注意所有branch page的起始item對應的data都是空的。
也就是說它不存儲當前branch page包含的所有leaf pages的索引字段內容的最小值。
7、根據ctid 查看leaf page的統計：
indx=# select * from bt_page_stats('tab1_pkey', 1);
blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags
-------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------
1 | l | 234 | 0 | 16 | 8192 | 3468 | 0 | 2952 | 0 | 1
btpo = 0 當前在第0層，即最底層，這里存儲的是heap ctid
btpo_flags = 1 說明是leaf page
第0層葉塊，第1層枝塊，第2層root塊。
8、查看leaf頁的指向表的ctid：
indx=# select * from bt_page_items('tab1_pkey', 1);
itemoffset | ctid | itemlen | nulls | vars | data
------------+------------+---------+-------+------+-------------------------
1 | (1509,1) | 16 | f | f | 25 09 00 00 00 00 00 00
2 | (4072,81) | 16 | f | f | 05 00 00 00 00 00 00 00
3 | (1035,12) | 16 | f | f | 07 00 00 00 00 00 00 00
9、通過ctid查看表的數據：
indx=# select * from tab2 where ctid='(1748,1)';
id | info
---------+----------------------------------
2222345 | aa2555d335e54892040bf20843ee71af
索引案例應用
利用查看索引數據塊的變化，去證明Autovacuum是否會維護索引。
1、環境搭建
create table tbl_test (id int, info text, c_time timestamp);
insert into tbl_test select generate_series(1,100000),md5(random()::text),clock_timestamp();
create index tbl_test_id_ind on tbl_test (id);
2、索引信息
--查看索引元數據
select * from bt_metap('tbl_test_id_ind');
--查看索引root根統計
select * from bt_page_stats('tbl_test_id_ind',3);
--查看索引葉塊內容(此時沒有發生數據更新)
indx=# select * from bt_page_items('tbl_test_id_ind',1);
itemoffset | ctid | itemlen | nulls | vars | data
------------+---------+---------+-------+------+-------------------------
1 | (3,1) | 16 | f | f | 6f 01 00 00 00 00 00 00
2 | (0,1) | 16 | f | f | 01 00 00 00 00 00 00 00
3 | (0,2) | 16 | f | f | 02 00 00 00 00 00 00 00
4 | (0,3) | 16 | f | f | 03 00 00 00 00 00 00 00
3、更新表數據，導致autovacuum觸發
update tbl_test set info=md5(random()::text) where id < 20060;
4、查看索引葉塊的內容變化(autovacuum前)
indx=# select * from bt_page_items('tbl_test_id_ind',1);
itemoffset | ctid | itemlen | nulls | vars | data
------------+-----------+---------+-------+------+-------------------------
1 | (1,1) | 16 | f | f | a3 00 00 00 00 00 00 00
2 | (0,1) | 16 | f | f | 01 00 00 00 00 00 00 00
3 | (934,63) | 16 | f | f | 01 00 00 00 00 00 00 00
4 | (0,2) | 16 | f | f | 02 00 00 00 00 00 00 00
5 | (934,64) | 16 | f | f | 02 00 00 00 00 00 00 00
6 | (0,3) | 16 | f | f | 03 00 00 00 00 00 00 00
7 | (934,65) | 16 | f | f | 03 00 00 00 00 00 00 00
注意紅色的為被更新的索引行。
5、查看索引葉塊的內容變化(autovacuum后)
indx=# select * from bt_page_items('tbl_test_id_ind',1);
itemoffset | ctid | itemlen | nulls | vars | data
------------+-----------+---------+-------+------+-------------------------
1 | (1,1) | 16 | f | f | a3 00 00 00 00 00 00 00
2 | (934,63) | 16 | f | f | 01 00 00 00 00 00 00 00
3 | (934,64) | 16 | f | f | 02 00 00 00 00 00 00 00
4 | (934,65) | 16 | f | f | 03 00 00 00 00 00 00 00
5 | (934,66) | 16 | f | f | 04 00 00 00 00 00 00 00
觀察后發現索引塊的信息更新了，原來的索引行被刪除。
說明autovacuum會自動維護索引信息。
索引維護
· 索引維護
testdb=# reindex INDEX id_data_ind2;
Reindex后索引的relfilenode就發生變化：
testdb=# select relname,oid,relfilenode from pg_class
where relname='id_data_ind2';
relname | oid | relfilenode
--------------+-------+-------------
id_data_ind2 | 65538 | 65546
Btree索引應用場景
· PostgreSQL B-Tree是一種變種(高并發B樹管理算法)
應用場景
b-tree適合所有的數據類型，支持排序，支持大于、小于、等于、大于或等于、小于或等于的搜索。
索引與遞歸查詢結合，還能實現快速的稀疏檢索。
示例
postgres=# create table t_btree(id int, info text);
CREATE TABLE
postgres=# insert into t_btree select generate_series(1,10000), md5(random()::text) ;
INSERT 0 10000
postgres=# create index idx_t_btree_1 on t_btree using btree (id);
CREATE INDEX
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_btree where id=1;
· Hash索引結構
哈希索引項只存儲每個索引項的哈希代碼，而不是實際的數據值
應用場景
hash索引存儲的是被索引字段VALUE的哈希值，只支持等值查詢。
hash索引特別適用于字段VALUE非常長(不適合b-tree索引，因為b-tree一個PAGE至少要存儲3個索引行，所以不支持特別長的VALUE)的場景，例如很長的字符串，并且用戶只需要等值搜索，建議使用hash index。
示例
postgres=# create table t_hash (id int, info text);
CREATE TABLE
postgres=# insert into t_hash select generate_series(1,100), repeat(md5(random()::text),10000);
INSERT 0 100
-- 使用b-tree索引會報錯，因為長度超過了1/3的索引頁大小
postgres=# create index idx_t_hash_1 on t_hash using btree (info);
ERROR: index row size 3720 exceeds maximum 2712 for index "idx_t_hash_1"
HINT: Values larger than 1/3 of a buffer page cannot be indexed.
Consider a function index of an MD5 hash of the value, or use full text indexing.
postgres=# create index idx_t_hash_1 on t_hash using hash (info);
CREATE INDEX
postgres=# explain (analyze,verbose,timing,costs,buffers) select * from t_hash where info in (select info from t_hash limit 1);
