PostgreSQL 實(shí)現(xiàn)

PostgreSQL B-Tree 索引是多級(jí)樹結(jié)構(gòu)，其中樹的每個(gè)級(jí)別都可以用作雙鏈接的頁(yè)列表。 單個(gè)元頁(yè)存儲(chǔ)在索引的第一個(gè)段文件開(kāi)始時(shí)的固定位置。所有其他頁(yè)都是葉頁(yè)或內(nèi)部頁(yè)。葉頁(yè)是在樹的最低層上的頁(yè)。 所有其他層級(jí)由內(nèi)部頁(yè)組成。每個(gè)葉頁(yè)都包含指向表行的元組。每個(gè)內(nèi)部頁(yè)都包含指向樹中下一級(jí)別的元組。 通常，超過(guò) 99% 的頁(yè)面是葉頁(yè)。 內(nèi)部頁(yè)和葉頁(yè)都使用 第 68.6 節(jié)中描述的標(biāo)準(zhǔn)頁(yè)格式。

當(dāng)已有葉頁(yè)不能適應(yīng)傳入元組時(shí)，新葉頁(yè)將添加到B-Tree索引中。 page split操作通過(guò)將部分項(xiàng)目移動(dòng)到新頁(yè)面為最初屬于溢出頁(yè)上的項(xiàng)目提供空間。 頁(yè)拆分還必須插入新的downlink到父頁(yè)中的新頁(yè)，這可能會(huì)導(dǎo)致父頁(yè)依次拆分。 頁(yè)拆分“cascade upwards”以遞歸的方式。 當(dāng)根頁(yè)最終無(wú)法適合新的下行鏈接時(shí)，發(fā)生root page split操作。 通過(guò)創(chuàng)建比原始根頁(yè)高一個(gè)級(jí)別的新根頁(yè)，為樹結(jié)構(gòu)添加新級(jí)別。

重復(fù)項(xiàng)是葉頁(yè)元組（指向表行的元組），其中所有 索引鍵列的值與同一索引中至少一個(gè)其他葉頁(yè)元組的相應(yīng)列值匹配。 重復(fù)元組在實(shí)踐中很常見(jiàn)。 當(dāng)啟用可選技術(shù)：重復(fù)時(shí)，B-Tree 索引可以對(duì)重復(fù)項(xiàng)使用特殊的、節(jié)省空間的表達(dá)方式。

重復(fù)數(shù)據(jù)刪除的工作為通過(guò)定期將重復(fù)元組合并在一起，為每個(gè)組構(gòu)建一個(gè)posting list元組。 列鍵值在此表示形式中僅顯示一次。 后面跟著指向表中行的TID的排序數(shù)組。 這顯著減少了索引的存儲(chǔ)大小，在其中每個(gè)值（或列值的每個(gè)不同組合）平均出現(xiàn)多次時(shí)。 查詢的延遲可以顯著降低。 總體查詢吞吐量可能會(huì)顯著增加。 常規(guī)索引清空的開(kāi)銷也可以顯著降低。

當(dāng)插入的新項(xiàng)無(wú)法適應(yīng)現(xiàn)有葉頁(yè)時(shí)，重復(fù)數(shù)據(jù)刪除過(guò)程進(jìn)行緩慢。這可以防止（或至少延遲）葉頁(yè)拆分。 不像 GIN 倒排列表元組，B-Tree倒排列表元組不需要在每次插入新重復(fù)項(xiàng)時(shí)展開(kāi);它們僅僅是葉頁(yè)原始邏輯內(nèi)容的替代物理表示方式。 此設(shè)計(jì)優(yōu)先考慮混合讀寫工作負(fù)載的一致性能。 大多數(shù)客戶端應(yīng)用程序可以從使用重復(fù)數(shù)據(jù)刪除中獲得適度的性能收益。默認(rèn)情況下，將啟用重復(fù)數(shù)據(jù)刪除。

CREATE INDEX和 REINDEX 應(yīng)用重復(fù)數(shù)據(jù)刪除來(lái)創(chuàng)建倒排列表元組，盡管它們使用的策略有所不同。 每組重復(fù)的普通元組遇到從表中取出的排序輸入將合并到倒排列表元組，在添加到當(dāng)前掛起的葉頁(yè)之前。 單獨(dú)倒排列表元組盡可能以TIDs封裝。 葉頁(yè)以通常的方式寫出，沒(méi)有任何分開(kāi)的重復(fù)數(shù)據(jù)刪除步驟。 此策略非常適合CREATE INDEX和REINDEX，因?yàn)樗鼈兪且淮涡缘呐幚聿僮鳌?/p>

由于索引中重復(fù)值很少或沒(méi)有重復(fù)值，因此無(wú)法從重復(fù)數(shù)據(jù)刪除中獲益的寫頻繁工作負(fù)載將產(chǎn)生少量的、固定性能損耗（除非顯式禁用重復(fù)數(shù)據(jù)刪除）。 deduplicate_items存儲(chǔ)參數(shù)可用于禁用單個(gè)索引中的重復(fù)數(shù)據(jù)消除。 只讀工作負(fù)載永遠(yuǎn)不會(huì)有任何性能損失，因?yàn)樽x取倒排列表元組至少與讀取標(biāo)準(zhǔn)元組表示一樣高效。 禁用重復(fù)數(shù)據(jù)刪除通常沒(méi)有幫助。

在 MVCC下B-Tree 索引不能直接感知，同一邏輯表行可能有多個(gè)現(xiàn)存版本;對(duì)于索引，每個(gè)元組都是一個(gè)獨(dú)立對(duì)象，需要自己的索引條目。 “Version duplicates”有時(shí)可能會(huì)累積并對(duì)其查詢延遲和吞吐量產(chǎn)生不利影響。 這通常發(fā)生在UPDATE重的工作負(fù)載中，其中大多數(shù)單獨(dú)的更新無(wú)法應(yīng)用HOT優(yōu)化（通常因?yàn)橹辽傩薷牧艘粋€(gè)索引列，需要一組新的索引元組版本 —一個(gè)新的元組對(duì)each and every索引）。 實(shí)際上，B-Tree重復(fù)數(shù)據(jù)刪除可以改善由版本變動(dòng)引起的索引膨脹。 請(qǐng)注意，即使唯一索引中的元組也不一定物理上唯一的，在版本變化而存儲(chǔ)在磁盤上時(shí)。 重復(fù)數(shù)據(jù)刪除優(yōu)化有選擇地應(yīng)用于唯一索引中。它針對(duì)那些看起來(lái)具有重復(fù)版本的頁(yè)面。 高級(jí)目標(biāo)是給VACUUM更多的時(shí)間，在版本改動(dòng)導(dǎo)致 “unnecessary”頁(yè)面拆分之前。

由于實(shí)現(xiàn)級(jí)別的限制，不能在所有情況下使用重復(fù)數(shù)據(jù)消除。 在CREATE INDEX 或 REINDEX時(shí)決定重復(fù)數(shù)據(jù)刪除安全性。

請(qǐng)注意，重復(fù)數(shù)據(jù)刪除被認(rèn)為是不安全的，不能用于下列涉及相同數(shù)據(jù)之間語(yǔ)義顯著差異的情況:

在未來(lái)版本的PostgreSQL中，還有一個(gè)實(shí)現(xiàn)級(jí)限制可能取消：

無(wú)論使用操作符類或排序規(guī)則如何，還有一個(gè)實(shí)現(xiàn)級(jí)別限制適用：