注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

生命无非记忆

不要在记忆中丢失了自己

 
 
 

日志

 
 

PostgreSQL GIN索引实现原理(1)  

2016-03-16 14:53:16|  分类: postgreSQL[原创] |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

1       概述

GIN(Generalized Inverted Index, 通用倒排索引)是一个存储对(key, posting list)集合的索引结构,其中key是一个键值,而posting list 是一组出现过key的位置。如(‘hello’, ’14:2 23:4’)中,表示hello14:223:4这两个位置出现过,在PG中这些位置实际上就是元组的tid

在表中的每一个属性,在建立索引时,都可能会被解析为多个键值,所以同一个元组的tid可能会出现在多个keyposting list中。

通过这种索引结构可以快速的查找到包含指定关键字的元组,因此GIN索引特别适用于支持全文搜索,而PGGIN索引模块也就是为了支持全文搜索而开发的。

2       GIN索引的扩展性

GIN索引具有很好的可扩展性,允许在开发自定义数据类型时由该数据类型的领域专家(而非数据库专家)设计适当的访问方法,这些访问方法只需考虑对于数据类型本身的语义处理,GIN索引自身可以处理并发控制、日志记录、搜索树结构等操作。

定义一个GIN访问方法所要做的就是实现5个用户定义的方法,这些方法定义了键值、键值与键值之间的关系、被索引值、能够使用索引的查询以及部分匹配。这些方法是:

1.       compare方法:比较两个键值ab,然后返回一个整数值,返回负值表示a < b,返回0表示a = b,返回正值表示a > b。其函数原型如下:

int compare(Datum a, Datum b)

                  

2.       extractValue方法:根据参数inputValue生成一个键值数组,并返回其指针,键值数组中元素的个数存放在另一个参数nkeys中。其函数原型如下:

Datum *extractValue(Datum inputValue, int32 *nkeys)

                  

3.       extractQuery方法:根据参数query生成一个用于查询的键值数组,并返回其指针。函数原型如下:

Datum *extractQuery(Datum query, int32 *nkeys, StrategyNumber n, bool **pmatch, Pointer **extra_data)

extractQuery通过参数n指定的操作符策略号来决定query的数据类型以及需要提取的键值,返回键值数组的长度存放在nkeys参数中。如果query中不包含键值,则nkeys可以为0或者-1nkeys = 0 表示索引中所有值都满足查询,将执行完全索引扫描(查询null时是这样); nkeys = -1 表示索引中没有键值满足查询,跳过索引扫描。

在部分匹配时,输出参数pmatch记录返回的键值数组中的每一个键值是否请求部分匹配。

输出参数extra_data用来向consistentcomparPartial方法传递用户自定义需要的数据。

4.       consistent方法:用于检查索引值是否满足查询,其函数原型如下:

bool consistent(bool check[], StrategyNumber n, Datum query, int32 nkeys,
Pointer extra_data[], bool *recheck)

如果索引值满足查询则返回true,如果recheck = true,则返回true的索引还需要进一步的检查。

recheck: 精确比较时recheck = false;否则recheck = true,通过索引找到的基表元组还需要进行是否满足操作符的检查(在TSVector类型时,如果key带有权值,则recheck = true)。

以查询 fat & (cat | dog)为例说consistent的执行:

PostgreSQL GIN索引实现原理(1) - zisedeqing - 生命无非记忆

 

5.       comparePartial方法:将部分匹配的查询与索引值进行比较,返回值为负值表示两者不匹配,但继续索引扫描;返回值为0表示两者匹配;返回值为正值表示停止扫描。其函数原型如下:

int comparePartial(Datum partial_key, Datum key, StrategyNumber n, Pointer
extra_data)

 

所以在PG中添加一种新的数据类型并且让GIN支持该数据类型,则需要完成以下步骤:

1.       添加数据类型

2.       为新数据类型实现并注册各种操作符所需要的函数,然后创建新类型的操作符

3.       CREATE OPERATOR CLASS为新的数据类型创建一个操作符类,该语句需要指定GIN索引所需要的5个支持函数

 

PGGIN索引,内部实现了对于TSVector数据类型的支持,并提供了把TEXT类型转换成TSVector的接口,所以可以说PGGIN索引支持TSVectorTEXT的数据类型。

3       GIN索引结构

3.1   逻辑结构

GIN索引在逻辑上可以看出一个relation,该relation有两种结构:

1.       只索引基表的一列

Key1

Posting list( or posting tree)

Key2

Posting list( or posting tree)

 

2.       索引基表的多列

Column1 num

Key1

Posting list( or posting tree)

Column2 num

Key2

Posting list( or posting tree)

Column3 num

Key3

Posting list( or posting tree)

这种结构,对于基表中不同列的相同的key,在GIN索引中也会当作不同的key来处理。

3.2   物理结构

GIN索引在物理存储上包含如下内容:

1.       EntryGIN索引中的一个元素,可以认为是一个词位,也可以理解为一个key

2.       Entry tree:在Entry上构建的B

3.       posting list:一个Entry出现的物理位置的链表

4.       posting tree:在一个Entry出现的物理位置链表上构建的B

5.       pending list:索引元组的临时存储链表,用于fastupdate模式的插入操作

 

从上面可以看出GIN索引主要由Entry treeposting treeor posting list)组成,其中Entry treeGIN索引的主结构树,posting tree是辅助树。

3.2.1  Entry tree

entry tree是一个B树,与Btree索引类似,用来组织和存储(key, posting list)对,其树结构如下:

PostgreSQL GIN索引实现原理(1) - zisedeqing - 生命无非记忆

 

从上图可以看出非叶子节点的每个元组都有一个指向孩子节点的指针,该指针由索引元组结构的tid来表示,中间节点和叶子节点还有一个右兄弟节点指针,指向其右兄弟节点,该指针记录在GinPageOpaqueDatarightlink内。

entry tree的非叶子节点与普通的btree树的非叶子节点类似,其叶子节点与普通btree的叶子节点不同,普通btree的叶子节点指向其索引的元组,而entry tree的叶子节点指向posting list,或者是posting tree。该指针用索引元组结构的tid表示,具体如何区分posting listposting tree将在页面结构中介绍。

从上图可以看出,如果posting list退化成单个itempointer,则GIN索引的结构就与B树索引完全一样。

3.2.2  posting tree

posting treeentry tree 类似,也是一个B树,其树结构与entry tree完全一样,不同之处就是posting tree页面存储的元组格式与entry tree不同,如下:

PostgreSQL GIN索引实现原理(1) - zisedeqing - 生命无非记忆

 

3.2.3  pending list

pending list是在fastupdate时,用来临时缓存GIN索引元组的,该链表把索引的插入操作推迟到一定条件时,批量处理。其结构是一个单向链表,如下:

PostgreSQL GIN索引实现原理(1) - zisedeqing - 生命无非记忆

 

从上图可以看出,pending listmeta页面用来指示pending list的头和尾的页面号,没有pending list的数据页面,存放的是新的索引元组。

  评论这张
 
阅读(325)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017