首先介紹一下索引的整體結(jié)構(gòu)，再具體介紹一下其中B+樹索引的一些特性

索引結(jié)構(gòu)

數(shù)據(jù)存儲：索引數(shù)據(jù)頁頭和與普通數(shù)據(jù)表頁頭一樣的結(jié)構(gòu)，占用24個字節(jié)，ItemIds占用4個字節(jié)；

image.png

每個索引entries結(jié)構(gòu)為IndexTupleData+Bitmap+Value，其中IndexTupleData占8個字節(jié)，Bitmap占4個字節(jié)，Value占4字節(jié)，合計占用16個字節(jié)，數(shù)據(jù)結(jié)構(gòu)如下：

    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+樹數(shù)據(jù)結(jié)構(gòu)

主要介紹頁面中special結(jié)構(gòu)存儲的東西，其他地方和數(shù)據(jù)頁面相同

typedef struct BTPageOpaqueDataInternal {
//B+樹頁面的special區(qū)域
    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的存儲結(jié)構(gòu)，通過Special Space可以獲得B-Tree的root、左右sibling等信息；
有序性：索引的數(shù)據(jù)區(qū)，并沒有按照大小順序排序，索引Page通過索引項指針保證有序性。

postgresql_btree.png

B-tree索引頁面.JPG

B+樹創(chuàng)建順序：

B+樹創(chuàng)建過程.png

1.index_build調(diào)用btbuild函數(shù)

btbuild函數(shù)：

2.構(gòu)造BTBuildState對象，調(diào)用_bt_spoolinit函數(shù)，初始化BTBuildState對象中的BTSpool

3.使用IndexBuildHeapScan函數(shù)獲得需要索引的元組數(shù)量，返回函數(shù)指針buildstate。

4.調(diào)用_bt_leafbuild函數(shù)，將buildstate中得到的索引元組構(gòu)建為索引結(jié)構(gòu)

IndexBuildHeapScan函數(shù)：

掃描堆表中的元組，當發(fā)現(xiàn)有一個元組需要索引時，調(diào)用btbuildCallback函數(shù)，直到全部掃描完成，返回需要索引的元組總數(shù)。

btbuildCallback函數(shù)：

調(diào)用_bt_spool函數(shù)，將需要索引的元組放入到BTBuildState->spool里面

_bt_spool函數(shù)：

調(diào)用tuplesort_putindextuplevalues函數(shù)進行操作

tuplesort_putindextuplevalues函數(shù)：

調(diào)用index_form_tuple函數(shù)設置SortTuple

調(diào)用puttuple_common將SortTuple存入state->memtuples中

這個state就是BTBuildState->BTSpool->sortstate。所以總的來說，還是把IndexTuple存到了BTBuildState。