首先介绍一下索引的整体结构，再具体介绍一下其中B+树索引的一些特性

索引结构

数据存储：索引数据页头和与普通数据表页头一样的结构，占用24个字节，ItemIds占用4个字节；

image.png

每个索引entries结构为IndexTupleData+Bitmap+Value，其中IndexTupleData占8个字节，Bitmap占4个字节，Value占4字节，合计占用16个字节，数据结构如下：

    typedef struct IndexTupleData {
        ItemPointerData t_tid; /* reference TID to heap tuple */

        /* ---------------
         * t_info is laid out in the following fashion:
         *
         * 15th (high) bit: has nulls
         * 14th bit: has var-width attributes
         * 13th bit: AM-defined meaning
         * 12-0 bit: size of tuple
         * ---------------
         */

        unsigned short t_info; /* various info about tuple */

    } IndexTupleData; /* MORE DATA FOLLOWS AT END OF STRUCT */

    typedef IndexTupleData* IndexTuple;

    typedef struct IndexAttributeBitMapData {
        bits8 bits[(INDEX_MAX_KEYS + 8 - 1) / 8];
    } IndexAttributeBitMapData;

    typedef IndexAttributeBitMapData* IndexAttributeBitMap;

    typedef struct ItemPointerData {
        BlockIdData ip_blkid;
        OffsetNumber ip_posid;
    }

B+树数据结构

主要介绍页面中special结构存储的东西，其他地方和数据页面相同

typedef struct BTPageOpaqueDataInternal {
//B+树页面的special区域
    BlockNumber btpo_prev; /* left sibling, or P_NONE if leftmost */
    BlockNumber btpo_next; /* right sibling, or P_NONE if rightmost */
    union {
        uint32 level;                /* tree level --- zero for leaf pages */
        ShortTransactionId xact_old; /* next transaction ID, if deleted */
    } btpo;
    uint16 btpo_flags;      /* flag bits, see below */
    BTCycleId btpo_cycleid; /* vacuum cycle ID of latest split */
} BTPageOpaqueDataInternal;

typedef BTPageOpaqueDataInternal* BTPageOpaqueInternal;

typedef struct BTPageOpaqueData {
    BTPageOpaqueDataInternal bt_internal;
    TransactionId xact; /* next transaction ID, if deleted */
} BTPageOpaqueData;

typedef BTPageOpaqueData* BTPageOpaque;

Special Space：介绍了索引PageHeaderData的Special Space的存储结构，通过Special Space可以获得B-Tree的root、左右sibling等信息；
有序性：索引的数据区，并没有按照大小顺序排序，索引Page通过索引项指针保证有序性。

postgresql_btree.png

B-tree索引页面.JPG

B+树创建顺序：

B+树创建过程.png

1.index_build调用btbuild函数

btbuild函数：

2.构造BTBuildState对象，调用_bt_spoolinit函数，初始化BTBuildState对象中的BTSpool

3.使用IndexBuildHeapScan函数获得需要索引的元组数量，返回函数指针buildstate。

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

IndexBuildHeapScan函数：

扫描堆表中的元组，当发现有一个元组需要索引时，调用btbuildCallback函数，直到全部扫描完成，返回需要索引的元组总数。

btbuildCallback函数：

调用_bt_spool函数，将需要索引的元组放入到BTBuildState->spool里面

_bt_spool函数：

调用tuplesort_putindextuplevalues函数进行操作

tuplesort_putindextuplevalues函数：

调用index_form_tuple函数设置SortTuple

调用puttuple_common将SortTuple存入state->memtuples中

这个state就是BTBuildState->BTSpool->sortstate。所以总的来说，还是把IndexTuple存到了BTBuildState。