Gist

通用搜尋樹(Generalized Search Trees,GiST)是一種通用索引機制,能有效支持數據類型和查詢謂詞的可擴展,在資料庫中引入新的數據類型時能提供對新的數據類型索引的支持,利用這種結構可以很容易實現R樹、RD樹等。它是一種可擴展的樹型索引結構框架。

市場定位:電子郵件收件箱搜尋

公司總部和網址:華盛頓州西雅圖市,gist.com

Gist主要向用戶提供電子郵件相關內容的搜尋服務。該公司已獲得150萬美元風險投資,投資商為美國Vulcan Capital風險投資公司。Vulcan由微軟聯合創始人保羅·艾倫(Paul Allen)創建。

GIST

胃腸道間質瘤 Gastrointestinal Stromal Tumors

簡介

GiST(Generalized Search Tree),通用搜尋樹,由加州大學Berkeley分校開發,支持研究人員對新的數據類型開發實驗索引。現在GiST已經內嵌在PostgreSQL中。 通用搜尋樹是一棵平衡樹,除根結點的扇出數在2和M之間外,每個節點的扇出數在kM和M之間,這裡2/M<=k<=1/2。常量k稱作該樹的最小填充因子,M為一個結點可以容納索引項的最大數目。索引項形式為(p,ptr),其中p是用作搜尋碼的謂詞。在葉結點中,ptr為指向資料庫中某一元組的指針;而在非葉結點中,ptr為指向其子樹根結點的指針。謂詞中可以包含自由變數,只要相應子樹中葉結點標識的所有元組能實例化這些變數即可。 它是一種可擴展的樹型索引結構框架。這裡的“可擴展”包 含 2 層意思:一是支持數據類型的可擴展性;二是支持查詢
謂詞的可擴展性。

Gist的操作方法

Consistent(E,q):對於給定的索引項E=(p,ptr)和查詢謂詞q,判斷索引是否和查詢謂詞q匹配,若肯定不能匹配,則返回FALSE;否則返回true。

Union(P):對於給定的索引項組,返回謂詞r,使得索引項組中各個索引項子樹中所有的元組均滿足r。

Compress(E):對於給定的索引項(p,ptr),返回(a,ptr),a為p的壓縮形式。

Decompress(E):對於索引項(a,ptr),其中a=Compress(p),返回(r,ptr),使得p→r。

Penalty(E1,E2):對於索引項E1=(p1,ptr1)和E2=(p2,ptr2),當把E2插入到E1的子樹時,返回一個與索引數據域相關的測度值。

PickSplit(P):對於包含M+1個索引項(p,ptr)的集合P而言,將P劃分為兩個索引項的集合P1和P2,每個集合至少包含kM個索引項。

1.

Consistent(E,q):對於給定的索引項E=(p,ptr)和查詢謂詞q,判斷索引是否和查詢謂詞q匹配,若肯定不能匹配,則返回FALSE;否則返回true。

2.

Union(P):對於給定的索引項組,返回謂詞r,使得索引項組中各個索引項子樹中所有的元組均滿足r。

3.

Compress(E):對於給定的索引項(p,ptr),返回(a,ptr),a為p的壓縮形式。

4.

Decompress(E):對於索引項(a,ptr),其中a=Compress(p),返回(r,ptr),使得p→r。

5.

Penalty(E1,E2):對於索引項E1=(p1,ptr1)和E2=(p2,ptr2),當把E2插入到E1的子樹時,返回一個與索引數據域相關的測度值。

6.

PickSplit(P):對於包含M+1個索引項(p,ptr)的集合P而言,將P劃分為兩個索引項的集合P1和P2,每個集合至少包含kM個索引項。

相關詞條

相關搜尋

熱門詞條

聯絡我們