华为openGauss数据库源码解析——B+树操作(2)

下面罗列了openGauss数据库中有关B+树操作的主要函数，并且对其进行一一分析。

BTSpool *_bt_spoolinit(Relation index, bool isunique, bool isdead, void *meminfo)
Datum btbuild(PG_FUNCTION_ARGS)
static inline double tableam_index_build_scan(Relation heapRelation, Relation indexRelation, IndexInfo* indexInfo, bool allow_sync, IndexBuildCallback callback, void* callback_state)   
double IndexBuildHeapScan(Relation heapRelation, Relation indexRelation, IndexInfo* indexInfo, bool allow_sync,IndexBuildCallback callback, void* callback_state)
static void btbuildCallback(Relation index, HeapTuple htup, Datum *values, const bool *isnull, bool tupleIsAlive,void *state);
void _bt_spool(BTSpool *btspool, ItemPointer self, Datum *values, const bool *isnull)
void tuplesort_putindextuplevalues(Tuplesortstate* state, Relation rel, ItemPointer self, Datum* values, const bool* isnull)
static void puttuple_common(Tuplesortstate* state, SortTuple* tuple)
void _bt_leafbuild(BTSpool *btspool, BTSpool *btspool2)
void tuplesort_performsort(Tuplesortstate* state)
static void _bt_load(BTWriteState *wstate, BTSpool *btspool, BTSpool *btspool2)
void _bt_buildadd(BTWriteState *wstate, BTPageState *state, IndexTuple itup)
static void _bt_sortaddtup(Page page, Size itemsize, IndexTuple itup, OffsetNumber itup_off)
void _bt_spooldestroy(BTSpool *btspool)
aminsert (Relation indexRelation,
      Datum *values,
      bool *isnull,
      ItemPointer heap_tid,
      Relation heapRelation,
      IndexUniqueCheck checkUnique);
Datum btinsert(PG_FUNCTION_ARGS)
static void _bt_findinsertloc(Relation rel, Buffer *bufptr, OffsetNumber *offsetptr, int keysz, ScanKey scankey,IndexTuple newtup, BTStack stack, Relation heapRel)
static void _bt_insertonpg(Relation rel, Buffer buf, Buffer cbuf, BTStack stack, IndexTuple itup,OffsetNumber newitemoff, bool split_only_page)
static OffsetNumber _bt_findsplitloc(Relation rel, Page page, OffsetNumber newitemoff, Size newitemsz,bool *newitemonleft)
static void _bt_checksplitloc(FindSplitData *state, OffsetNumber firstoldonright, bool newitemonleft,int olddataitemstoleft, Size firstoldonrightsz)
static Buffer _bt_split(Relation rel, Buffer buf, Buffer cbuf, OffsetNumber firstright, OffsetNumber newitemoff,Size newitemsz, IndexTuple newitem, bool newitemonleft)
void _bt_insert_parent(Relation rel, Buffer buf, Buffer rbuf, BTStack stack, bool is_root, bool is_only)

_bt_spoolinit函数

作用：建立以及初始化一个spool 结构

参数：(Relation index, bool isunique, bool isdead, void *meminfo)

btbuild函数

作用：建立一个新的b+树索引

参数：(PG_FUNCTION_ARGS)

1.构建一个BTBuildState对象，BTBuildState中包含两个BTSpool对象指针，用于将heap tuple加载到内存中，调用_bt_spoolinit函数，初始化BTSpool。

2.调用GlobalIndexBuildHeapScan函数或者 tableam_index_build_scan函数获得需要所有的元组数量，返回函数指针buildstate。

3.调用_bt_leafbuild函数，将buildstate中得到的索引元组构建为索引结构

tableam_index_build_scan函数

这个函数实际上调用的是IndexBuildHeapScan函数

IndexBuildHeapScan函数

作用：扫描堆表结构，寻找需要建立索引的元组

参数：(Relation heapRelation, Relation indexRelation, IndexInfo* indexInfo, bool allow_sync,

IndexBuildCallback callback, void* callback_state)

1.参数检查

2.需要读取所有heap tuple（SNAPSHOT_ANY），然后判断heap tuple是否需要被索引。如果是create index concurrently 基于MVCC snapshot读取heaptuple（SNAPSHOT_MVCC），每个读取出来的heap tuple抽取出索引需要的列信息

3.通过heap_beginscan_strat建立扫描描述符，然后while(heap_getnext),对堆表上的元组循环扫描，判断元组的状态、是否需要建立索引，然后调用callback函数（b+树使用的是btbuildCallback函数），对需要索引的元组进行处理。

4.结束扫描，返回需要索引的元组个数。

HeapTupleSatisfiesVacuum函数

作用：根据一系列规则，判断元组的状态（在astore文件中有提起过）

参数：(HeapTuple htup, TransactionId OldestXmin, Buffer buffer, bool isAnalyzing)

btbuildCallback函数

作用：处理需要索引的元组，建立IndexTuple结构

参数：(Relation index, HeapTuple htup, Datum *values, const bool *isnull, bool tupleIsAlive,void *state)

调用_bt_spool函数进行实现

_bt_spool函数

作用：将SortTuple存入到Spool结构中

参数：(BTSpool *btspool, ItemPointer self, Datum *values, const bool *isnull)

tuplesort_putindextuplevalues函数

作用：将SortTuple存入到Spool结构中

参数：(Tuplesortstate* state, Relation rel, ItemPointer self, Datum* values, const bool* isnull)

1.调用MemoryContextSwitchTo切换内存上下文，防止产生内存泄漏

2.新建SortTuple类型变量，调用index_form_tuple函数，获取IndexTuple变量，将IndexTuple的t_tid指针指向需要索引的堆表元组。设置SortTuple->tuple = IndexTuple，同时设置第一列的值（datum1)，（猜测是用来排序的键值）。

3.调用puttuple_common函数，将SortTuple存入state中。

4.调用MemoryContextSwitchTo切换内存上下文

puttuple_common函数

作用：根据Tuplesortstate的状态，将SortTuple存入state->memtuples数组中

参数：(Tuplesortstate* state, SortTuple* tuple)

1.根据Tuplesortstate的状态。

typedef enum {
    //装载元组,在内存限制之内
    TSS_INITIAL,      /* Loading tuples; still within memory limit */
    //装载元组到有界堆中
    TSS_BOUNDED,      /* Loading tuples into bounded-size heap */
    //装载元组,写入到tape中    
    TSS_BUILDRUNS,    /* Loading tuples; writing to tape */
    //完全在内存中完成排序
    TSS_SORTEDINMEM,  /* Sort completed entirely in memory */
    //完成排序,最后在tape上执行排序
    TSS_SORTEDONTAPE, /* Sort completed, final run is on tape */
    //不落地执行最后的归并
    TSS_FINALMERGE    /* Performing final merge on-the-fly */
} TupSortStatus;

2.TSS_INITIAL状态时，将SortTuple存入state->memtuples数组中，并且判断寻找状态是否需要变成TSS_BOUNDED状态，调用make_bounded_heap函数进行调整，进行排序，生成大顶堆的结构。

3.TSS_BOUNDED状态，如果新元组<=堆顶元素，那么就不考虑这个新元组，否则的话将堆顶元素pop出来， 插入新元组。

4.TSS_BUILDRUNS:状态，直接存入新元组（此时未排序），调用dumptuples函数，如果我们超过了内存限制，转储元组直到低于内存限制