知名开发网站公司简介,凡科建站快车代理登录,俄文网站建设方案,荆门建网站费用B-Tree索引代码流程分析 专栏内容#xff1a; postgresql内核源码分析手写数据库toadb并发编程 开源贡献#xff1a; toadb开源库 个人主页#xff1a;我的主页 管理社区#xff1a;开源数据库 座右铭#xff1a;天行健#xff0c;君子以自强不息#xff1b;地势坤 postgresql内核源码分析手写数据库toadb并发编程 开源贡献 toadb开源库 个人主页我的主页 管理社区开源数据库 座右铭天行健君子以自强不息地势坤君子以厚德载物. 概述 在postgresql最常用的索引就是btree它支持范围和等值查询。 本文主要介绍btree的代码的入口接口定义主要涉及索引的查询插入删除和数据的清理操作。 前言 索引是为了更快的找到实际数据表中的数据那么索引键值就非常小可以一次性从磁盘读取大量的索引数据。 但是有些索引值中存储了实际数据与数据是一一对应的就是密集型索引而有一些索引并不存储实际数据而是存储范围内的最大最小值此类型索引叫做稀疏索引 对于密集型索引如主键直接可以得到对应的数据位置或对应列的数据btree算法就可以支持此类型的索引 而稀疏索引查到索引后需要再遍历数据表或者二级索引才能命中目标数据。 代码入口
postgresql中为了代码的解耦定义了索引操作的结构体基成员是一组统一的操作和标识选项 对于btree的定义如下可以在这里找到btree索引的操作接口名称在实际实用的只是调用结构体的成员也就是函数指针。
/** Btree handler function: return IndexAmRoutine with access method parameters* and callbacks.*/
Datum
bthandler(PG_FUNCTION_ARGS)
{IndexAmRoutine *amroutine makeNode(IndexAmRoutine);amroutine-amstrategies BTMaxStrategyNumber;amroutine-amsupport BTNProcs;amroutine-amoptsprocnum BTOPTIONS_PROC;amroutine-amcanorder true;amroutine-amcanorderbyop false;amroutine-amcanbackward true;amroutine-amcanunique true;amroutine-amcanmulticol true;amroutine-amoptionalkey true;amroutine-amsearcharray true;amroutine-amsearchnulls true;amroutine-amstorage false;amroutine-amclusterable true;amroutine-ampredlocks true;amroutine-amcanparallel true;amroutine-amcaninclude true;amroutine-amusemaintenanceworkmem false;amroutine-amsummarizing false;amroutine-amparallelvacuumoptions VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;amroutine-amkeytype InvalidOid;amroutine-ambuild btbuild;amroutine-ambuildempty btbuildempty;amroutine-aminsert btinsert;amroutine-ambulkdelete btbulkdelete;amroutine-amvacuumcleanup btvacuumcleanup;amroutine-amcanreturn btcanreturn;amroutine-amcostestimate btcostestimate;amroutine-amoptions btoptions;amroutine-amproperty btproperty;amroutine-ambuildphasename btbuildphasename;amroutine-amvalidate btvalidate;amroutine-amadjustmembers btadjustmembers;amroutine-ambeginscan btbeginscan;amroutine-amrescan btrescan;amroutine-amgettuple btgettuple;amroutine-amgetbitmap btgetbitmap;amroutine-amendscan btendscan;amroutine-ammarkpos btmarkpos;amroutine-amrestrpos btrestrpos;amroutine-amestimateparallelscan btestimateparallelscan;amroutine-aminitparallelscan btinitparallelscan;amroutine-amparallelrescan btparallelrescan;PG_RETURN_POINTER(amroutine);
}我们首先来看索引的基本操作查询btgettuple插入btinsert和删除。 索引查询
索引查询的调用栈
ExecIndexScan 在执行计划中会有索引查询的节点如ExecIndexScan 发起索引查询通过索引查找到数据表的tuple; - IndexNext 返回数据表的tuple 如果是稀疏索引此处会进行二次查找; - index_getnext_slot 返回数据表的tuple此处会使用索引找到的tid在数据表中查找并检查可见性如果不可见那继续查找下一条; - index_getnext_tid 返回索引键中的记录的tid; -btgettuple 在索引中查找, 通过遍历比较命中查找键对应的索引项 查找索引数据的基本流程 索引的查找大致分为两个步骤 找到起始点也就是查找键值从起始点开始扫描返回符合条件的索引项 代码分析
索引的查询入口函数是 btgettuple下面是它的实现
bool
btgettuple(IndexScanDesc scan, ScanDirection dir)
{BTScanOpaque so (BTScanOpaque) scan-opaque;bool res;/* btree indexes are never lossy */scan-xs_recheck false;/** If we have any array keys, initialize them during first call for a* scan. We cant do this in btrescan because we dont know the scan* direction at that time.*/if (so-numArrayKeys !BTScanPosIsValid(so-currPos)){/* punt if we have any unsatisfiable array keys */if (so-numArrayKeys 0)return false;_bt_start_array_keys(scan, dir);}/* This loop handles advancing to the next array elements, if any */do{/** If weve already initialized this scan, we can just advance it in* the appropriate direction. If we havent done so yet, we call* _bt_first() to get the first item in the scan.*/if (!BTScanPosIsValid(so-currPos))res _bt_first(scan, dir); else{/** Check to see if we should kill the previously-fetched tuple.*/if (scan-kill_prior_tuple){/** Yes, remember it for later. (Well deal with all such* tuples at once right before leaving the index page.) The* test for numKilled overrun is not just paranoia: if the* caller reverses direction in the indexscan then the same* item might get entered multiple times. Its not worth* trying to optimize that, so we dont detect it, but instead* just forget any excess entries.*/if (so-killedItems NULL)so-killedItems (int *)palloc(MaxTIDsPerBTreePage * sizeof(int));if (so-numKilled MaxTIDsPerBTreePage)so-killedItems[so-numKilled] so-currPos.itemIndex;}/** Now continue the scan.*/res _bt_next(scan, dir);}/* If we have a tuple, return it ... */if (res)break;/* ... otherwise see if we have more array keys to deal with */} while (so-numArrayKeys _bt_advance_array_keys(scan, dir));return res;
}初始化查找点从代码来看进入循环后先 BTScanPosIsValid(so-currPos) 判断currPos是否有效也就是查找点是否已经初始化如果没有初始化则调用 _bt_first 进行初始化扫描索引项 初始化查找点后调用 _bt_next 获取一条索引项数据找到有效索引后就会返回
索引插入
索引插入调用栈
从insert来看调用路径如下
ExecInsert SQL insert语句的执行入口函数 - ExecInsertIndexTuples 如果当前表中建有索引在表数据tuple插入后调用此函数插入索引有可能存在多个索引循环对每个索引调用下级函数进行插入 index_insert 索引插入的公共调用接口实际调用对应索引的插入定义接口 btinsert btree索引插入的操作的入口函数 在此函数中首先拼装一个索引tuple然后调用下级函数进行插入 _bt_doinsert 执行索引项的插入会经过查找位置检查唯一性插入等一系列流程环节 索引插入的基本流程
索引插入的大体流程主要有以下环节
查找索引项插入的位置因为btree是一个有序的树所以先要找到插入的位置保持顺序 此时会与索引查询类似先初始化查找键并找到查询点唯一性约束的检查如果索引中属性列都为NULL是不进行唯一性检查的索引的插入环节调用_bt_insertonpg来完成其中会有查找空闲空间可能会索引分裂等
代码分析
索引插入的入函数是 btinsert实际执行是 _bt_doinsert下面来看一下执行的代码流程
bool
_bt_doinsert(Relation rel, IndexTuple itup,IndexUniqueCheck checkUnique, bool indexUnchanged,Relation heapRel)
{bool is_unique false;BTInsertStateData insertstate;BTScanInsert itup_key;BTStack stack;bool checkingunique (checkUnique ! UNIQUE_CHECK_NO);/* we need an insertion scan key to do our search, so build one */itup_key _bt_mkscankey(rel, itup);if (checkingunique){if (!itup_key-anynullkeys){/* No (heapkeyspace) scantid until uniqueness established */itup_key-scantid NULL;}else{checkingunique false;/* Tuple is unique in the sense that core code cares about */Assert(checkUnique ! UNIQUE_CHECK_EXISTING);is_unique true;}}insertstate.itup itup;insertstate.itemsz MAXALIGN(IndexTupleSize(itup));insertstate.itup_key itup_key;insertstate.bounds_valid false;insertstate.buf InvalidBuffer;insertstate.postingoff 0;search:stack _bt_search_insert(rel, heapRel, insertstate);if (checkingunique){TransactionId xwait;uint32 speculativeToken;xwait _bt_check_unique(rel, insertstate, heapRel, checkUnique,is_unique, speculativeToken);if (unlikely(TransactionIdIsValid(xwait))){/* Have to wait for the other guy ... */_bt_relbuf(rel, insertstate.buf);insertstate.buf InvalidBuffer;if (speculativeToken)SpeculativeInsertionWait(xwait, speculativeToken);elseXactLockTableWait(xwait, rel, itup-t_tid, XLTW_InsertIndex);/* start over... */if (stack)_bt_freestack(stack);goto search;}/* Uniqueness is established -- restore heap tid as scantid */if (itup_key-heapkeyspace)itup_key-scantid itup-t_tid;}if (checkUnique ! UNIQUE_CHECK_EXISTING){OffsetNumber newitemoff;CheckForSerializableConflictIn(rel, NULL, BufferGetBlockNumber(insertstate.buf));newitemoff _bt_findinsertloc(rel, insertstate, checkingunique,indexUnchanged, stack, heapRel);_bt_insertonpg(rel, heapRel, itup_key, insertstate.buf, InvalidBuffer,stack, itup, insertstate.itemsz, newitemoff,insertstate.postingoff, false);}else{/* just release the buffer */_bt_relbuf(rel, insertstate.buf);}/* be tidy */if (stack)_bt_freestack(stack);pfree(itup_key);return is_unique;
}代码流程如下:
初始化工作 初始化查找键查找插入位置 调用 _bt_search_insert 进行查询到一个有足够空闲空间的叶子节点page检查唯一性约束检查唯一性约束如果有冲突事务则等待冲突事务执行完成后再重新查询位置再检查唯一性约束然后对结果的判断checkUnique ! UNIQUE_CHECK_EXISTING如果违返那么插入结束否则执行插入动作索引插入先确定插入位置再调用_bt_insertonpg
索引删除 索引的更新就是删除和插入操作这里我们来看一下索引删除的概要流程。 对于数据表的tuple的删除数据并没有真实删除所以对应的索引项也不会删除那么什么时候删除索引项呢 删除索引基本流程 在进行vacuum 或进行 prune paga时对于HOT链都会在每个page上留下最后一个数据元组因为同一个page内的HOT链只对应一个索引项留下这最后一个也是为了删除索引项。 当进行vacuum 索引时就会通过这个dead tuple找到对应的索引项先删除索引项再删除dead tuple。 常常说索引的性能下降了其实就是索引膨胀导致也就是deadtuple变多导致待删除索引项变多查询效率大降低同时也会带来索引IO的增加。 代码分析
vac_bulkdel_one_index 调用 通用索引处理接口 -index_bulk_delete 这里通用索引处理接口其中调用对应索引的处理接口这里是调用btree索引处理 -btbulkdelete btree对应的批量删除接口 避免退出的影响在开始时会注册退出的回调函数在解除共享内存前处理善后然后调用 btvacuumscan 对所有page进行索引删除清理。 结尾 非常感谢大家的支持在浏览的同时别忘了留下您宝贵的评论如果觉得值得鼓励请点赞收藏我会更加努力 作者邮箱studysenllang.onaliyun.com 如有错误或者疏漏欢迎指出互相学习。
注未经同意不得转载
