複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/Gist/3204796
複製
複製成功

Gist

（通用索引機制）

鎖定
通用搜索樹（Generalized Search Trees，GiST）是一種通用索引機制，能有效支持數據類型和查詢謂詞的可擴展，在數據庫中引入新的數據類型時能提供對新的數據類型索引的支持，利用這種結構可以很容易實現R樹、RD樹等。它是一種可擴展的樹型索引結構框架。
中文名
通用搜索樹
外文名
Generalized Search Trees
分    類
計算機圖像處理

目錄

  1. 1 市場定位：電子郵件收件箱搜索
  2. 2 簡介
  3. 3 Gist的操作方法

Gist市場定位：電子郵件收件箱搜索

公司總部和網址：華盛頓州西雅圖市，gist.com
Gist主要向用户提供電子郵件相關內容的搜索服務。該公司已獲得150萬美元風險投資，投資商為美國Vulcan Capital風險投資公司。Vulcan由微軟聯合創始人保羅·艾倫(Paul Allen)創建。
GIST
胃腸道間質瘤 Gastrointestinal Stromal Tumors

Gist簡介

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

GistGist的操作方法

  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個索引項。 [2] 
參考資料
  • 1.    圖像處理中gist算法是什麼  ．百度知道．2011-11-02[引用日期2013-03-18]
  • 2.    許向陽,劉少治,金光.iGiST一個改進的通用搜索樹 [J].武漢：華中科技大學學報，2002年11月