/*

validate_index - support code for concurrent index builds We do a concurrent index build by first inserting the catalog entry for the index via index_create(), marking it not indisready and not indisvalid.
Then we commit our transaction and start a new one, then we wait for all transactions that could have been modifying the table to terminate. Now we know that any subsequently-started transactions will see the index and honor its constraints on HOT updates; so while existing HOT-chains might be broken with respect to the index, no currently live tuple will have an incompatible HOT update done to it. We now build the index normally via index_build(), while holding a weak lock that allows concurrent insert/update/delete. Also, we index only tuples that are valid as of the start of the scan (see IndexBuildHeapScan), whereas a normal build takes care to include recently-dead tuples. This is OK because we won’t mark the index valid until all transactions that might be able to see those tuples are gone. The reason for doing that is to avoid bogus unique-index failures due to concurrent UPDATEs (we might see different versions of the same row as being valid when we pass over them, if we used HeapTupleSatisfiesVacuum). This leaves us with an index that does not contain any tuples added to the table while we built the index.
Next, we mark the index “indisready” (but still not “indisvalid”) and commit the second transaction and start a third. Again we wait for all transactions that could have been modifying the table to terminate. Now we know that any subsequently-started transactions will see the index and insert their new tuples into it. We then take a new reference snapshot which is passed to validate_index(). Any tuples that are valid according to this snap, but are not in the index, must be added to the index.
(Any tuples committed live after the snap will be inserted into the index by their originating transaction. Any tuples committed dead before the snap need not be indexed, because we will wait out all transactions that might care about them before we mark the index valid.)
validate_index() works by first gathering all the TIDs currently in the index, using a bulkdelete callback that just stores the TIDs and doesn’t ever say “delete it”. (This should be faster than a plain indexscan; also, not all index AMs support full-index indexscan.) Then we sort the TIDs, and finally scan the table doing a “merge join” against the TID list to see which tuples are missing from the index. Thus we will ensure that all tuples valid according to the reference snapshot are in the index.
Building a unique index this way is tricky: we might try to insert a tuple that is already dead or is in process of being deleted, and we mustn’t have a uniqueness failure against an updated version of the same row. We could try to check the tuple to see if it’s already dead and tell index_insert() not to do the uniqueness check, but that still leaves us with a race condition against an in-progress update. To handle that,we expect the index AM to recheck liveness of the to-be-inserted tuple
before it declares a uniqueness error.
After completing validate_index(), we wait until all transactions that were alive at the time of the reference snapshot are gone; this is necessary to be sure there are none left with a transaction snapshot older than the reference (and hence possibly able to see tuples we did not index). Then we mark the index “indisvalid” and commit. Subsequent transactions will be able to use it for queries.
Doing two full table scans is a brute-force strategy. We could try to be cleverer, eg storing new tuples in a special area of the table (perhaps making the table append-only by setting use_fsm). However that would add yet more locking issues.
*/

bt_build
{
    // table scan
    // 表扫描，基于 snapshot 判断 heap tuple 可见性
    if (RelationIsGlobalIndex(index)) {
        allPartTuples = GlobalIndexBuildHeapScan(heap, index, indexInfo, btbuildCallback, (void*)&buildstate);
    } else {
        reltuples = tableam_index_build_scan(heap, index, indexInfo, true, btbuildCallback, (void*)&buildstate);
    }
    // 按照索引 key 对 tuple 进行排序
    // 基于排完序的 tuple 构建 btree
    _bt_leafbuild(buildstate.spool, buildstate.spool2);
    ...
}

validate_index
{
    ...
    // scan index and gather all the tids into a tuplesort object
    // 这段代码收集索引中的 tids 走的是 vacuum 流程中扫描索引的流程，是按照 physical order 扫描 index pages，
    // 但在 callback 中只是收集 tids 并不会真正删除任何内容
    state.tuplesort = tuplesort_begin_datum(
        TIDOID, TIDLessOperator, InvalidOid, false, u_sess->attr.attr_memory.maintenance_work_mem, false);
    state.htups = state.itups = state.tups_inserted = 0;
    (void)index_bulk_delete(&ivinfo, NULL, validate_index_callback, (void*)&state);
    /* Execute the sort */
    // 按照 tid 大小排序
    tuplesort_performsort(state.tuplesort);
    /*
     * Now scan the heap and "merge" it with the index
     */
    // 第二次 table scan ，每个 scan 出的 tuple， 如果是在 hot-chain 上则是
    // hot-chain 的 root tuple ，在 索引 scan 出的 tuple 中(已经按照 tid 排序)查找，找不到则说明不在索引中，应该追加到索引中。
    // 调用 index_insert 将这个 heap tuple 的索引数据插入索引
    tableam_index_validate_scan(heapRelation, indexRelation, indexInfo, snapshot, &state);
    ...
}

validate_index_heapscan 的主要代码逻辑如下：

validate_index_heapscan
{
    ...
    // 遍历 heap tuple
    while ((heapTuple = heap_getnext(scan, ForwardScanDirection)) != NULL)
    {
        ...
        // 如果在 hot-chain，用 hot-chain 的 root tuple 的 tid 在索引中查找
        if (HeapTupleIsHeapOnly(heapTuple)) {
            root_offnum = root_offsets[root_offnum - 1];
            Assert(OffsetNumberIsValid(root_offnum));
            ItemPointerSetOffsetNumber(&rootTuple, root_offnum);
        }
        ...
        // 在 索引的 tids 中查找，由于索引的 tids 是有序的，
        // 当 heap tuple 的 tid 小于索引的 tid 继续查找，否则
        // 1. 在索引中找到（tid相等），不需要再插入索引
        // 2. 不在索引中，需要插入
        while (!tuplesort_empty && (!indexcursor || ItemPointerCompare(indexcursor, &rootTuple) < 0)) {
            ...
        }
        // 没有找到对应的 tid，需要插入索引
        if ((tuplesort_empty || ItemPointerCompare(indexcursor, &rootTuple) > 0) && !in_index[root_offnum - 1]) {
            ...
            // 追加索引
            (void)index_insert(indexRelation,
                values,
                isnull,
                &rootTuple,
                heapRelation,
                indexInfo->ii_Unique ? UNIQUE_CHECK_YES : UNIQUE_CHECK_NO);
        }
    }
}