赞
踩
PostgreSQL版本为8.4.1
(本文为《PostgreSQL数据库内核分析》一书的总结笔记,需要电子版的可私信我)
索引篇:
GiST(Generalized Search Tree,通用搜索树)是一种平衡的、树状结构的访问方法。
它在系统中相当于一个基础的模板,几乎可以使用它实现任意索引模式。B-trees、R-trees 和许多其他的索引模式都可以用GiST实现。它可以建立一种可扩展的索引结构,包括数据类型和查询谓词的扩展。
GiST 允许用户(并非数据库专家)开发自己的数据类型,并通过相应的访问方法来在该数据类型上使用GiST索引。通常,实现一种新的索引访问方法意味着大量艰苦的工作。因为必须理解数据库的内部工作机制,比如锁的机制和预写式日志。GiST 接口提供了一个高层的抽象,只要求访问方法的实现者实现被访问数据类型的语义。GiST层本身会处理并发、日志和搜索树结构的任务。
GiST的代码分布在\src\backend\access\gist目录下,包括了GiST索引的创建、查找、删除等代码。
GiST是一棵平衡树,除根节点的子树数目在2 ~ M之间外,每个节点的子树数目在k*M ~ M之间,常量k称作该树的最小填充因子,满足2/M≤k≤1/2,M为一个节点可以容纳索引项的最大数目。
索引项形式为(p,ptr),其中p是搜索的谓词。在叶子节点中,ptr为指向数据库中某一元组的指针;而在非叶子节点中,ptr为指向其子树节点的指针。
在图4-27中,SP1、SP2 ( subtree predicates)是指用于分隔数据的谓词。可以看出,GiST 的结构和B-Tree 索引的结构有一定的相似性。
GiST内置实现了索引项查询、插入和删除等算法。
用户通过定义索引项并提供与索引项管理有关的方法,便可以实现某一特定的索引结构。
这些方法包括:
Consistent(E,q)
:对于给定的索引项E (p,ptr)和查询谓词q,判断索引项E是否与查询谓词q匹配,若肯定不能匹配,则返回假;否则,返回真。
Union(P)
:对于给定集合Р中索引项(p1,ptr1),…,(pn,ptrn),返回谓词r,满足(p1V…Vpn)→r,r代表了ptr1 到ptrn所指向的所有记录。
Same(E1,E2)
:如果两个条目相同,返回真,否则返回假。
Penalty(E1,E2)
:给定两个索引项E1 (p1,ptr1)和E2(p2,ptr2),返回值为将E2插入到以E1为根的子树中时的惩罚值(表示插入的代价)。
这用来辅助Split和Insert 算法,有利于将一个记录对应的索引项插入到最适合的位置(该插入引起的惩罚值最小)。
PickSplit(P)
:对于包含M+1个索引项(p,ptr)的集合Р而言,将Р划分为两个集合P1和P2,每个集合至少包含k*M个索引项。该方法确定了节点分裂的原则。
Compress(E)
:对于给定的索引项(p,ptr),返回(π,ptr),π为p的压缩形式。Decompress(E)
:对于给定的压缩表示索引项(π,ptr),π = Compress( p ),返回(r,ptr),r满足p→r。(可能为有损压缩,并不要求p←→r)。由于GiST 已内置实现了索引项的创建、查找和删除等操作,而这些操作都依赖于4.4.2节中介绍的7个方法,因此用户只需要实现这7种方法。而索引的创建、查找等PostgreSQL自动会进行扩展。下面将对数据库如何使用这7种方法来实现对数据库的操作进行分析。
Postgres 中 GiST索引的创建由函数gistbuild完成,实现流程如图4-28所示。
在索引创建过程中,索引元组的插入在函数gistdoinsert中完成,该函数将一个索引元组插入到索引结构中。
其实现过程是先从搜索树的根节点开始遍历,找到插入代价最小(由Penalty
方法实现)的叶子节点进行插入。若叶子节点已满,插入新索引项会导致叶子节点的分裂,也可能造成分裂的向上传播。分裂时将调用用户定义的PickSplit
方法来决定新老节点中索引项的布局。而在向上更新描述谓词时,将会调用Union
方法来确定父节点相应索引项中的描述谓词。其执行流程如图4-29所示。
static void gistdoinsert(Relation r, IndexTuple itup, Size freespace, GISTSTATE *giststate) { GISTInsertState state; memset(&state, 0, sizeof(GISTInsertState)); state.itup = (IndexTuple *) palloc(sizeof(IndexTuple)); state.itup[0] = (IndexTuple) palloc(IndexTupleSize(itup)); memcpy(state.itup[0], itup, IndexTupleSize(itup)); state.ituplen = 1; state.freespace = freespace; state.r = r; state.key = itup->t_tid; state.needInsertComplete = true; state.stack = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack)); state.stack->blkno = GIST_ROOT_BLKNO; gistfindleaf(&state, giststate); gistmakedeal(&state, giststate); }
从根节点往下查找到待插入的节点
static void gistfindleaf(GISTInsertState *state, GISTSTATE *giststate) { ItemId iid; IndexTuple idxtuple; GISTPageOpaque opaque; /* * walk down, We don't lock page for a long time, but so we should be * ready to recheck path in a bad case... We remember, that page->lsn * should never be invalid. */ for (;;) { if (XLogRecPtrIsInvalid(state->stack->lsn)) state->stack->buffer = ReadBuffer(state->r, state->stack->blkno); LockBuffer(state->stack->buffer, GIST_SHARE); gistcheckpage(state->r, state->stack->buffer); state->stack->page = (Page) BufferGetPage(state->stack->buffer); opaque = GistPageGetOpaque(state->stack->page); state->stack->lsn = PageGetLSN(state->stack->page); Assert(state->r->rd_istemp || !XLogRecPtrIsInvalid(state->stack->lsn)); if (state->stack->blkno != GIST_ROOT_BLKNO && XLByteLT(state->stack->parent->lsn, opaque->nsn)) { /* * caused split non-root page is detected, go up to parent to * choose best child */ UnlockReleaseBuffer(state->stack->buffer); state->stack = state->stack->parent; continue; } if (!GistPageIsLeaf(state->stack->page)) { /* * This is an internal page, so continue to walk down the tree. We * find the child node that has the minimum insertion penalty and * recursively invoke ourselves to modify that node. Once the * recursive call returns, we may need to adjust the parent node * for two reasons: the child node split, or the key in this node * needs to be adjusted for the newly inserted key below us. */ GISTInsertStack *item = (GISTInsertStack *) palloc0(sizeof(GISTInsertStack)); // gistchoose 找到插入代价最小的那个节点(调用了gistpenalty方法) state->stack->childoffnum = gistchoose(state->r, state->stack->page, state->itup[0], giststate); iid = PageGetItemId(state->stack->page, state->stack->childoffnum); idxtuple = (IndexTuple) PageGetItem(state->stack->page, iid); item->blkno = ItemPointerGetBlockNumber(&(idxtuple->t_tid)); LockBuffer(state->stack->buffer, GIST_UNLOCK); item->parent = state->stack; item->child = NULL; if (state->stack) state->stack->child = item; state->stack = item;// 继续向下循环 } else { /* be carefull, during unlock/lock page may be changed... */ LockBuffer(state->stack->buffer, GIST_UNLOCK); LockBuffer(state->stack->buffer, GIST_EXCLUSIVE); state->stack->page = (Page) BufferGetPage(state->stack->buffer); opaque = GistPageGetOpaque(state->stack->page); if (state->stack->blkno == GIST_ROOT_BLKNO) { /* * the only page can become inner instead of leaf is a root * page, so for root we should recheck it */ if (!GistPageIsLeaf(state->stack->page)) { /* * very rarely situation: during unlock/lock index with * number of pages = 1 was increased */ LockBuffer(state->stack->buffer, GIST_UNLOCK); continue; } /* * we don't need to check root split, because checking * leaf/inner is enough to recognize split for root */ } else if (XLByteLT(state->stack->parent->lsn, opaque->nsn)) { /* * detecting split during unlock/lock, so we should find * better child on parent */ /* forget buffer */ UnlockReleaseBuffer(state->stack->buffer); state->stack = state->stack->parent; continue; } state->stack->lsn = PageGetLSN(state->stack->page); /* ok we found a leaf page and it X-locked */ break; } } /* now state->stack->(page, buffer and blkno) points to leaf page */ }
在插入索引元组的过程中,会生成一个类型为GISTInsertStack的栈结构,用于记录当前插入节点及其父节点的相关信息。通过该结构能够找到当前插入节点的父节点,当插入节点发生分裂需要插入新节点到父节点中,或更新父节点的信息时,通过该栈保存的信息能够依次向上层进行调整。
其结构如数据结构4.12所示。
插入索引节点,并调整索引结构
void gistmakedeal(GISTInsertState *state, GISTSTATE *giststate) { int is_splitted; ItemId iid; IndexTuple oldtup, newtup; /* walk up */ while (true) { /* * After this call: 1. if child page was splited, then itup contains * keys for each page 2. if child page wasn't splited, then itup * contains additional for adjustment of current key */ if (state->stack->parent) { /* * X-lock parent page before proceed child, gistFindCorrectParent * should find and lock it */ gistFindCorrectParent(state->r, state->stack); } // gistplacetopage会判断待插入节点是否有足够空间, // 空间不够就split(通过gistSplit)和union is_splitted = gistplacetopage(state, giststate); /* parent locked above, so release child buffer */ UnlockReleaseBuffer(state->stack->buffer); /* pop parent page from stack */ state->stack = state->stack->parent; /* stack is void */ if (!state->stack) break; /* * child did not split, so we can check is it needed to update parent * tuple */ if (!is_splitted) { /* parent's tuple */ iid = PageGetItemId(state->stack->page, state->stack->childoffnum); oldtup = (IndexTuple) PageGetItem(state->stack->page, iid); // 通过Union判断是否需要更新父节点的key,需要的话就会返回新key newtup = gistgetadjusted(state->r, oldtup, state->itup[0], giststate); if (!newtup) { /* not need to update key */ LockBuffer(state->stack->buffer, GIST_UNLOCK); break; } state->itup[0] = newtup; } } /* while */ /* release all parent buffers */ while (state->stack) { ReleaseBuffer(state->stack->buffer); state->stack = state->stack->parent; } /* say to xlog that insert is completed */ if (state->needInsertComplete && !state->r->rd_istemp) gistxlogInsertCompletion(state->r->rd_node, &(state->key), 1); }
GiST索引的查询流程与B-Tree索引类似,从根节点开始按深度优先原则自上而下进行检索:
若当前节点R是内部节点,遍历检查R上每个索引项E是否与检索谓词q相符合,
对于满足Consistent(E,q)
的索引项,递归向下检索以 E.ptr 为根的子树。
若R是叶子节点,遍历检查R上每个索引项E是否满足Consistent(E,q)
;
对于满足Consistent(E,q)
的索引项,则通过 E.ptr 取得相应记录与q进行准确匹配;
将匹配成功的记录放结果集中。
GiST索引查询主要通过函数gistnext来实现,该函数通过从上往下搜索索引结构,使用上面的方法找到结果。
在扫描的过程中会生成一个类型为GISTSearchStack栈结构,用于保存扫描过程中内部节点里面满足前述的Consistent方法的节点:如果扫描的是内部节点且找到满足Consistent方法的元组,则将该元组指向的下一层的节点入栈。
其数据结构见数据结构4.13所示:
typedef XLogRecPtr GistNSN; typedef struct XLogRecPtr { uint32 xlogid; /* log file #, 0 based */ uint32 xrecoff; /* byte offset of location in log file */ } XLogRecPtr; /* 结构定义描述了一个名为XLogRecPtr的结构体,它用于表示在XLOG(WAL,Write-Ahead Logging)中的位置指针。XLOG是PostgreSQL中用于持久化数据更改的一种方法,它确保在数据库崩溃时数据的持久性和一致性。 以下是对结构体成员的解释: uint32 xlogid: 这个成员表示日志文件的编号,从0开始计数。在XLOG中,有一系列日志文件,每个文件都有一个唯一的编号,这个编号在XLogRecPtr结构中表示。每个XLOG文件实际上是XLogSegSize(一般是16MB)大小的一个“段”。 uint32 xrecoff: 这个成员表示在日志文件中的字节偏移量。它指示了指定XLOG文件中的具体位置。当组合起来与xlogid时,它标识了一个唯一的物理XLOG文件。分段号和文件内偏移量可以通过将xrecoff除以XLogSegSize来计算,结果整数部分是分段号,余数是段内偏移量。 这个结构中的两个成员组合起来提供了对XLOG中特定位置的唯一标识。当数据库系统需要记录某个事务提交的位置时,就会使用这种结构来表示。通常,这些指针被用来跟踪数据库的事务日志,以支持持久性和故障恢复。 */
执行完 gistnext 函数后,即得到结果集。
GISTScanOpaqueData结构(跟踪索引扫描时的父节点堆栈,记录当前页面和被标记了的页面的信息)
/* * When we're doing a scan, we need to keep track of the parent stack * for the marked and current items. */ typedef struct GISTScanOpaqueData { GISTSearchStack *stack; GISTSearchStack *markstk; bool qual_ok; /* false if qual can never be satisfied */ GISTSTATE *giststate; MemoryContext tempCxt; Buffer curbuf; ItemPointerData curpos; ItemResult pageData[BLCKSZ / sizeof(IndexTupleData)]; OffsetNumber nPageData; OffsetNumber curPageData; } GISTScanOpaqueData; typedef GISTScanOpaqueData *GISTScanOpaque;
static int64 gistnext(IndexScanDesc scan, TIDBitmap *tbm) { Page p; OffsetNumber n; GISTScanOpaque so; GISTSearchStack *stk; IndexTuple it; GISTPageOpaque opaque; int64 ntids = 0; so = (GISTScanOpaque) scan->opaque;// opaque是void*类型的,是一种通用的,表示索引的特定方法 if (so->qual_ok == false) return 0; if (so->curbuf == InvalidBuffer) { if (ItemPointerIsValid(&so->curpos) == false) { /* Being asked to fetch the first entry, so start at the root */ Assert(so->curbuf == InvalidBuffer); Assert(so->stack == NULL); so->curbuf = ReadBuffer(scan->indexRelation, GIST_ROOT_BLKNO); stk = so->stack = (GISTSearchStack *) palloc0(sizeof(GISTSearchStack)); stk->next = NULL; stk->block = GIST_ROOT_BLKNO; pgstat_count_index_scan(scan->indexRelation); } else { /* scan is finished */ return 0; } } /* * check stored pointers from last visit */ if (so->nPageData > 0) { /* * gistgetmulti never should go here */ Assert(tbm == NULL); if (so->curPageData < so->nPageData) { scan->xs_ctup.t_self = so->pageData[so->curPageData].heapPtr; scan->xs_recheck = so->pageData[so->curPageData].recheck; ItemPointerSet(&so->curpos, BufferGetBlockNumber(so->curbuf), so->pageData[so->curPageData].pageOffset); so->curPageData++; return 1; } else { /* * Go to the next page */ stk = so->stack->next; pfree(so->stack); so->stack = stk; /* If we're out of stack entries, we're done */ if (so->stack == NULL) { ReleaseBuffer(so->curbuf); so->curbuf = InvalidBuffer; return 0; } so->curbuf = ReleaseAndReadBuffer(so->curbuf, scan->indexRelation, stk->block); } } for (;;)// 外层循环,遍历每个节点,通过so->stack的next指针一直往后 { CHECK_FOR_INTERRUPTS(); /* First of all, we need lock buffer */ Assert(so->curbuf != InvalidBuffer); LockBuffer(so->curbuf, GIST_SHARE); gistcheckpage(scan->indexRelation, so->curbuf); p = BufferGetPage(so->curbuf); opaque = GistPageGetOpaque(p); /* remember lsn to identify page changed for tuple's killing */ so->stack->lsn = PageGetLSN(p); /* check page split, occured since visit to parent */ if (!XLogRecPtrIsInvalid(so->stack->parentlsn) && XLByteLT(so->stack->parentlsn, opaque->nsn) && opaque->rightlink != InvalidBlockNumber /* sanity check */ && (so->stack->next == NULL || so->stack->next->block != opaque->rightlink) /* check if already added */ ) { /* detect page split, follow right link to add pages */ stk = (GISTSearchStack *) palloc(sizeof(GISTSearchStack)); stk->next = so->stack->next; stk->block = opaque->rightlink; stk->parentlsn = so->stack->parentlsn; memset(&(stk->lsn), 0, sizeof(GistNSN)); so->stack->next = stk; } /* if page is empty, then just skip it */ if (PageIsEmpty(p)) { LockBuffer(so->curbuf, GIST_UNLOCK); stk = so->stack->next; pfree(so->stack); so->stack = stk; if (so->stack == NULL) { ReleaseBuffer(so->curbuf); so->curbuf = InvalidBuffer; return ntids; } so->curbuf = ReleaseAndReadBuffer(so->curbuf, scan->indexRelation, stk->block); continue; } n = FirstOffsetNumber; /* wonderful, we can look at page */ so->nPageData = so->curPageData = 0; for (;;)// 内层循环,遍历节点内的索引项 { n = gistfindnext(scan, n); if (!OffsetNumberIsValid(n)) { /* * If we was called from gistgettuple and current buffer * contains something matched then make a recursive call - it * will return ItemPointer from so->pageData. But we save * buffer pinned to support tuple's killing */ if (!tbm && so->nPageData > 0) { LockBuffer(so->curbuf, GIST_UNLOCK); return gistnext(scan, NULL); } /* * We ran out of matching index entries on the current page, * so pop the top stack entry and use it to continue the * search. */ LockBuffer(so->curbuf, GIST_UNLOCK); stk = so->stack->next; pfree(so->stack); so->stack = stk; /* If we're out of stack entries, we're done */ if (so->stack == NULL) { ReleaseBuffer(so->curbuf); so->curbuf = InvalidBuffer; return ntids; } so->curbuf = ReleaseAndReadBuffer(so->curbuf, scan->indexRelation, stk->block); /* XXX go up */ break; } if (GistPageIsLeaf(p)) { /* * We've found a matching index entry in a leaf page, so * return success. Note that we keep "curbuf" pinned so that * we can efficiently resume the index scan later. */ if (!(scan->ignore_killed_tuples && ItemIdIsDead(PageGetItemId(p, n)))) { it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); ntids++; if (tbm != NULL)// 将匹配的元组放入结果集 tbm_add_tuples(tbm, &it->t_tid, 1, scan->xs_recheck); else { so->pageData[so->nPageData].heapPtr = it->t_tid; so->pageData[so->nPageData].pageOffset = n; so->pageData[so->nPageData].recheck = scan->xs_recheck; so->nPageData++; } } } else { /* * We've found an entry in an internal node whose key is * consistent with the search key, so push it to stack */ stk = (GISTSearchStack *) palloc(sizeof(GISTSearchStack)); it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); stk->block = ItemPointerGetBlockNumber(&(it->t_tid)); memset(&(stk->lsn), 0, sizeof(GistNSN)); stk->parentlsn = so->stack->lsn; stk->next = so->stack->next; so->stack->next = stk; } n = OffsetNumberNext(n); } } return ntids; }
返回与当前页中偏移量’n’后的搜索key一致的第一个索引项的偏移量。(gistnext函数会循环调用它)
如果没有一致的条目,则返回InvalidoffsetNumber。
如果执行成功,则scan→xs_recheck的设置也正确。
/* * Return the offset of the first index entry that is consistent with * the search key after offset 'n' in the current page. If there are * no more consistent entries, return InvalidOffsetNumber. * On success, scan->xs_recheck is set correctly, too. * Page should be locked.... */ static OffsetNumber gistfindnext(IndexScanDesc scan, OffsetNumber n) { OffsetNumber maxoff; IndexTuple it; GISTScanOpaque so; MemoryContext oldcxt; Page p; so = (GISTScanOpaque) scan->opaque; p = BufferGetPage(so->curbuf); maxoff = PageGetMaxOffsetNumber(p); /* * Make sure we're in a short-lived memory context when we invoke a * user-supplied GiST method in gistindex_keytest(), so we don't leak * memory */ oldcxt = MemoryContextSwitchTo(so->tempCxt); while (n >= FirstOffsetNumber && n <= maxoff) { it = (IndexTuple) PageGetItem(p, PageGetItemId(p, n)); if (gistindex_keytest(it, scan, n)) break; n = OffsetNumberNext(n); } MemoryContextSwitchTo(oldcxt); MemoryContextReset(so->tempCxt); /* * If we found a matching entry, return its offset; otherwise return * InvalidOffsetNumber to inform the caller to go to the next page. */ if (n >= FirstOffsetNumber && n <= maxoff) return n; else return InvalidOffsetNumber; } /* gistindex_keytest()——判断这个索引元组是否满足扫描键 成功返回叶子元组时,scan->xs_recheck被设置为是否需要重新检查。 我们重新检查是否有Consistent()函数请求它。 在将key传递给scan->keyData->sk_func之前,我们必须解压IndexTuple中的键(我们之前已经覆盖了sk func以使用用户定义的一致方法,因此实际上我们正在调用它)。 请注意,该函数总是在短期内存上下文中调用,因此我们不需要担心清理已分配的内存,无论是在这里还是在任何一致的方法的实现中。 */
与B-Tree索引类似,当表元组被删除时,GiST索引中与之对应的索引元组不是立即被删除,而是由VACUUM操作来批量完成无效索引元组的清除。
在删除过程中,首先找到叶子节点中需删除的索引项,然后从叶子节点往上回溯更新索引,若删除索引项后,存在空节点,则删除该节点。
Datum gistvacuumcleanup(PG_FUNCTION_ARGS) { IndexVacuumInfo *info = (IndexVacuumInfo *) PG_GETARG_POINTER(0); GistBulkDeleteResult *stats = (GistBulkDeleteResult *) PG_GETARG_POINTER(1); Relation rel = info->index; BlockNumber npages, blkno; BlockNumber totFreePages; BlockNumber lastBlock = GIST_ROOT_BLKNO, lastFilledBlock = GIST_ROOT_BLKNO; bool needLock; /* No-op in ANALYZE ONLY mode */ if (info->analyze_only) PG_RETURN_POINTER(stats); /* Set up all-zero stats if gistbulkdelete wasn't called */ if (stats == NULL) { stats = (GistBulkDeleteResult *) palloc0(sizeof(GistBulkDeleteResult)); /* use heap's tuple count */ stats->std.num_index_tuples = info->num_heap_tuples; stats->std.estimated_count = info->estimated_count; /* * XXX the above is wrong if index is partial. Would it be OK to just * return NULL, or is there work we must do below? */ } /* gistVacuumUpdate may cause hard work */ if (info->vacuum_full) { GistVacuum gv; ArrayTuple res; /* note: vacuum.c already acquired AccessExclusiveLock on index */ gv.index = rel; initGISTstate(&(gv.giststate), rel); gv.opCtx = createTempGistContext(); gv.result = stats; gv.strategy = info->strategy; /* walk through the entire index for update tuples */ res = gistVacuumUpdate(&gv, GIST_ROOT_BLKNO, false); /* cleanup */ if (res.itup) { int i; for (i = 0; i < res.ituplen; i++) pfree(res.itup[i]); pfree(res.itup); } freeGISTstate(&(gv.giststate)); MemoryContextDelete(gv.opCtx); } else if (stats->needFullVacuum) ereport(NOTICE, (errmsg("index \"%s\" needs VACUUM FULL or REINDEX to finish crash recovery", RelationGetRelationName(rel)))); /* * If vacuum full, we already have exclusive lock on the index. Otherwise, * need lock unless it's local to this backend. */ if (info->vacuum_full) needLock = false; else needLock = !RELATION_IS_LOCAL(rel); /* try to find deleted pages */ if (needLock) LockRelationForExtension(rel, ExclusiveLock); npages = RelationGetNumberOfBlocks(rel); if (needLock) UnlockRelationForExtension(rel, ExclusiveLock); totFreePages = 0; // 遍历索引节点,记录空闲的节点 for (blkno = GIST_ROOT_BLKNO + 1; blkno < npages; blkno++) { Buffer buffer; Page page; vacuum_delay_point(); buffer = ReadBufferExtended(rel, MAIN_FORKNUM, blkno, RBM_NORMAL, info->strategy); LockBuffer(buffer, GIST_SHARE); page = (Page) BufferGetPage(buffer); if (PageIsNew(page) || GistPageIsDeleted(page))// 说明这个索引节点是新的或者是已删除的(空闲) { totFreePages++; RecordFreeIndexPage(rel, blkno);// mark a page as free in the FSM } else lastFilledBlock = blkno; UnlockReleaseBuffer(buffer); } lastBlock = npages - 1; if (info->vacuum_full && lastFilledBlock < lastBlock) { /* try to truncate index */ RelationTruncate(rel, lastFilledBlock + 1); stats->std.pages_removed = lastBlock - lastFilledBlock; totFreePages = totFreePages - stats->std.pages_removed; } /* Finally, vacuum the FSM 以深度优先顺序遍历索引树。 */ IndexFreeSpaceMapVacuum(info->index); /* return statistics */ stats->std.pages_free = totFreePages; if (needLock) LockRelationForExtension(rel, ExclusiveLock); stats->std.num_pages = RelationGetNumberOfBlocks(rel); if (needLock) UnlockRelationForExtension(rel, ExclusiveLock); PG_RETURN_POINTER(stats); }
PostgreSQL 8.4.1内建了对box (矩形)、polygon (多边形)和circle (圆形) 等数据类型的GiST索引的支持,
可以在postgresql-8.4.1\src\backend\access\gist\gistproc.c文件中查看到相关代码。这些数据类型可以直接创建GiST索引,其他数据类型如果需要创建GiST索引,则需要用户手动添加。
在postgresql-8.4.1\contrib文件夹下提供了很多扩展的模块,其中也有关于GiST的模块,如:
cube文件夹下是用于多维立方体的GiST索引;
ltree文件夹下是用于树状结构的GiST索引等。编译这些模块,就可以使数据库支持该种数据类型,同时可以在该类型上创建GiST索引。
下面就以多维立方体cube文件夹下的扩展模块为例,讲解如何将其添加到数据库系统中。
查看cube文件夹下的文件可以看出,这些文件已经编写好了增加一种数据类型、相应的操作符、该数据类型的支持函数、以及GiST索引对该数据类型的支持。那么,只需要将这些信息编译进数据库即可。主要包括以下几个步骤:
执行make编译C代码得到cube. so链接库。
这一步主要完成的工作是将该种数据类型所需要的支持函数、GiST索引需要实现的7种函数方法编译到链接库里,供数据库调用。
执行make install,
这时系统就会自动将刚才得到的链接库添加到数据库中,然后执行新生成cube. sql,添加相关命令到数据库系统中。
当执行完成make命令之后,可以看到在当前目录下新生成了一个文件cube.sql,该文件是修改了cube.sql.in得到的(将make得到的cube.so链接库的目录写入了)。若读者感兴趣,也可以自己手动将cube.sql.in 中的命令添加到数据库系统中,只需在执行make之后执行以下命令:
修改cube.sql.in文件。
该文件的主要功能是向数据库系统中添加数据类型(pg.type 系统表)、添加该数据类型及索引的操作符(pg_opelass、pg_amop、pg_operator系统表)以及支持函数(pa_amproc系统表),由于这些函数都要链接到刚才编译得到的cube.so,所以需要修改cube.sql.in文件里cube. so文件的路径。
登录一个数据库,然后执行cube.sql.in语句,PostgreSQL会自动执行cube.sql.in 里所有的语句,将相关信息添加到数据库系统中。
通过以上四个步骤就完成了向数据库系统里添加cube数据类型、操作符、相关函数及其对GiST索引类型的支持,下面就可以像使用数据库自带的数据类型一样使用cube类型。如首先创建一个表:
CREATE TABLE test_cube (
name varchar,
cub cube);
插入一些数据后,即可在该表的cub字段上创建GiST索引,并使用该索引进行查找:
CREATE INDEX test_cube_ix ON test_cube USING gist (cub);
SELECT * FROM test_cube WHERE cub && '(3000,1000),(0,0)' ;
执行make install,
这时系统就会自动将刚才得到的链接库添加到数据库中,然后执行新生成cube. sql,添加相关命令到数据库系统中。
当执行完成make命令之后,可以看到在当前目录下新生成了一个文件cube.sql,该文件是修改了cube.sql.in得到的(将make得到的cube.so链接库的目录写入了)。若读者感兴趣,也可以自己手动将cube.sql.in 中的命令添加到数据库系统中,只需在执行make之后执行以下命令:
修改cube.sql.in文件。
该文件的主要功能是向数据库系统中添加数据类型(pg.type 系统表)、添加该数据类型及索引的操作符(pg_opelass、pg_amop、pg_operator系统表)以及支持函数(pa_amproc系统表),由于这些函数都要链接到刚才编译得到的cube.so,所以需要修改cube.sql.in文件里cube. so文件的路径。
登录一个数据库,然后执行cube.sql.in语句,PostgreSQL会自动执行cube.sql.in 里所有的语句,将相关信息添加到数据库系统中。
通过以上四个步骤就完成了向数据库系统里添加cube数据类型、操作符、相关函数及其对GiST索引类型的支持,下面就可以像使用数据库自带的数据类型一样使用cube类型。如首先创建一个表:
CREATE TABLE test_cube (
name varchar,
cub cube);
插入一些数据后,即可在该表的cub字段上创建GiST索引,并使用该索引进行查找:
CREATE INDEX test_cube_ix ON test_cube USING gist (cub);
SELECT * FROM test_cube WHERE cub && '(3000,1000),(0,0)' ;
如果想了解具体添加了哪些信息到数据库中,可以查看cube\cube.sql.in文件。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。