Postgres支持B-tree, hash, GiST, and GIN，也支持用户通过Gist自定义索引方法，比如时空数据库的R-Tree索引。

为了支持索引框架，在创建索引时会查找和操作一系列Catalog元数据，另外为了加速B-Tree索引的构建，会先对待创建索引的数据进行排序，然后再按照B-Tree的页面格式直接写B-Tree的page，避免page的split。

例子

create table t001(id int, i int, j int, k int, msg text);
create table t002(id int, i int, j int, k int, msg text);
insert into t001 select i, i+1, i+2, i+3, md5(random()::text) from generate_series(1,1000) as i;
insert into t002 select i, i+1, i+2, i+3, md5(random()::text) from generate_series(1,1000) as i;
create index t001_i_j on t001(i, j);

创建B-Tree索引分成2个部分:

catalog系统中生成新索引的相关元数据（索引文件也是一个表，因此相关的元数据需要建立和关联起来）；
对索引列进行排序并生成BTree的page；

校验新索引的Catalog元数据

语法解析

create index t001_i_j on t001 using btree (i, j);

通过parse.y将创建索引的sql解析成IndexStmt结构，其中：

IndexStmt
{
    type = T_IndexStmt
    idxname = "t001_i_j"
    accessMethod = "btree"
}

校验B-Tree的handler

using btree执行了索引的类型是btree，因此需要校验内核是否支持该类型的索引。

pg_am

tuple = SearchSysCache1(AMNAME, PointerGetDatum("btree"));

在pg_am中查找"btree"对应的handler

postgres=# select oid,* from pg_am;
 oid  | amname |  amhandler  | amtype
------+--------+-------------+--------
  403 | btree  | bthandler   | i
  405 | hash   | hashhandler | i
  783 | gist   | gisthandler | i
 2742 | gin    | ginhandler  | i
 4000 | spgist | spghandler  | i
 3580 | brin   | brinhandler | i
(6 行记录)

BTree的handler是bthandler，是一个regproc类型，对应pg_proc一个函数。对于内置的BTree索引，相关的函数是在bootstrap过程中插入(pg_proc.dat文件）。

pg_proc

pg_proc.dat文件（下面代码会被重新格式化成postgres.bki文件，并且在inintdb时被bootstrap.y解析插入）：

# Index access method handlers
{ oid => '330', descr => 'btree index access method handler',
  proname => 'bthandler', provolatile => 'v', prorettype => 'index_am_handler',
  proargtypes => 'internal', prosrc => 'bthandler' },

postgres=# select oid,* from pg_proc where proname='bthandler';
-[ RECORD 1 ]---+----------
oid             | 330
proname         | bthandler
pronamespace    | 11
proowner        | 10
prolang         | 12
procost         | 1
prorows         | 0
provariadic     | 0
protransform    | -
prokind         | f
prosecdef       | f
proleakproof    | f
proisstrict     | t
proretset       | f
provolatile     | v
proparallel     | s
pronargs        | 1
pronargdefaults | 0
prorettype      | 325
proargtypes     | 2281
proallargtypes  |
proargmodes     |
proargnames     |
proargdefaults  |
protrftypes     |
prosrc          | bthandler
probin          |
proconfig       |
proacl          |

校验索引列及比较函数

查找pg_attribute，校验create index中指定的索引列是否存在，如果存在记录attno，并且根据atttypid查找对应的比较函数；

校验pg_attribute

postgres=# select a.*  from pg_class c, pg_attribute a  where c.relname='t001' and c.oid = a.attrelid;
-[ RECORD 8 ]-+---------
attrelid      | 16384
attname       | i
atttypid      | 23
attstattarget | -1
attlen        | 4
attnum        | 2
attndims      | 0
attcacheoff   | -1
atttypmod     | -1
attbyval      | t
attstorage    | p
attalign      | i
attnotnull    | f
atthasdef     | f
atthasmissing | f
attidentity   |
attisdropped  | f
attislocal    | t
attinhcount   | 0
attcollation  | 0
attacl        |
attoptions    |
attfdwoptions |
attmissingval |
-[ RECORD 9 ]-+---------
attrelid      | 16384
attname       | j
atttypid      | 23
attstattarget | -1
attlen        | 4
attnum        | 3
attndims      | 0
attcacheoff   | -1
atttypmod     | -1
attbyval      | t
attstorage    | p
attalign      | i
attnotnull    | f
atthasdef     | f
atthasmissing | f
attidentity   |
attisdropped  | f
attislocal    | t
attinhcount   | 0
attcollation  | 0
attacl        |
attoptions    |
attfdwoptions |
attmissingval |

查找比较函数

其中403是pg_am中btree的handler的oid

postgres=# select * from pg_opclass where  opcmethod = 403 and opcintype  = 23;
-[ RECORD 1 ]+---------
opcmethod    | 403
opcname      | int4_ops
opcnamespace | 11
opcowner     | 10
opcfamily    | 1976
opcintype    | 23
opcdefault   | t
opckeytype   | 0

在经过上述元数据校验之后，可以开始为新的索引文件生成相关元数据了。

创建新索引的元数据

在文件系统中创建索引文件

生成Oid

DefineIndex -> index_create -> GetNewRelFileNode

为新的索引文件生成唯一oid，过程是：生成一个新的oid，然后查找pg_class的索引，如果不存在就返回这个oid。

跟新本地的relcache

把正在创建的relation添加到relcache系统中

DefineIndex -> index_create -> heap_create -> RelationBuildLocalRelation

创建文件

DefineIndex -> index_create -> heap_create -> RelationCreateStorage

文件系统中生成新的文件；

路径：
 "file-dio:///home/postgres/tmp_datadir_polardb_pg_1100_bld/base/13881/16391"

生成wal日志，类型是

XLogInsert(RM_SMGR_ID, XLOG_SMGR_CREATE | XLR_SPECIAL_REL_UPDATE)

创建新索引的Catalog元数据

pg_class

新的索引文件也是一个表文件，因此需要插入到pg_class中：

DefineIndex -> index_create -> InsertPgClassTuple

postgres=# select * from pg_class where relname = 't001_i_j';
-[ RECORD 1 ]-------+---------
relname             | t001_i_j
relnamespace        | 2200
reltype             | 0
reloftype           | 0
relowner            | 10
relam               | 403
relfilenode         | 16396
reltablespace       | 0
relpages            | 6
reltuples           | 1100
relallvisible       | 0
reltoastrelid       | 0
relhasindex         | f
relisshared         | f
relpersistence      | p
relkind             | i
relnatts            | 2
relchecks           | 0
relhasoids          | f
relhasrules         | f
relhastriggers      | f
relhassubclass      | f
relrowsecurity      | f
relforcerowsecurity | f
relispopulated      | t
relreplident        | n
relispartition      | f
relrewrite          | 0
relfrozenxid        | 0
relminmxid          | 0
relacl              |
reloptions          |

pg_attribute

把索引文件引用的列插入pg_attr中：

DefineIndex -> index_create -> AppendAttributeTuples

postgres=# select a.*  from pg_class c, pg_attribute a  where c.relname='t001_i_j' and c.oid = a.attrelid;
-[ RECORD 1 ]-+------
attrelid      | 16396
attname       | i
atttypid      | 23
attstattarget | -1
attlen        | 4
attnum        | 1
attndims      | 0
attcacheoff   | -1
atttypmod     | -1
attbyval      | t
attstorage    | p
attalign      | i
attnotnull    | f
atthasdef     | f
atthasmissing | f
attidentity   |
attisdropped  | f
attislocal    | t
attinhcount   | 0
attcollation  | 0
attacl        |
attoptions    |
attfdwoptions |
attmissingval |
-[ RECORD 2 ]-+------
attrelid      | 16396
attname       | j
atttypid      | 23
attstattarget | -1
attlen        | 4
attnum        | 2
attndims      | 0
attcacheoff   | -1
atttypmod     | -1
attbyval      | t
attstorage    | p
attalign      | i
attnotnull    | f
atthasdef     | f
atthasmissing | f
attidentity   |
attisdropped  | f
attislocal    | t
attinhcount   | 0
attcollation  | 0
attacl        |
attoptions    |
attfdwoptions |
attmissingval |
postgres=#

pg_index

把索引本身相关信息插入pg_index中，如果索引包含了表达式，则把表达式通过nodeToString序列化成字符串：

DefineIndex -> index_create -> UpdateIndexRelation

postgres=# select * from pg_indexes where indexname = 't001_i_j';
-[ RECORD 1 ]-------------------------------------------------------
schemaname | public
tablename  | t001
indexname  | t001_i_j
tablespace |
indexdef   | CREATE INDEX t001_i_j ON public.t001 USING btree (i, j)
postgres=#

relcache生效

为了使catalog元数据的变更对所有进程生效，把该heap相关的元数据invalid掉，此处仅仅是注册失效函数，在CommandCounterIncrement，开启执行下一个command时才真正执行invalid。

DefineIndex -> index_create -> CacheInvalidateRelcache

pg_depend

记录该索引对heap的依赖，对collations的依赖，对opclass的依赖，

比如：
t001_i_j依赖表 t001的i；
t001_i_j依赖表 t001的j；

postgres=# select * from pg_depend where objid = 16396;
-[ RECORD 1 ]------
classid     | 1259
objid       | 16396
objsubid    | 0
refclassid  | 1259
refobjid    | 16384
refobjsubid | 2
deptype     | a
-[ RECORD 2 ]------
classid     | 1259
objid       | 16396
objsubid    | 0
refclassid  | 1259
refobjid    | 16384
refobjsubid | 3
deptype     | a

CommandCounterIncrement

使得新索引文件相关的relcache生效

构建B-Tree索引

create index时通过"btree" ，找到bthandler函数，找到btbuild

DefineIndex -> index_create -> index_build -> btbuild

排序

构建sortkey

通过index的索引列构建排序时需要用到的sortkey：

btbuild -> _bt_spools_heapscan -> tuplesort_begin_index_btree

扫描heap表

在非concurrent模式下create index时，为了扫描所有的tpule，snapshot使用SnapshotAny，

btbuild -> _bt_spools_heapscan -> IndexBuildHeapScan -> IndexBuildHeapRangeScan -> heap_getnext

自下向上构建B-Tree索引page

逐个读取排好序的tuple，填充到B-Tree的叶子节点上，自下向上插入B-Tree，插入叶子节点可能会递归的触发起父节点也插入。

page layout

索引页面的内存布局整体上是遵循堆表的布局：pageheader，行指针数组构成。

不同点是：

1. 页面的尾巴上多了BTree自定义的BTPageOpaqueData结构，和左右邻居页面组织成链表；

2. 每个行指针指向的内容由IndexTupleData和key组成；

PostgreSQL 创建B-Tree索引的过程例子校验新索引的Catalog元数据创建新索引的元数据构建B-Tree索引

填充率

向刚刚创建出来的索引插入新的数据时，为了避免split，在第一次构建索引时，每个页面上都预留了一些空间：

1. 叶子节点90%；

2. 中间节点70%；

自下向上构建

填充叶子page：leaf-0;
当leaf-0满了，leaf-0落盘前需要把它的邻居和父节点相关指针更新；
分配一个paret0，leaf-0插入parent0中；
分配一个新的页面leaf-1，leaf-0的右指针指向leaf-1；
leaft-0可以落盘；
leaft-1也满了后，过程和2到6一样；
当leaf-2满了后，要把leaf-2插入父节点，此时父节点也满了，因此要递归的把父节点落盘，过程和2到6一样；

leaf-0

leaf-0满了

leaf-1满了

leaf-2满了，先递归处理parent0满的情况

leaf-2满了，再处理leaf-2自身满的情况

indextuple和scankey的语义

对于叶子节点，indextuple指向heap表的行指针；
对于中间节点，indextuple指向大于scankey的页面，是一个左闭右开区间[scankey, )；

索引页面中真正存放的是indextuple和scankey的组合，在page这个层面中把这两个当做一个item，长度是两者之和；

在实际查找时，同时linp定位到indextuple，由于indextuple是定长的，只需要再往前移动sizeof(indextuple)就能找到scankey的datum和null区域；

根据index的attribute desc来解析datum和null；

key space

对于-Tree中间节点的任意一层，它的所有的indextuple和scankey并集在一起是[负无穷，正无穷]。

由于一对indextuple和scankey组合表达的是左闭右开区间[scankey, )：

1. 对于最右侧的scankey (k4)，它的语义本身就是[scankey，正无穷)；

2. 对于最左侧的scankey (k1)，这个key本身代表的是负无穷的语义：

使用该层出现的第一个key内容(记录在pagesate->minkey)；

indextuple中只记录blkno，使用offset来记录attr为0；

不存储scankey的datum和null；

if (last_off == P_HIKEY)
    {
        Assert(state->btps_minkey == NULL);
        state->btps_minkey = CopyIndexTuple(itup);
        BTreeTupleSetNAtts(state->btps_minkey, 0);
    }
    
    ...
    
    if (!P_ISLEAF(opaque) && itup_off == P_FIRSTKEY)
    {
        trunctuple = *itup;
        trunctuple.t_info = sizeof(IndexTupleData);
        BTreeTupleSetNAtts(&trunctuple, 0);
        itup = &trunctuple;
        itemsize = sizeof(IndexTupleData); //大小仅仅是indextuple，去除了datum和null
    }

high key和first key

每个非最右侧页面都有highkey，highkey的语义是改页面所有key的上界（不包含），因此最右侧页面没有highkey，它的上界是正无穷。

页面1的highkey是在页面1满了之后，生成页面2时确定下来的：

1. 把页面1的highkey内容拷贝到页面2，做为页面2的FIRSTKEY；

2. 设置页面1的P_HIHEY指向最后一个行指针last_off，并且标记last_off为无效指针；

因此，页面1的highkey是页面2的FIRSTKEY。

未满页面的落盘

当所有的heap表都被插入了之后，还没有达到满的页面需要落盘，在自下向上的过程中，插入父节点时是一个递归的过程，为了维护每次递归的状态信息，每层的页面用一个BTPageState结构来描述：

记录level；
记录当前层的最右侧的page；
记录minkey；

BTPageState结构是一个单向链表，因此在插入了所有heap表之后，只需要遍历这个链表，从叶子节点开始落盘。

注意：过程中会往往父节点插入(indextuple,scankey)，可能会触发父节点满了而落盘，因而产生一个新的父节点，所属层的BTPageState会被更新，沿着BTPageState链表会最终把这个新产生的页面也落盘了。

metapage

metapage记录B-Tree：level，root，fastroot等信息。

metapge始终在索引文件的第0个page，root的位置是不固定的。

PostgreSQL 创建B-Tree索引的过程例子校验新索引的Catalog元数据创建新索引的元数据构建B-Tree索引

例子