PostgreSQL 簡介

SP-GiST是空間劃分GiST（Space-partitioned GiST）的簡稱。SP-GiST支持劃分搜索樹，它們可用于開發(fā)許多各種不同的非平衡數(shù)據(jù)結(jié)構(gòu)，例如四叉樹、k-d樹和單詞查找樹。這些結(jié)構(gòu)的共同特征是它們反復(fù)地將搜索空間劃分成大小不需要相等的分區(qū)。匹配這些劃分規(guī)則的搜索將會很快。

這些常用的數(shù)據(jù)結(jié)構(gòu)最初是為在內(nèi)存中使用而設(shè)計(jì)的。在主存中，它們通常被設(shè)計(jì)為一組由指針鏈接的動態(tài)分配的結(jié)點(diǎn)。這對直接在磁盤上存儲并不合適，因?yàn)檫@些指針鏈可能很長并且需要太多次的磁盤訪問。相反，基于磁盤的數(shù)據(jù)結(jié)構(gòu)應(yīng)該具有高扇出來最小化 I/O。SP-GiST所提出的挑戰(zhàn)是將搜索樹結(jié)點(diǎn)映射到磁盤頁面，這樣即使是一次搜索會穿過很多結(jié)點(diǎn)，它也只需要訪問很少的幾個磁盤頁面。

和GiST一樣，SP-GiST也打算允許帶有合適訪問方法的自定義數(shù)據(jù)類型的開發(fā)，這種開發(fā)只需由該數(shù)據(jù)類型的領(lǐng)域?qū)＜覅⑴c，而不需要數(shù)據(jù)庫專家的參與。

這里的一些信息是來自于普渡大學(xué)的 SP-GiST 索引項(xiàng)目網(wǎng)站。PostgreSQL中的SP-GiST實(shí)現(xiàn)主要由 Teodor Sigaev 和 Oleg Bartunov 維護(hù)，在他們的 網(wǎng)站上有更多信息。