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

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

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

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

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

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

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

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

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