数据库倒排索引



PostgreSQL版本为8.4.1
（本文为《PostgreSQL数据库内核分析》一书的总结笔记，需要电子版的可私信我）
索引篇：

• PostgreSQL索引篇 | BTree
• PostgreSQL索引篇 | GiST索引
• PostgreSQL索引篇 | Hash索引
• PostgreSQL索引篇 | TSearch2 全文搜索

GIN（Generalized Inverted Index，通用倒排索引）是一个存储对（key,posting list）集合的索引结构

其中“key”是一个键值，而“posting list”是一组出现过“key”的位置。

如 (“hello”，“14:17，23:1，……”)中，“hello”表示一个键值，而“14:17，23:1，……”则表示“hello”这个键值出现的位置。

每一个位置又由“元组ID:位置”来表示，位置“14:17”说明“hello”在第14号元组的被索引属性中第17个位置出现。每一个被索引的属性值都可能包含多个键值，因此同一个元组的ID可能会出现在多个存储对的“posting list”中。通过这种索引结构可以快速地查找到包含指定关键字的元组，因此GIN索引特别适合于支持全文搜索。

而开发GIN索引的主要目的就是为了让PostgreSQL能支持功能高度可扩展的全文搜索。

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

定义一个GIN访问方法所要做的就是实现五个用户定义的方法，这些方法定义了键值、键值与键值之间的关系、被索引值、能够使用索引的查询及部分匹配。简而言之，GIN结合了扩展性、普遍性、代码重用、清晰的接口等特点。

一个GIN索引需要实现的五个方法如下：

• 方法：比较两个键值a和b，然后返回一个整数值，返回负值表示a小于b，返回0表示a等于b，返回正值表示a大于b。

  其原型如下：

• 方法：根据参数inputValue生成一个键值数组，并返回其指针，键值数组中元素的个数存放在另一个参数nkeys 中。

  其原型如下：

• 方法：根据一个查询（由参数query 给定）生成一个用于查询的键值数组，并返回其指针。
  • extractQuery通过参数n指定的操作符策略号来决定query的数据类型以及需要提取的键值，返回键值数组的长度存放在nkeys参数中。如果query中不包含键值，则extractQuery将根据操作符的语义在nkeys中存储0或-1。
  • nkeys值为0表示索引中所有值都能满足query，因此将执行完全索引扫描，例如当query为空字符串时就会发生此种情况。当nkeys值为-1时表明索引中没有键值能匹配查询，因此可以跳过索引扫描。
  • 当索引支持部分匹配时，输出参数pmatch用于记录返回的键值数组中每一个键值是否要求部分匹配。extractQuery将分配一个长度为nkeys 的布尔型数组，将这个数组的指针通过pmatch输出，数组中的每一个元素都记录了键值数组中对应位置键值的部分匹配情况，如果为真就表示该键值要求部分匹配。
  • 输出参数extra_data用来向consistent和comparePartial方法传递用户定义需要的数据，extra_data指向一个长度为nkeys 的指针数组，extractQuery可以在每一个数组元组所指向的内存空间存放任何数据。如果extra_data被设为非空，则extra_data指向的整个数组都将被传递给方法，而其中适当的元素将被传递给comparePartial方法。

  其原型如下：

• 方法：该方法用于检查索引值是否满足查询。
  • 如果查询与索引满足策略号为n的操作符则返回真，如果返回真且输出参数recheck也设置为真则说明查询和索引可能满足，还需要进一步检查。check 数组的长度必须与先前由extractQuery为该查询返回的键值数量相同。
  • 如果索引值包含相应的查询，那么check 数组中的每一个元素都是真。也就是说，如果check[i]为真，那么extractQuery返回的键值数组的第i个键值存在于索引值当中。
  • 如果GIN索引的比较是精确的，recheck将被设置为假，否则recheck将被设置为真，通过索引找到的基表元组还需要进行是否满足操作符的检查。

  图4-33为一个consistent方法实现的实例，图中查询条件中的“&”符号表示“与”，而“|”符号则表示“或”。

  其原型如下：

  

• 方法：将部分匹配的查询与索引值进行比较，返回值为负值表示两者不匹配，但继续扫描索引；

  返回值为0表示两者匹配；返回值为正值表示停止扫描。

  n是操作符的策略号；

  extra_data是由函数extractQuery传递过来的数组。

  这个函数是在PostgreSQL 8.4.1中新增的函数。该方法的原型如下：

如果要在 PostgreSQL中添加一种新的数据类型并且让GIN索引能够支持该数据类型，则需要完成以下步骤：

• 添加数据类型：
  • ①实现新数据类型的输入输出函数，并通过语句将其注册到数据库内部，这一步操作将会在pg.proc系统表中为每一个函数增加一个元组。
  • ②利用上一步注册的输入输出函数，通过“CREATE TYPE”语句创建数据类型，这一步会在pg_type系统表中为新数据类型增加一个元组，并通过元组中的属性值与上一步创建的输入输出函数关联起来。
  • ③为新数据类型实现并注册各种操作符所需的函数，然后通过“CREATE OPERATOR”语句为新数据类型创建操作符。
• 为新数据类型实现GIN索引所需要的5种支持函数（compare、extractValue等），

  并通过语句将这些函数注册到数据库内部。

• 用“CREATE OPERATOR CLASS”语句为新的数据类型创建一个操作符类，该SQL语句需指定GIN索引所需要的5个支持函数。

GIN索引包括以下四个部分：

• ：是GIN索引中的一个元素（可以认为是一个词位），Entry也可以理解为GIN索引中的一个键值。
• ：在一些Entry上构建的B-Tree。
• ：在一个Entry出现的物理位置上构建的 B-Tree。
• ：一个Entry出现的物理位置的列表。

GIN索引包含一个构建在Entry（键值）上的B-Tree索引 （Entry Tree)，“Entry Tree”的内部节点与普通B–Tree索引的内部节点一样，不同的是叶子节点中索引项的指针指向不同，普通B-Tree的叶子节点中索引项指针指向基表元组的物理存储位置，而GIN索引的叶子节点中索引项的指针指向位置分两种情况：

• 如果该叶子节点中索引项内包含的键值（Entry）所出现的物理位置大于宏TOAST_INDEX_TARCET所指定的值，则在这些物理位置上构建“Posting Tree”，然后将索引项指针指向“Posting Tree”的根节点。
• 否则，叶子节点中索引项指针直接指向“Posting List”。

也就是说，如果某个Entry出现的位置较多（超过了TOAST_INDEX_TARCET的值)，则在其出现的位置（也就是“Posting List”)上再创建一个B-Tree结构，以加快查找的速度。

一个GIN索引的组织结构示例如图4-34所示：

在实现上，“Entry Tree”的非叶子节点部分和B–Tree索引类似，都是以一个页面来组织索引元组。

但“Entry Tree”叶子节点和普通的B-Tree索引页面结构有些区别：

• 若叶子节点中索引元组（IndexTuple，见数据结构4.3）的位置信息采用形式存储，则在该索引元组键值之后的空间连续存放“Posting List”，这样可快速获取到该键值所有的位置信息。由于是连续存储（不需要访问其他节点），因此索引元组的t_tid字段的ip_blkid部分用于存储“Posting List”的长度（即该键值出现了多少次），而ip_posid部分用于记录该索引元组的大小（不包括“Posting List”的大小）。
• 若叶子节点中索引元组的位置信息采用形式存储（空间换时间），则该索引元组的t_tid字段的ip_blkid部分记录了“Posting Tree”根节点所在的磁盘块号，而t_tid字段的ip_posid部分则设置为GIN_TREE_POSTING，用于与“Posting List”区分开来。

通过这种方式，巧妙地使用索引元组中的t_tid字段，使得对“Posting List”和“Posting Tree”的操作得到统一，根据t_tid字段中的ip_posid部分的取值可以区分“Posting List”和“Posting Tree”，然后根据两种不同的类型调用不同的方法来读取位置信息。PostgreSQL提供了一系列的宏定义用于支持这些操作。

GIN索引中共设置了5种页面类型，如表4-8所示。

元页

其中，GIN索引的元页主要用来管理索引创建过程中待索引的页面信息，其定义如数据结构4.14所示。

Pending List

在创建GIN索引时，首先会将所有所有待索引的Entry及其位置信息统计出来，并将这些信息存储在GIN_LIST页面中，GIN_LIST页面将构成一个双向链表（也称为“Pending List”)，在元页中通过head、tail两个字段分别指向这个链表的头部和尾部。

在存储Entry及其位置信息时，先申请一个GIN_LIST页面，将其填满之后链接在“Pending List”尾部，然后再申请下一个GIN_LIST页面进行填充。因此在“Pending List”中，只有尾部的页面可能是不满的，其他页面都是被填充满的，在元页中用tailFreeSize字段记录最尾部页面的剩余空间大小。在创建GIN索引结构时，会依次读取出“Pending List”中页面里的信息，并插入到索引结构中。

在PostgreSQL8.4.1中，GIN索引可以支持tsvector和所有内置数据类型的一维数组。

另外，在源代码的contrib目录（含很多扩展模块）下还有btree-gin、hstore、intarray和pg_trgm四个子目录，每一个子目录中的代码都可以用来在数据库系统中增加一种新的数据类型并让GIN索引能支持它，其基本实现过程和上面（GIN添加一种新的数据类型）所介绍的一致。

索引的创建

GIN索引的创建过程就是从基表中依次取出基表元组，然后从基表元组构建出若干个Entry及其“Posting List”，然后将这些Entry插入到GIN索引结构中。

在实现中，GIN索引的创建函数并不是构建出一个Entry就立即将其插入到GIN索引中，而是建立了一个“蓄积池”，构建出的Entry都将先放入“蓄积池”，当“蓄积池”填充到一定程度之后才会将其中缓存的Entry依次插入到GIN索引中去。

GinBuildState类型

GIN索引的创建函数使用了一个GinBuildState类型（数据结构4.15）的变量来对整个创建过程的状态加以控制。

• 字段存放当前使用的GIN索引相关的5个支持函数信息，这些信息是与要创建GIN索引的基表属性的数据类型相关的。
• 字段则指向索引创建过程中所使用的“蓄积池”，其数据类型为BuildAccumulator。

BuildAccumulator类型

BuildAccumulator中的和两个字段反映了“蓄积池”中填充Entry的程度，如果maxdepth超过GIN_MAX_TREE_DEPTH（值为100）或者allocatedMemory超过一个阈值(阈值为16384*1024)，则创建过程会先将“蓄积池”中的Entry都插入到GIN索引中，然后清空“蓄积池”。

EntryAccumulator类型

对于EntryAccumulator结构中的字段说明如下：

• 字段：由于GIN支持多属性索引，attnum记录了Entry出现在第几个被索引的属性中，该字段从1开始递增。也就是说，如果一个关键词出现在同一个元组的两个不同属性中，则会为该关键词创建两个EntryAccumulator添加到树中。
• 字段：由于一个Entry出现的次数是无法预知的，所以list字段所指向的数组长度是动态变化的，当number（频率）大于等于length（目前分配给list的长度）时，即将length翻倍，同时list的长度也翻倍。
• 字段：若该Entry在多个地方出现，依次将读取到的位置信息插入到list字段（Posting List）中，由于后面插入的位置可能会使得list中的位置变成无序的，就需要标记shouldSort字段为真，在插入GIN索引时会根据这个字段的值来判断是否需要进行排序。

  注：在插入出现位置到“Posting List”时并不排序，而是在构建整个GIN索引结构时，根据该字段判断是否需要排序。

需注意：

• 对于同一个Entry，即使在多个元组的同一个属性中出现（相同），也都是保存在同一个EntryAccumulator中，其出现的不同位置保存在结构中。

  说明一个EntryAccumulator会有这个Entry在不同元组、同一个属性中出现的位置。

• 但是同一个Entry如果出现在不同的属性（不同）中，则要用不同的EntryAccumulator来表示。

EntryAccumulator通过其let和right字段指向其左右子节点，EntryAccumulator构成的二叉树是有序的，左子节点的Entry比父节点的Entry“小”，父节点的Entry比右子节点的Entry“小”。这里的大小可通过compareAttEntries函数来进行比较。

PostgreSQL中提供了ginInsertRecordBA函数将来自于同一个元组的同一个属性的多个Entry插入到“蓄积池”。ginInsertRecordBA插入Entry所采用的策略如下：

1. 将Entry数组进行排序。
2. 首先将Entry数组中间元素插入到排序二叉树中，然后采用同样的策略递归处理Entry数组的左半部分和右半部分。

例如，要用ginInsertRecordBA函数插人以下的Entry数组（这里没有列举Entry出现的位置，只给出了关键词)：

待插入的Entry数组（已排序)：ahstract, hinary, hash, hello, index, tree,world`

实际ginInsertRecordBA执行的过程如下：

1. 插入数组中间元素hello，左右部分分别作为左右孩子，递归插入左右两个数组：

   和

   树中此时只有一个根节点：

2. 递归地对左数组取出中间元素，左右部分分别作为左右孩子，此时二叉树的结构为：

   

3. 递归处理右数组并插入到树中后，二叉树的结构为：

   

采用这种插入策略的好处是能够尽量保证插入记录后的二叉树趋于平衡，不会使得其高度太大影响查找效率。

我总结下上面提到的Entry和EntryAccumulator的关系图：（后者数量多于前者）
注：蓝色部分表示查找条件为：身高=181或身高=170时找到的所有EntryAccumulator。
Entry可能包含了来自不同元组、不同属性的key。

ginbuild函数

创建GIN索引函数是ginbuild函数，其流程如下：

1. 调用initGinState初始化创建状态变量buildstate（GinBuildState类型）的字段，该函数会根据当前要创建的索引的信息以及被索引属性的信息从系统表中抽取5个支持函数的信息用于填充ginstate字段的内容。
2. 初始化GIN索引的元页，并初始化buildstate的其他字段，包括置为0、创建临时内存上下文和函数调用内存上下文。
3. 调用ginInitBA初始化“蓄积池”（即buildstate中的字段）。
4. 调用IndexBuildHeapScan对基表扫描，并将ginBuildCallback函数的指针传递给IndexBuildHeapScan。每扫描到一个基表元组，IndexBuildHeapScan都将其被索引属性的值解析出来然后传递给ginBuildCallback处理，在ginBuildCallback中将进行以下处理：
   • ①对于每一个被索引属性的值，调用ginHeapTupleBulkInsert对其进行处理,
     该函数会调用GIN索引的extractValue方法将被索引属性的值解析成若干个Entry（一个属性值中可能包含多个关键词），并将这些获得的Entry插入到“蓄积池”中（ginInsertRecordBA函数），该函数值将返回获得的Entry的个数，这个数量将被累加到buildstate的indtuples字段中。

   • ②对“蓄积池”的填充情况进行检查，如果或字段的值超过阈值则循环调用ginGetEntry从“蓄积池”中取出一个Entry，并将其用ginEntryInsert插入到GIN索引中。
   • ③当“蓄积池”中的Entry都已经被插入到GIN索引中后，通过重置buildstate中的临时内存上下文来清空“蓄积池”，然后调用ginInitBA重新初始化“蓄积池”。

5. 当IndexBuildHeapScan扫描完成后，“蓄积池”中有可能还有一部分Entry没有被插入到GIN索引中（ 和字段的值都没有超过阈值），同样循环调用ginGetEntry获取Entry再通过ginEntryInsert插入GIN索引中。
6. 返回统计信息，包括被索引的基表元组以及索引元组的数目。

ginEntryInsert函数

将Entry及其位置信息插入到GIN索引结构中，是通过调用ginEntryInsert函数来完成的，该函数的流程如图4-35所示。

在ginEntryInsert中，待插入的Entry用一个数据结构GinBtreeData来管理，其定义如下所示：

注意，GinBtreeData数据结构不仅在GIN索引的创建过程中会使用，在使用GIN索引进行查询、插入时都会使用到。

其中的字段在创建索引时用于保存该Entry所有的位置信息，即保存“Posting List”，然后根据位置数组的长度来判断是否需要构建“Posting Tree”。

可以看到，GinBtreeData数据结构中定义了9个函数指针，这些函数指针指向的函数实现了对GIN索引结构的查找、插入、分裂等操作，对于每一个函数指针，既可以定义对Entry节点操作的函数，也可以指向对位置信息进行操作的函数。

每一个函数的功能说明如下：

1. ：在GinBtreeStack类型参数的字段对应的非叶子层页面中找到Entry（由GinBtreeData类型参数表示）对应的索引元组（由于是非叶子层页面，索引元组中的指针指向下一层的孩子页面），并返回索引元组指向的孩子页面的块号。
2. ：比较Page类型参数对应的页面中最后一个索引元组与GinBtree对应的Entry的值大小，如果小于则返回真（表示该页面应该右移），否则返回假。
3. ：在GinBtreeStack类型参数的buffer字段对应的叶子层页面中查找Entry (由GinBtreeData类型参数表示）对应的索引元组，若存在，将索引元组在页面中的偏移量赋给GinBtreeStack类型参数的off字段并返回真，否则返回假。
4. ：在Page类型参数对应的页面中查找孩子页面号为BlockNumber的索引元组的页面内偏移量并返回。
5. ：返回非叶子层页面中第一个索引元组指向的页面号。
6. ：判断Buffer类型参数指向的缓冲区中是否有足够空间存储GinBtree对应的索引元组，如果有足够空间则返回真，否则返回假。
7. ：将GinBtree中的索引元组写到缓冲区中，OffsetNumber类型参数为写入缓冲区的起始偏移量，并写日志。
8. ：将GinBtree中的索引元组插入到第一个参数指定的缓冲区中，并将该缓冲区分裂成两个大小几乎相当的缓冲区，分裂产生的新缓冲区放在第二个参数中，返回第一个缓冲区的页面号，最后写日志。
9. ：将第三、四个参数指定的两个缓冲区最右端的索引元组填充到第二个参数指定的缓冲区中，并将被填充索引元组的指针分别指向第三、四个参数对应的页面号。

可以看出，这些函数中很多都使用了GinBtreeStack数据结构，该结构用于记录索引结构在一次查找过程中从根节点到叶子节点的路径，当插入一个Entry引起节点分裂后，需要使用该结构向上回溯调整。

GinBtreeStack结构的定义见数据结构4.19。

对于GIN索引的插入，若一次插入了很多元组，则会调用ginHeapTupleFastInsert函数进行批量插入，该函数的执行流程与索引创建流程类似，这里就不再赘述。

在大多数情况下，若更新的数据量很大，GIN索引的“Posting List”结构可能较长，向GIN索引插入的速度较慢。因此，对于向表中大量插入的操作，建议先删除GIN索引，在完成插入之后再重建它。

索引查询

GIN索引的查询通过关键词与Entry的匹配操作来查找其所在的元组。在查找的过程中按照B-Tree结构进行搜索，调用consistent方法来判断是否找到。GIN索引没有提供返回单个元组的函数（类似B-Tree索引的btgettuple函数），只提供了位图查询的方式，也就是说，对GIN索引的查询只能得到一个位图，其中包含了符合查询条件的元组的物理位置。

开发GIN索引的目的是让PostgreSQL支持高度可扩展的全文索引。我们常常会遇到全文索引返回海量结果的情形，在查询高频词时得到的很大的结果集其实并没有什么用，因为从磁盘读取大量记录并对其进行排序会消耗大量资源。

为了易于控制这种情况，GIN索引有一个结果集大小 “软上限” 的配置参数gin_fuzzy_search_limit，其缺省值为0，表示没有限制。如果设置了非零值，那么返回的结果就是从完整结果集中随机选择的一部分。

版权声明：

本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。

本文网址：https://www.mushiming.com/mjsbk/8800.html