1. 表的頁面結(jié)構(gòu)

1.1 表和索引相關(guān)文件的布局

在數(shù)據(jù)庫內(nèi)部，表和索引作為數(shù)據(jù)庫對象是通過oid(object identifier, 對象標(biāo)識(shí)符)來管理的，而這些數(shù)據(jù)文件由變量relfilenode管理。
數(shù)據(jù)庫和堆表對象的 oid 分別存儲(chǔ)在pg_database和pg_class 中。
表和索引在剛創(chuàng)建的時(shí)候，relfilenode值是與其oid一致的；但是在后續(xù)維護(hù)過程中relfilenode會(huì)發(fā)生變化，oid不會(huì)變。

查看t1表的oid及relfilenode值：

select relname,oid,relfilenode from pg_class where relname='t1';

查看t1表的文件：

select pg_relation_filepath('t1');

表和索引的relfilenode值會(huì)被一些命令所改變。
例如對表t1執(zhí)行TRUNCATE命令，會(huì)為表分配一個(gè)新的relfilenode(24595)，刪除舊的數(shù)
據(jù)文件(24592)，并創(chuàng)建一個(gè)新的數(shù)據(jù)文件(24595)：

新建表：

對表執(zhí)行truncate后：

當(dāng)表和索引的文件大小超過1GB時(shí)，會(huì)創(chuàng)建并使用一個(gè)名為relfilenode.1的新文件。
如果新文件也填滿了，則會(huì)創(chuàng)建下一個(gè)名為 relfilenode.2的新文件，以此類推。
之所以采用1G的大小，是因?yàn)樵?2位操作系統(tǒng)中，允許的單個(gè)文件最大大小一般是2G或者4G，采用1G可以避免操作系統(tǒng)integer溢出的問題。在實(shí)踐中發(fā)現(xiàn)1G也是最合理的值。

在數(shù)據(jù)庫系統(tǒng)內(nèi)部，這些文件(主體數(shù)據(jù)文件、空閑空間映射文件、可見性映射文件等)也被稱為相應(yīng)關(guān)系的分支(fork)。
表、索引、TOAST表都?xì)w類為關(guān)系。
每個(gè)關(guān)系(relation)可能會(huì)有4種分支，分支編號(hào)分別為0、1、2、3

• 0號(hào)分支main為關(guān)系數(shù)據(jù)文件本體
• 1號(hào)分支fsm(空閑空間映射)保存了main分支中空閑空間的信息
• 2號(hào)分支vm(可見性映射)保存了main分支中可見性的信息
• 3號(hào)分支init 是很少見的特殊分支，通常表示不被日志記錄的表與索引

1.2 堆表文件的內(nèi)部結(jié)構(gòu)

其中重點(diǎn)如下：

• pd_lsn: 存儲(chǔ)最近改變該頁面的xlog位置。（在集群環(huán)境下，xlog堆積等問題可能會(huì)用到）
• pd_checksum: 存儲(chǔ)頁面校驗(yàn)和。（頁面損壞問題可能會(huì)用到）
• pd_lower，pd_upper: pd_lower指向行指針(line pointer)的尾部，即圖中的pg_linp[1]，pd_upper指向最后那個(gè)元組，即圖中的Tuple2（元組是從頁尾往前寫的。所以Tuple2實(shí)際上是時(shí)間上更靠后的）。
• pd_special: 索引頁面中使用，它指向特殊空間的開頭。（pd_special在堆表中是個(gè)固定值，沒什么用；但在索引中是串聯(lián)形成平衡樹的）
• pd_line: 行指針，四字節(jié)，每一條元組會(huì)有一個(gè)行指針指向真實(shí)元組位置。
• Tuple: 存放真實(shí)的元組數(shù)據(jù)，
  注意元組是從頁面的尾部向前堆積的，元組和行指針之間的是數(shù)據(jù)頁的空閑空間。

page選擇8192大小的原因主要是出于在常用場景表列數(shù)支持下，對性能和效率的考慮。
以下是幾個(gè)主要因素:

• 1.內(nèi)存管理: 內(nèi)存中，在linux下，每頁的大小通常為4096，選擇8192(顯然選擇4096更合適，為什么選擇的8192?)大小的頁面可以更好地適應(yīng)內(nèi)存緩存的頁大小，從而提高查詢效率。
• 2.I/O性能: 磁盤I/O操作是數(shù)據(jù)庫性能的一個(gè)重要瓶頸。選擇8192(16384更加減少磁盤I/O操作次數(shù)，為什么還是8192?)大小的頁面可以更好地利用磁盤塊的大小，從而減少磁盤I/O操作次數(shù)，提高數(shù)據(jù)庫的整體性能。
• 3.并發(fā)控制: Postgresql數(shù)據(jù)庫使用多版本并發(fā)控制(MVCC)機(jī)制來支持并發(fā)訪問。選擇8192大小的頁面可以更好地控制并發(fā)訪問時(shí)的鎖競爭，從而提高并發(fā)性能。

注：8KB也是理論和長期實(shí)踐得出的結(jié)論。

1.3 行頁面結(jié)構(gòu)

即元組的結(jié)構(gòu)：

• t_xmin: 代表插入此元組的事務(wù)xid;
• t_xmax: 代表更新或者刪除此元組的事務(wù)xid，如果該元組插入后未進(jìn)行更新或者刪除，txmax=0:
• t_cid: commandid，代表在當(dāng)前事務(wù)中已經(jīng)執(zhí)行過多少條sql，例如執(zhí)行第一sql時(shí)cid=0，執(zhí)行第二條sql時(shí)cid=1;
• t_ctid: 保存著指向自身或者新元組的元組標(biāo)識(shí)(tid)，由兩個(gè)數(shù)字組成，第一個(gè)數(shù)字代表物理塊號(hào)，或者叫頁面號(hào)，第二個(gè)數(shù)字代表元組號(hào)。
  在元組更新后tid指向新版本的元組，否則指向自己，這樣其實(shí)就形成了新舊元組之間的“元組鏈”，這個(gè)鏈在元組查找和定位上起著重要作用。

如下面例子中，我們事務(wù)100先插入一條記錄，值為a，t_ctid值是(0,1)表示在0頁的1號(hào)元組。
然后我們事務(wù)101將其更新為b，結(jié)果如下：

在此基礎(chǔ)上我們的事務(wù)102將其刪除，結(jié)果如下：

1.4 頁面結(jié)構(gòu)的變化：DML

依賴于安裝pageinspect插件。

參考：

https://cloud.tencent.com/developer/article/1377728

然后執(zhí)行vacuum：

2. FSM及VM的介紹

2.1 FSM

空閑空間管理：用于快速定位到表文件中的空閑空間以便于插入新數(shù)據(jù)及整理空間從而提高空間利用率。
在mvcc機(jī)制中，當(dāng)進(jìn)行增刪改這些操作時(shí)，都會(huì)產(chǎn)生一些舊版本的數(shù)據(jù)，在vacuum時(shí)會(huì)清理掉這些舊版本數(shù)據(jù)，這樣數(shù)據(jù)塊上就會(huì)存在很多空閑的空間。
如果不能夠把這些空間再次利用起來，每次新插入數(shù)據(jù)最后一個(gè)數(shù)據(jù)塊不夠空間時(shí)都分配一個(gè)新的數(shù)據(jù)塊，那么數(shù)據(jù)文件的膨脹速度就會(huì)非?？?，因此便通過FSM來實(shí)現(xiàn)這一功能。

為了能夠更快地查找合適的空閑空間，F(xiàn)SM文件不應(yīng)該太大。
因此在FSM中存儲(chǔ)的并不是實(shí)際的文件塊空閑空間的大小，而是僅僅用一個(gè)字節(jié)來記錄。
該字節(jié)的值用于描述對應(yīng)文件塊中空閑空間的范圍。
以頁面的1/256的粒度記錄空閑空間，最大映射值是255。

為避免混淆，我們將表中的文件塊稱為表塊，將FSM文件中的文件塊稱為FSM塊。
對于每個(gè)表塊，不論其中是否有空閑空間，在FSM文件中都能找到對應(yīng)的字節(jié)。

為了實(shí)現(xiàn)快速查找，F(xiàn)SM文件中并不是簡單地使用數(shù)組順序存儲(chǔ)每個(gè)表塊的空閑空間，而是使用了樹結(jié)構(gòu)。
在FSM塊之間使用了一個(gè)三層樹的結(jié)構(gòu)，第0層和第1層為輔助層，第2層FSM塊中用于實(shí)際存放各表塊的空閑空間值。

• 第0層: FSM塊只有一個(gè)，作為樹根，葉子節(jié)點(diǎn)從左至右順序?qū)?yīng)第1層FSM塊的根節(jié)點(diǎn)。表示第1層數(shù)據(jù)塊中的最大值。
• 第1層: FSM塊可以有多個(gè)，作為第0層FSM塊的子節(jié)點(diǎn)，葉子節(jié)點(diǎn)從左至右順序?qū)?yīng)第2層FSM塊的根節(jié)點(diǎn)。表示第2層數(shù)據(jù)塊中的最大值。
• 第2層: FSM塊也可以有多個(gè)，作為第1層FSM塊的子節(jié)點(diǎn)，葉子節(jié)點(diǎn)從左至右順序?qū)?yīng)表文件中的每一個(gè)表塊的空閑空間值。

每個(gè)FSM塊大小默認(rèn)為8KB，除去必要的文件塊頭部信息，F(xiàn)SM塊中剩下的空間都用來存儲(chǔ)塊內(nèi)的二叉樹結(jié)構(gòu)，每個(gè)葉子節(jié)點(diǎn)用一個(gè)字節(jié)記錄，因此FSM塊內(nèi)大約可以保存4000個(gè)葉子節(jié)點(diǎn)，其他空間均用作構(gòu)成最大堆二叉樹的輔助節(jié)點(diǎn)。
in reality, it holds (BLCKSZ-headers)/2, or ~4000 with default BLCKSZ
這樣，一個(gè)FSM文件中總共可以記錄4000^{3個(gè)葉子節(jié)點(diǎn)(表塊)，遠(yuǎn)遠(yuǎn)大于2}32——單個(gè)表的
最大塊數(shù)，這樣三層的結(jié)構(gòu)足以記錄表文件所有文件塊的空閑空間值。

例: 假如表文件有1024*1024個(gè)block(即:8G)，則需要FSM文件的block數(shù)量為:
1024 × 1024 - 4000 = 262余576，再加上第0層和第1層的fsm塊，所以共需要265個(gè)block，則共需要fsm文件大小為:265 × 8KB ≈ 2.07MB，這個(gè)空間極小。

2.2 創(chuàng)建FSM

文件并不是在創(chuàng)建表文件的時(shí)候就被創(chuàng)建，而是推遲到需要使用FSM文件的時(shí)候，即：
執(zhí)行VACUUM操作時(shí)或?yàn)榱瞬迦朐M而第一次查找FSM文件時(shí)才創(chuàng)建。

在創(chuàng)建FSM文件時(shí)，會(huì)預(yù)先創(chuàng)建三個(gè)FSM塊: 第0號(hào)為根節(jié)點(diǎn)即第0層的FSM 塊，第1號(hào)為第1層的第一個(gè)節(jié)點(diǎn)，第2號(hào)為第2層的第一個(gè)節(jié)點(diǎn)。
當(dāng)?shù)?號(hào)FSM塊滿了之后，將會(huì)擴(kuò)展新的FSM塊，該工作主要調(diào)用函數(shù)fsm_extend進(jìn)行實(shí)現(xiàn)。

2.3 VM

多版本并發(fā)控制(MVCC)，當(dāng)事務(wù)刪除或者更新元組時(shí)，并非從物理上刪除，而是將其標(biāo)記無效，最終再通過VACUUM命令清理這些無效元組，真正的物理刪除發(fā)生在清理過程。
清理無效元組時(shí)，需要先找到無效元組，再進(jìn)行清理。如果沒有其他技術(shù)，需要遍歷查找每一個(gè)頁，找到頁中的無效元組。如果更新和刪除不是很頻繁，表文件中大部分頁都沒有無效元組，如果遍歷所有頁，開銷會(huì)非常大。
為了能加快VACUUM查找包含無效元組的文件塊的過程，Vastbase為每個(gè)表文件設(shè)置了一個(gè)附屬文件 -- 可見性映射表。

對于每個(gè)表文件，其對應(yīng)的VM文件命名為: “關(guān)系表OID_vm”。
VM中為表的每一個(gè)文件塊(Page)設(shè)置了一位，用來標(biāo)記該文件塊是否包含無效元組。
當(dāng)表塊中所有元組都對當(dāng)前事務(wù)可見時(shí)，表塊對應(yīng)的位才被設(shè)置為1，VACUUM會(huì)忽略掃描
對應(yīng)的表塊，所以能大大提高VACUUM的效率。
當(dāng)對某個(gè)表塊中的元組進(jìn)行更新或者刪除后，那么該表塊在VM文件中對應(yīng)位置的標(biāo)志位將
被置為0。

（除了提升vacuum效率外，還有一個(gè)常見場景是提升索引掃描效率）

VM文件被劃分為若干個(gè)文件塊(簡稱VM塊)。
VM塊中除了必要的標(biāo)記信息（頭信息）外，其他的每一位都對應(yīng)于一個(gè)表塊（或頁）。每一位中0表示存在，1表示不存在。

假設(shè)該表包含三個(gè)頁面，第0頁和第2頁包含死元組，而第1頁不包含死元組。（0表示存在，1表示不存在）
表的可見性映射中保存著那些頁面包含死元組的信息。
在這種情況下，清理過程可以參考VM中的信息，跳過第一個(gè)頁面。

2.4 FSM及VM的應(yīng)用

vacuum、索引

• 查詢優(yōu)化器使用可見性映射
  如果一個(gè)查詢使用了索引掃描，并且目標(biāo)頁被標(biāo)記為ALL_VISIBLE，則可以跳過 Heap Tuple
  的可見性檢查(Heap Fetch)。
  這減少了 I/O 和 CPU 開銷，提升查詢性能。
• 支持 HOT 更新優(yōu)化(Heap-Only Tuple)
  當(dāng)一個(gè)頁面被標(biāo)記為ALL_VISIBLE，HOT更新可以在不創(chuàng)建新索引項(xiàng)的情況下進(jìn)行(因?yàn)椴?br> 需要修改索引鍵)。
  這有助于減少索引膨脹。

3. 索引的頁面結(jié)構(gòu)

3.1 索引

• 1、索引類型: Vastbase支持不同類型的索引，包括B-tree、哈希、GiST、SP-GiST、GIN和BRIN等。
  每種索引類型都有自己的適用場景和優(yōu)缺點(diǎn)。
• 2、索引結(jié)構(gòu): 不同類型的索引采用不同的數(shù)據(jù)結(jié)構(gòu)，例如B-tree采用平衡樹結(jié)構(gòu)，哈希采用哈希表結(jié)構(gòu)，GiST和SP-GiST采用通用搜索樹結(jié)構(gòu)等。
  這些結(jié)構(gòu)都是為了提高查詢效率和節(jié)省存儲(chǔ)空間而設(shè)計(jì)的。
• 3、索引操作: Vastbase提供了多種索引操作，包括創(chuàng)建索引、刪除索引、修改索引、查詢索引等。
  通過這些操作，可以對索引進(jìn)行管理和優(yōu)化，以滿足不同的查詢需求。
• 4、索引優(yōu)化: 在實(shí)際應(yīng)用中，為了提高查詢效率和節(jié)省存儲(chǔ)空間，需要對索引進(jìn)行優(yōu)化。Vastbase提供了多種優(yōu)化方法，包括索引列的選擇、索引類型的選擇、多列索引的使用、索引覆蓋等。
  這些方法都是為了在滿足查詢需求的前提下，盡可能地提高查詢效率和節(jié)省存儲(chǔ)空間。

3.2 Btree索引的頁面結(jié)構(gòu)

• B樹是平衡有序的，每個(gè)頁面與根都有相同數(shù)量的內(nèi)部頁面分隔開，搜索任何值都需要花費(fèi)類似的時(shí)間。
• B樹是多分支的，B樹的深度不會(huì)太深，對于大表4-5層就夠了。
• 同一級(jí)別的頁面通過雙向列表相互連接，可以通過列表的一個(gè)方向或另一個(gè)方向獲得有序數(shù)據(jù)集，不必每次都返回到根。（通過前面提到的pd_special串聯(lián)起來）
• B樹適用于范圍和等值查詢。

【meta page】

• 1)meta page 原數(shù)據(jù)塊, 指向root page的page_id
• 2)root page根塊，一個(gè)頁面存儲(chǔ)，當(dāng)存不下時(shí)就有l(wèi)eaf page,或者branch page
• 3)根，枝，葉組成了索引的高度

3.3 索引的成長

通過bt_metap()看meta page的基本信息：下圖中root page是1個(gè)，0層，即一個(gè)root page就能存下例子中的100條。
通過bt_page_stat()看索引統(tǒng)計(jì)信息：其中1是剛才查出來的root號(hào)；可以看到item有100個(gè)，頁面大小是8k，btpo是它的深度，0表示就1層，跟bt_metap()中的level是對應(yīng)的，btpo_flags=3意思是即是根節(jié)點(diǎn)又是葉子節(jié)點(diǎn)。
通過bt_page_items()查看ctid（哪個(gè)頁的哪個(gè)元組，以及具體數(shù)據(jù)），可通過ctid看在表里的數(shù)據(jù)（顯示的info是16進(jìn)制，轉(zhuǎn)換后得到插入值，由此可反推數(shù)據(jù)）。

然后我們插入更多的數(shù)據(jù)（10000條）；
再看根節(jié)點(diǎn)已經(jīng)變成了3號(hào)，level變成了1，也就是兩層了；btpo即前面的level；
此時(shí)再看葉子結(jié)點(diǎn)，記錄的已經(jīng)不是一個(gè)值了，而是一個(gè)范圍

我們繼續(xù)插入更多的數(shù)據(jù)：
root已經(jīng)變成了411號(hào)，深度已經(jīng)3層；
我們查看branch信息

3.4 Vacuum對索引的影響

更新后再vacuum，信息變了；所以vacuum不僅對表有影響，對索引也有影響。

3.5 索引的分裂