PostgreSQL 實現(xiàn)

單獨(dú)的葉子節(jié)點(diǎn)和內(nèi)部節(jié)點(diǎn)必須能適合一個單一的索引頁面（默認(rèn)為 8kB）。因此，當(dāng)索引值是一種變長數(shù)據(jù)類型時（長值只能由如 radix 樹的方法所支持），樹的每一層包含的前綴都足夠短以適合一個頁面，并且最終的葉子層包括的后綴也足夠短以適合一個頁面。如果操作符類準(zhǔn)備好做這種事情，它應(yīng)該將longValuesOK設(shè)置為true。否則，SP-GiST核心將拒絕任何要索引超過一個所以頁面長度的值的請求。

同樣，操作符類應(yīng)該負(fù)責(zé)不要讓內(nèi)部元組增長到無法放在一個索引頁面中。這限制了能在一個內(nèi)部元組中使用的子節(jié)點(diǎn)的數(shù)目，以及一個前綴值的最大尺寸。

另一個限制是，當(dāng)一個內(nèi)部元組的節(jié)點(diǎn)指向一組葉子元組時，這些元組必須都在同一個索引頁面中（這種設(shè)計是為了減少在這類元組構(gòu)成鏈中進(jìn)行定位的時間并且節(jié)省空間）。如果葉子元組集合增長到無法放在一個頁面中，將執(zhí)行一次分裂并且插入一個中間的內(nèi)部元組。為此，新的內(nèi)部元組必須把葉子值的集合劃分成多于一個節(jié)點(diǎn)分組。如果操作符類的picksplit函數(shù)無法做到這一點(diǎn)， SP-GiST核心只能求助于第 65.4.3 節(jié)中所介紹的額外措施。

某些樹算法對每個內(nèi)部元組都使用一種固定的節(jié)點(diǎn)集合。例如，在一個四叉樹中總是正好有四個節(jié)點(diǎn)對應(yīng)于圍繞內(nèi)部節(jié)點(diǎn)中心點(diǎn)的四個象限。在這種情況下，代碼總是通過編號來處理節(jié)點(diǎn)，而不需要顯式的節(jié)點(diǎn)標(biāo)簽。要抑制節(jié)點(diǎn)標(biāo)簽（因而節(jié)省一些空間），picksplit函數(shù)可以為nodeLabels數(shù)組返回NULL，同樣choose函數(shù)可以在一個 spgSplitTuple動作期間為prefixNodeLabels數(shù)組返回NULL。這將會導(dǎo)致后續(xù)對choose和inner_consistent調(diào)用時nodeLabels也為 NULL。原則上，可以為同一個索引中的某些內(nèi)部元組使用節(jié)點(diǎn)標(biāo)簽而對其他內(nèi)部節(jié)點(diǎn)省略節(jié)點(diǎn)標(biāo)簽。

在處理具有無標(biāo)簽節(jié)點(diǎn)的內(nèi)部元組時，讓choose返回spgAddNode是一種錯誤，因為該節(jié)點(diǎn)集合在這種情況下被假定為固定的集合。

當(dāng)picksplit無法把提供的葉子值劃分成至少兩個節(jié)點(diǎn)分類，SP-GiST核心能推翻操作符類的picksplit函數(shù)的結(jié)果。在發(fā)生這種情況時，會創(chuàng)建一個新的內(nèi)部元組，其中有多個節(jié)點(diǎn)，每一個節(jié)點(diǎn)都有相同的標(biāo)簽（如果有標(biāo)簽），標(biāo)簽是由picksplit之前給一個節(jié)點(diǎn)用的，并且葉子值會被隨機(jī)地劃分給這些等效的節(jié)點(diǎn)中。該內(nèi)部元組上會設(shè)置 allTheSame標(biāo)志以警告choose和inner_consistent函數(shù)該元組不具有它們所期望的節(jié)點(diǎn)集合。

在處理allTheSame元組時，choose函數(shù)的結(jié)果spgMatchNode會被解釋為新值可以被賦值給任一等價的節(jié)點(diǎn)。核心代碼將忽略提供的nodeN值并且隨機(jī)地下降到其中一個節(jié)點(diǎn)中（以便保持樹平衡）。對choose來說，返回 spgAddNode是一種錯誤，因為那會讓節(jié)點(diǎn)不全部等效。如果要被插入的值不匹配現(xiàn)有的節(jié)點(diǎn)，則必須使用spgSplitTuple動作。

在處理allTheSame元組時，為了繼續(xù)索引搜索，inner_consistent函數(shù)應(yīng)該返回全部節(jié)點(diǎn)或者不返回節(jié)點(diǎn)作為目標(biāo)，因為這些節(jié)點(diǎn)都是等效的。根據(jù)inner_consistent函數(shù)對這些節(jié)點(diǎn)含義的假定程度，這可能會也可能不會要求任何處理特殊情況的代碼。