Gist

生活百科 2023-01-25 21:22生活百科www.aizhengw.cn

Gist

通用搜寻树(Generalized Search Trees,GiST)是一种通用索引机制,能有效支持数据类型和查询谓词的可扩展,在资料库中引入新的数据类型时能提供对新的数据类型索引的支持,利用这种结构可以很容易实现R树、RD树等。它是一种可扩展的树型索引结构框架。

基本介绍

  • 中文名通用搜寻树
  • 外文名Generalized Search Trees
  • 分类计算机图像处理

市场定位电子邮件收件箱搜寻

公司总部和网址华盛顿州西雅图市,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的操作方法

  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个索引项。
上一篇:Don Grady 下一篇:EVE姐妹共济会

Copyright@2015-2025 www.aizhengw.cn 癌症网版板所有