衡水移动网站建设价格,wordpress 获取当前文章id,做二维码推送网站,网页制作相关网站GIN索引 倒排索引
PostgreSQL版本为8.4.1 #xff08;本文为《PostgreSQL数据库内核分析》一书的总结笔记#xff0c;需要电子版的可私信我#xff09; 索引篇#xff1a;
PostgreSQL索引篇 | BTreePostgreSQL索引篇 | GiST索引PostgreSQL索引篇 | Hash索引PostgreSQL索引…GIN索引 倒排索引
PostgreSQL版本为8.4.1 本文为《PostgreSQL数据库内核分析》一书的总结笔记需要电子版的可私信我 索引篇
PostgreSQL索引篇 | BTreePostgreSQL索引篇 | GiST索引PostgreSQL索引篇 | Hash索引PostgreSQL索引篇 | TSearch2 全文搜索
概述
GINGeneralized Inverted Index通用倒排索引是一个存储对key,posting list集合的索引结构
其中“key”是一个键值而“posting list”是一组出现过“key”的位置。
如 (“hello”“14:1723:1……”)中“hello”表示一个键值而“14:1723:1……”则表示“hello”这个键值出现的位置。
每一个位置又由“元组ID:位置”来表示位置“14:17”说明“hello”在第14号元组的被索引属性中第17个位置出现。每一个被索引的属性值都可能包含多个键值因此同一个元组的ID可能会出现在多个存储对的“posting list”中。通过这种索引结构可以快速地查找到包含指定关键字的元组因此GIN索引特别适合于支持全文搜索。
而开发GIN索引的主要目的就是为了让PostgreSQL能支持功能高度可扩展的全文搜索。
GIN索引具有很好的可扩展性允许在开发自定义数据类型时由该数据类型的领域专家而不是数据库专家设计适当的访问方法这些访问方法只需要考虑对于数据类型本身语义的处理而GIN索引自身可以处理并发操作、记录日志、搜索树结构等操作。
定义一个GIN访问方法所要做的就是实现五个用户定义的方法这些方法定义了键值、键值与键值之间的关系、被索引值、能够使用索引的查询及部分匹配。简而言之GIN结合了扩展性、普遍性、代码重用、清晰的接口等特点。
一个GIN索引需要实现的五个方法如下 compare方法比较两个键值a和b然后返回一个整数值返回负值表示a小于b返回0表示a等于b返回正值表示a大于b。 其原型如下 int compare (Datum a,Datum b) extractValue方法根据参数inputValue生成一个键值数组并返回其指针键值数组中元素的个数存放在另一个参数nkeys 中。 其原型如下 Datum* extractValue (Datum inputvalue,uint32 *nkeys) extractQuery方法根据一个查询由参数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指向的整个数组都将被传递给consistent方法而其中适当的元素将被传递给comparePartial方法。 其原型如下 Datum *extractQuery (Datum query, int32 * nkeys,strategyNumber n, bool * *pmatch,Pointer * *extra_data)consistent方法该方法用于检查索引值是否满足查询。 如果查询与索引满足策略号为n的操作符则返回真如果返回真且输出参数recheck也设置为真则说明查询和索引可能满足还需要进一步检查。check 数组的长度必须与先前由extractQuery为该查询返回的键值数量相同。 如果索引值包含相应的查询那么check 数组中的每一个元素都是真。也就是说如果check[i]为真那么extractQuery返回的键值数组的第i个键值存在于索引值当中。 如果GIN索引的比较是精确的recheck将被设置为假否则recheck将被设置为真通过索引找到的基表元组还需要进行是否满足操作符的检查。 图4-33为一个consistent方法实现的实例图中查询条件中的“”符号表示“与”而“|”符号则表示“或”。 其原型如下 bool consistent (bool check[],strategyNumber n,Datum query, int32 nkeys,Pointer extra_data[], bool * recheck)comparePartial方法将部分匹配的查询与索引值进行比较返回值为负值表示两者不匹配但继续扫描索引 返回值为0表示两者匹配返回值为正值表示停止扫描。 n是操作符的策略号 extra_data是由函数extractQuery传递过来的数组。 这个函数是在PostgreSQL 8.4.1中新增的函数。该方法的原型如下 int conparePartial (Datum partial_key,Datum key,strategyNumber n, Pointer extra_data)添加一种新的数据类型
如果要在 PostgreSQL中添加一种新的数据类型并且让GIN索引能够支持该数据类型则需要完成以下步骤 添加数据类型 ①实现新数据类型的输入输出函数并通过CREATE OR REPLACE FUNCTION语句将其注册到数据库内部这一步操作将会在pg.proc系统表中为每一个函数增加一个元组。②利用上一步注册的输入输出函数通过“CREATE TYPE”语句创建数据类型这一步会在pg_type系统表中为新数据类型增加一个元组并通过元组中的属性值与上一步创建的输入输出函数关联起来。③为新数据类型实现并注册各种操作符所需的函数然后通过“CREATE OPERATOR”语句为新数据类型创建操作符。 为新数据类型实现GIN索引所需要的5种支持函数compare、extractValue等 并通过CREATE OR REPLACE FUNCTION语句将这些函数注册到数据库内部。 用“CREATE OPERATOR CLASS”语句为新的数据类型创建一个操作符类该SQL语句需指定GIN索引所需要的5个支持函数。
完成上述步骤之后就可以用以下SQL语句在新数据类型上创建GIN索引了 CREATE INDEX index_name ON table_name (column_name) USING GIN;
GIN索引的组织结构
GIN索引包括以下四个部分
Entry是GIN索引中的一个元素可以认为是一个词位Entry也可以理解为GIN索引中的一个键值。Entry Tree在一些Entry上构建的B-Tree。Posting Tree在一个Entry出现的物理位置上构建的 B-Tree。Posting List一个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形式存储则在该索引元组键值之后的空间连续存放“Posting List”这样可快速获取到该键值所有的位置信息。由于是连续存储不需要访问其他节点因此索引元组的t_tid字段的ip_blkid部分用于存储“Posting List”的长度即该键值出现了多少次而ip_posid部分用于记录该索引元组的大小不包括“Posting List”的大小。若叶子节点中索引元组的位置信息采用Posting Tree形式存储空间换时间则该索引元组的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的变量来对整个创建过程的状态加以控制。 ginstate字段存放当前使用的GIN索引相关的5个支持函数信息这些信息是与要创建GIN索引的基表属性的数据类型相关的。 accum字段则指向索引创建过程中所使用的“蓄积池”其数据类型为BuildAccumulator。
BuildAccumulator类型 BuildAccumulator中的maxdepth和allocatedMemory两个字段反映了“蓄积池”中填充Entry的程度如果maxdepth超过GIN_MAX_TREE_DEPTH值为100或者allocatedMemory超过一个阈值(阈值为16384*1024)则创建过程会先将“蓄积池”中的Entry都插入到GIN索引中然后清空“蓄积池”。
EntryAccumulator类型 对于EntryAccumulator结构中的字段说明如下 attnum字段由于GIN支持多属性索引attnum记录了Entry出现在第几个被索引的属性中该字段从1开始递增。也就是说如果一个关键词出现在同一个元组的两个不同属性中则会为该关键词创建两个EntryAccumulator添加到树中。 length字段由于一个Entry出现的次数是无法预知的所以list字段所指向的数组长度是动态变化的当number频率大于等于length目前分配给list的长度时即将length翻倍同时list的长度也翻倍。 shouldSort字段若该Entry在多个地方出现依次将读取到的位置信息插入到list字段Posting List中由于后面插入的位置可能会使得list中的位置变成无序的就需要标记shouldSort字段为真在插入GIN索引时会根据这个字段的值来判断是否需要进行排序。 注在插入出现位置到“Posting List”时并不排序而是在构建整个GIN索引结构时根据该字段判断是否需要排序。
需注意 对于同一个Entry即使在多个元组的同一个属性中出现attnum相同也都是保存在同一个EntryAccumulator中其出现的不同位置保存在List结构中。 说明一个EntryAccumulator会有这个Entry在不同元组、同一个属性中出现的位置。 但是同一个Entry如果出现在不同的属性attnum不同中则要用不同的EntryAccumulator来表示。
EntryAccumulator通过其let和right字段指向其左右子节点EntryAccumulator构成的二叉树是有序的左子节点的Entry比父节点的Entry“小”父节点的Entry比右子节点的Entry“小”。这里的大小可通过compareAttEntries函数来进行比较。
PostgreSQL中提供了ginInsertRecordBA函数将来自于同一个元组的同一个属性的多个Entry插入到“蓄积池”。ginInsertRecordBA插入Entry所采用的策略如下
将Entry数组进行排序。首先将Entry数组中间元素插入到排序二叉树中然后采用同样的策略递归处理Entry数组的左半部分和右半部分。
例如要用ginInsertRecordBA函数插人以下的Entry数组这里没有列举Entry出现的位置只给出了关键词)
待插入的Entry数组已排序)ahstract, hinary, hash, hello, index, tree,world
实际ginInsertRecordBA执行的过程如下 插入数组中间元素hello左右部分分别作为左右孩子递归插入左右两个数组 ahstract, hinary, hash和index, tree,world 树中此时只有一个根节点hello 递归地对左数组取出中间元素左右部分分别作为左右孩子此时二叉树的结构为 递归处理右数组并插入到树中后二叉树的结构为
采用这种插入策略的好处是能够尽量保证插入记录后的二叉树趋于平衡不会使得其高度太大影响查找效率。
我总结下上面提到的Entry和EntryAccumulator的关系图后者数量多于前者 注蓝色部分表示查找条件为身高181或身高170时找到的所有EntryAccumulator。 Entry可能包含了来自不同元组、不同属性的key。 ginbuild函数
创建GIN索引函数是ginbuild函数其流程如下 调用initGinState初始化创建状态变量buildstateGinBuildState类型的ginstate字段该函数会根据当前要创建的索引的信息以及被索引属性的信息从系统表中抽取5个支持函数的信息用于填充ginstate字段的内容。 初始化GIN索引的元页并初始化buildstate的其他字段包括置indtuples为0、创建临时内存上下文和函数调用内存上下文。 调用ginInitBA初始化“蓄积池”即buildstate中的accum字段。 调用IndexBuildHeapScan对基表扫描并将ginBuildCallback函数的指针传递给IndexBuildHeapScan。每扫描到一个基表元组IndexBuildHeapScan都将其被索引属性的值解析出来然后传递给ginBuildCallback处理在ginBuildCallback中将进行以下处理 ①对于每一个被索引属性的值调用ginHeapTupleBulkInsert对其进行处理, 该函数会调用GIN索引的extractValue方法将被索引属性的值解析成若干个Entry一个属性值中可能包含多个关键词并将这些获得的Entry插入到“蓄积池”中ginInsertRecordBA函数该函数值将返回获得的Entry的个数这个数量将被累加到buildstate的indtuples字段中。 for (i 0; i buildstate-ginstate.origTupdesc-natts; i)if (!isnull[i])buildstate-indtuples ginHeapTupleBulkInsert(buildstate,(OffsetNumber) (i 1), values[i],htup-t_self);②对“蓄积池”的填充情况进行检查如果allocatedMemory或maxdepth字段的值超过阈值则循环调用ginGetEntry从“蓄积池”中取出一个Entry并将其用ginEntryInsert插入到GIN索引中。 ③当“蓄积池”中的Entry都已经被插入到GIN索引中后通过重置buildstate中的临时内存上下文来清空“蓄积池”然后调用ginInitBA重新初始化“蓄积池”。 /* If weve maxed out our available memory, dump everything to the index *//* Also dump if the tree seems to be getting too unbalanced */if (buildstate-accum.allocatedMemory maintenance_work_mem * 1024L ||buildstate-accum.maxdepth GIN_MAX_TREE_DEPTH){ItemPointerData *list;Datum entry;uint32 nlist;OffsetNumber attnum;while ((list ginGetEntry(buildstate-accum, attnum, entry, nlist)) ! NULL){/* there could be many entries, so be willing to abort here */CHECK_FOR_INTERRUPTS();ginEntryInsert(index, buildstate-ginstate, attnum, entry, list, nlist, TRUE);}MemoryContextReset(buildstate-tmpCtx);ginInitBA(buildstate-accum);}当IndexBuildHeapScan扫描完成后“蓄积池”中有可能还有一部分Entry没有被插入到GIN索引中 allocatedMemory和maxdepth字段的值都没有超过阈值同样循环调用ginGetEntry获取Entry再通过ginEntryInsert插入GIN索引中。 返回统计信息包括被索引的基表元组以及索引元组的数目。
Datum
ginbuild(PG_FUNCTION_ARGS)
{Relation heap (Relation) PG_GETARG_POINTER(0);Relation index (Relation) PG_GETARG_POINTER(1);IndexInfo *indexInfo (IndexInfo *) PG_GETARG_POINTER(2);IndexBuildResult *result;double reltuples;GinBuildState buildstate;Buffer RootBuffer,MetaBuffer;ItemPointerData *list;Datum entry;uint32 nlist;MemoryContext oldCtx;OffsetNumber attnum;if (RelationGetNumberOfBlocks(index) ! 0)elog(ERROR, index \%s\ already contains data,RelationGetRelationName(index));// 初始化创建状态变量buildstate的ginstate字段,填充5个函数initGinState(buildstate.ginstate, index);/* initialize the meta page */MetaBuffer GinNewBuffer(index);/* initialize the root page */RootBuffer GinNewBuffer(index);START_CRIT_SECTION();// 初始化GIN索引的元页GinInitMetabuffer(MetaBuffer);MarkBufferDirty(MetaBuffer);GinInitBuffer(RootBuffer, GIN_LEAF);MarkBufferDirty(RootBuffer);if (!index-rd_istemp){XLogRecPtr recptr;XLogRecData rdata;Page page;rdata.buffer InvalidBuffer;rdata.data (char *) (index-rd_node);rdata.len sizeof(RelFileNode);rdata.next NULL;recptr XLogInsert(RM_GIN_ID, XLOG_GIN_CREATE_INDEX, rdata);page BufferGetPage(RootBuffer);PageSetLSN(page, recptr);PageSetTLI(page, ThisTimeLineID);page BufferGetPage(MetaBuffer);PageSetLSN(page, recptr);PageSetTLI(page, ThisTimeLineID);}UnlockReleaseBuffer(MetaBuffer);UnlockReleaseBuffer(RootBuffer);END_CRIT_SECTION();/* build the index 初始化buildstate的其他字段包括置indtuples为0*/buildstate.indtuples 0;/* 创建 临时内存上下文 和 函数调用内存上下文* create a temporary memory context that is reset once for each tuple* inserted into the index*/buildstate.tmpCtx AllocSetContextCreate(CurrentMemoryContext,Gin build temporary context,ALLOCSET_DEFAULT_MINSIZE,ALLOCSET_DEFAULT_INITSIZE,ALLOCSET_DEFAULT_MAXSIZE);buildstate.funcCtx AllocSetContextCreate(buildstate.tmpCtx,Gin build temporary context for user-defined function,ALLOCSET_DEFAULT_MINSIZE,ALLOCSET_DEFAULT_INITSIZE,ALLOCSET_DEFAULT_MAXSIZE);// buildstate.accum.ginstate buildstate.ginstate;// 初始化“蓄积池”ginInitBA(buildstate.accum);/* 扫描基表* 每扫描到一个基表元组都将其被索引属性的值解析出来然后传递给ginBuildCallback处理* Do the heap scan. We disallow sync scan here because dataPlaceToPage* prefers to receive tuples in TID order.*/reltuples IndexBuildHeapScan(heap, index, indexInfo, false,ginBuildCallback, (void *) buildstate);/* dump remaining entries to the index 当IndexBuildHeapScan扫描完成后“蓄积池”中有可能还有一部分Entry没有被插入到GIN索引中allocatedMemory和maxdepth字段的值都没有超过阈值同样循环调用ginGetEntry获取Entry再通过**ginEntryInsert**插入GIN索引中。*/oldCtx MemoryContextSwitchTo(buildstate.tmpCtx);while ((list ginGetEntry(buildstate.accum, attnum, entry, nlist)) ! NULL){/* there could be many entries, so be willing to abort here */CHECK_FOR_INTERRUPTS();ginEntryInsert(index, buildstate.ginstate, attnum, entry, list, nlist, TRUE);}MemoryContextSwitchTo(oldCtx);MemoryContextDelete(buildstate.tmpCtx);/* 返回统计信息包括被索引的基表元组以及索引元组的数目* Return statistics*/result (IndexBuildResult *) palloc(sizeof(IndexBuildResult));result-heap_tuples reltuples;result-index_tuples buildstate.indtuples;PG_RETURN_POINTER(result);
}ginEntryInsert函数
将Entry及其位置信息插入到GIN索引结构中是通过调用ginEntryInsert函数来完成的该函数的流程如图4-35所示。 在ginEntryInsert中待插入的Entry用一个数据结构GinBtreeData来管理其定义如下所示
typedef struct GinBtreeData
{/* search methods 查找schema使用的函数指针*/BlockNumber (*findChildPage) (GinBtree, GinBtreeStack *);bool (*isMoveRight) (GinBtree, Page);bool (*findItem) (GinBtree, GinBtreeStack *);/* insert methods 插入schema使用的函数指针*/OffsetNumber (*findChildPtr) (GinBtree, Page, BlockNumber, OffsetNumber);BlockNumber (*getLeftMostPage) (GinBtree, Page);bool (*isEnoughSpace) (GinBtree, Buffer, OffsetNumber);void (*placeToPage) (GinBtree, Buffer, OffsetNumber, XLogRecData **);Page (*splitPage) (GinBtree, Buffer, Buffer,OffsetNumber,XLogRecData **);void (*fillRoot) (GinBtree, Buffer, Buffer, Buffer);bool searchMode; //是否为查找模式Relation index; //索引表GinState *ginstate; //用于记录GIN索引提供的5种扩展方法bool fullScan; //是否为完全扫描bool isBuild; //该Entry对应的位置信息上是否创建了B-TreeBlockNumber rightblkno; //该Entry所在页面的下一个(右)页面/* Entry options */OffsetNumber entryAttnum; //Entry在索引元组中对应属性编号Datum entryValue; //Entry的键值IndexTuple entry; //Entry对应的索引元组bool isDelete; //Entry是否被删除/* Data (posting tree) option 以下是与位置信息相关字段*/ItemPointerData *items; //Entry的位置数组 “Posting List”uint32 nitem; //位置数组的长度 根据nitem来判断是否需要构建“Posting Tree”。uint32 curitem; //当前使用的“位置”PostingItem pitem; //保存叶子节点页面的页面号以及一个物理地址
} GinBtreeData;注意GinBtreeData数据结构不仅在GIN索引的创建过程中会使用在使用GIN索引进行查询、插入时都会使用到。
其中的items字段在创建索引时用于保存该Entry所有的位置信息即保存“Posting List”然后根据位置数组的长度来判断是否需要构建“Posting Tree”。
可以看到GinBtreeData数据结构中定义了9个函数指针这些函数指针指向的函数实现了对GIN索引结构的查找、插入、分裂等操作对于每一个函数指针既可以定义对Entry节点操作的函数也可以指向对位置信息进行操作的函数。
每一个函数的功能说明如下
findChildPage在GinBtreeStack类型参数的buffer字段对应的非叶子层页面中找到Entry由GinBtreeData类型参数表示对应的索引元组由于是非叶子层页面索引元组中的指针指向下一层的孩子页面并返回索引元组指向的孩子页面的块号。isMoveRight比较Page类型参数对应的页面中最后一个索引元组与GinBtree对应的Entry的值大小如果小于则返回真表示该页面应该右移否则返回假。finditem在GinBtreeStack类型参数的buffer字段对应的叶子层页面中查找Entry (由GinBtreeData类型参数表示对应的索引元组若存在将索引元组在页面中的偏移量赋给GinBtreeStack类型参数的off字段并返回真否则返回假。findChildPtr在Page类型参数对应的页面中查找孩子页面号为BlockNumber的索引元组的页面内偏移量并返回。getLeftMostPage返回非叶子层页面中第一个索引元组指向的页面号。isEnoughSpace判断Buffer类型参数指向的缓冲区中是否有足够空间存储GinBtree对应的索引元组如果有足够空间则返回真否则返回假。placeToPage将GinBtree中的索引元组写到缓冲区中OffsetNumber类型参数为写入缓冲区的起始偏移量并写日志。splitPage将GinBtree中的索引元组插入到第一个参数指定的缓冲区中并将该缓冲区分裂成两个大小几乎相当的缓冲区分裂产生的新缓冲区放在第二个参数中返回第一个缓冲区的页面号最后写日志。fillRoot将第三、四个参数指定的两个缓冲区最右端的索引元组填充到第二个参数指定的缓冲区中并将被填充索引元组的指针分别指向第三、四个参数对应的页面号。
可以看出这些函数中很多都使用了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表示没有限制。如果设置了非零值那么返回的结果就是从完整结果集中随机选择的一部分。
