在PostgreSQL的基础就是Tuple数据的管理均是由以此，

    源文件在: postgresql/src/backend/access/common/heaptuple.c 在函数heap_compute_data_size中，该函数用来计算Tuple的大小，在该函数的输入参数中，isnull 用来标识该tuple种的数据，那些属性上是可以为null，因为在关系数据库中，对于一张表上的字段，某些字段可以为空，而这些为空的字段在保存在tuple时候，通过构建该tuple的函数中体现，对于空属性则使用字符’n’来占位描述，而对于非null属性则使用’ ‘ 来进行占位。

heap_fill_tuple 函数用来完成对于tuple数据填充。最后的数据都分装在Datum* values中，该函数是用来加载数据。

当我们创建一个表时候，会使用xdb_catalog.c中的heap_create来，由于catalog中所保存的数据均为元数据信息，由于xmldb是架构在pg基础上的，因此我们的元数据管理，仍然采用pg的一套规则，我们所创建的所有表在pg的底层均存在中, 例如： pg_catalog表。

由于我们将Tuple的的列的描述机制进行了修改，将TupleDesc改由ColumInfo来描述，即：对于关系数据库我们在创建表的时候，使用
createTable A {
col1 int,
col2 varchar,
col3 char
}

如上的脚本进行创建表时候，我们可以清楚描述该表的列信息：该表上有多少个列，每个列的大小，类型等信息等信息，而这些基本信息会在pg_attribute(?) 系统的元数据表中保存。在需要使用的时候我们可以根据该表的oid来在系统元数据表中进行查找从而能获得该表的列信息。

但是我们不同与关系数据库其可以通过脚本创建表，而我们xml数据库则则没有通过脚本来创建表的接口，因此我们将表的列信息使用columninfo来描述，而这些columninfo在系统初始化时候就进行设置，这些我们可以从metaData.cpp中可以看出 getColInfo函数，描述了使用Oid来进行获取ColumnInfo的方法。然后会在 relache.c中的构造一个Relation对象，并将设置该新构造的Relation对象的相关参数，例如：Relation的oid, TupleDesc等参数，然后将该Relation插入到relcache中，所以这些操作均在 RelationBuildLocalRelation中完成。 在RelationOpenSmgr，完成对relation到后台文件系统的映射，例如：根据releation 的oid以及databbase oid以及table space的oid来生成相应的文件路径，如：base/1222/22/。在完成了Relation到oid的映射后，我们就可以按照该生成的路径来生成相应的物理文件，该项功能由 RelationCreateStorage来完成，而存储层(物理磁盘 Magnetic Disk)与Relation由 SMgrRelation来描述，例如在 storage.c中

而smgropen函数中完成对于SMgrRelation的打开工作，其首先会从hash table中进行查找，如果没有的话会缓存进去。然后调用smgrcreate函数来完成对于物理文件的创建， smgr_create所对应的函数为 mdcreate函数，而该函数是磁盘文件系统的管理函数，直接与os文件系统交互。 在完成上述的物理文件创建后，对于xmldb系统来说，其会将其插入到元数据表中(table id: 254, 此表上创建了相应的索引 )。

然后使用 xxx_heap_formtuple函数来完成Tuple的构造，将数据(char* 或者Datum形式的数据，封装在Tuple中) 然后调用 simple_heap_insert函数来进行数据插入。而在该函数中，又使用heap_insert来进行数据的插入。新的tuple被打上当前事务id和当前的命令id。

在该函数中（heap_insert）首先要进行相应的infomask掩码的设置并设计该tuple所对于的事务id和命令id等等信息(例如：HeapTupleHeaderSetXmin, HeapTupleHeaderSetCmin, HeapTupleHeaderSetXmax等，而这些参数又是标识该元组可见性的重要数据。) (大家想想，在插入数据的时候会涉及到哪些问题？ 元组的可见性，事务冲突性检查，然后buffer更新？然后磁盘写入，日志的记录等等问题) 。

接下来进行读写行的冲突检查，当我们没有检测到相应的读写冲突时候，说明我们可以进行相应的插入操作，此时首先会将该tuple插入到相应的buffer中，在完成插入到buffer之前，我们要根据所给出的relation id 在buffer中查询出可以空间满足我们所插入tuple大小的buffer来，而该项操作由函数 RelationGetBufferForTuple来完成。 从官方源码中的注释： * Returns pinned and exclusive-locked buffer of a page in given relation * with free space >= given len. 可以看出，当满足该空间要求后，会将该buffer进行上锁操作，以防止该空间被其它事务所使用。当我们在buffer pool中没有找到所需要的buffer空间时候，说明我们这个page没有在buffer中，因此需要我们使用fsm来查询空闲的buffer块， 当我们能够从buffer pool中查找到相应的page时候我们使用BufferGetBlockNumber函数来获得该buffer所对应的块号，这样我们在进行数据写入的时候可以定位到相应的块号，当没有空闲的空间时候，使用GetPageWithFreeSpace来从fsm所描述的空闲空间上查找到空闲空间，在完成上述操作后，通过函数ReadBufferBI将指定的块号的数据读入buffer中（这里不再详细描述，其使用ReadBuffer_common函数来完成与操作系统文件系统的io操作，由函数smgrnblocks来完成读取指定block的数据）

BufferPool的构成形式，
——————————————–
page1 | page2 | page3| …. | pageN|
——————————————–

在完成relation的查找后，获得目标buffer的位置，然后就使用RelationPutHeapTuple 函数将之前所设定好的Tuple，保存到该buffer上。使用PageAddItem函数将Tuple中所所对应的数据，按照PageHeader中所描述的

此项结构进行数据填充，此时需要将修改LinpN已经ItemDataPointer所指向的数据，以及pd_lower和pd_upper的指针，这两个在PageHeaderData中的指针描述了数据可以空间的上下限。然后该buffer标记为dirty状态，表明该buffer需要进行刷盘操作，然后进行日志写入(WAL)。 而标记dirty的过程就是将该buffer进行上锁，然后将标准设置为dirty。 写磁盘使用的操作由后台进程 bgwriter来完成，由于在markdirty时候，首先要写日志，并设置一个checkpoint，因此后台进程bgwriter在检查到该checkpoint时候，就会执行buffersync操作。 此时如果系统crash后，也可以通过日志来进行redo操作完成数据的写盘操作。

至此我们就完成了，创建一个relation，然后插入数据的过程。

下面我们将分析下数据的读取：
首先调用 relation_open来打开一个表，relation。首先会从relation cache中进行查找，并将cache中的relation返回，而后系统会调用heap_beginscan来进行开始扫描，而其会调用真正的扫描heap_beginscan_internal函数来完成对数据的扫描。在heap_beginscan_internal函数内部首先系统会构造一个scandesc对象，而这个对象描述了如何使用何种条件进行数据扫描，例如：所要扫描的表的oid，snapshot类型，扫描的key的数量，以及开始和结束的块的编号。首先，需要判断是否需要加意向锁（？那么为啥 indexscan的时候不需要加意向锁? 由于在进行indexscan的时候，我们会在特定的page range内加锁，而对于普通的heapscan没有使用更细粒度的锁，因此我们需要首先判断是否需要加意向锁，这只是在全表扫描的且事务是序列化事务隔离级别的时候，为了保证序列化事务下。不容许进行数据插入。）； 然后会启动initscan启动扫描，在该函数中主要初始化设置HeapScanDesc对象。那么问题来了，我们是如何获得数据的呢？ 不能就仅仅是初始化完HeapScanDesc对象就可以了？ 答案是：heap_getnext函数。 使用该函数来获得相应的满足条件的数据。

heap_getnext函数又调用 heapgettup函数来真正的数据的获取，在进行初步判断后（例如：是否已经做过initscan操作，已经该要查找的relation是否为空等），就使用heapgetpage来获取满足条件的page，读取相应page的函数由ReadBufferExtended来完成。（大家注意该函数的输入参数），在该函数中会使用SMgrRelation对象来进行实际物理磁盘的读写；（1）使用RelationOpenSmgr宏来根据 relation中所指定的表oid，数据库的oid，tablespace的oid来与物理文件的映射(详细如何映射，后续讲座进行详述)，然后就是该函数进行 ReadBuffer_common来根据所指定的blocknum来读取相应的数据，由于这里我们讨论的是全表扫描故而是由表的第一个块号进行读取数据，因此在HeapScanDesc->rs_nblocks =1 ; ///* number of blocks to scan */ ; 对于函数ReadBuffer_common的输入参数大家可以仔细看看下，其所需要的参数，其中描述了其开始的块号，ForkNum，以及所需要读取的blocknum，smgrread完成与md的交互(md为 magnetic disk管理的代码)。至此，我们从创建一个表开始，如何创建一个表，其在创建表的过程发生了什么，以及在进行全表扫描的过程中发生了什么，系统是如果知道需要查找那些数据(具体点是：起始块号和结束块号等等)。

对于索引扫描： 对于xmldb来说我们定义一个所谓的EntrySetScan这么一个类，而该类描述了我们所打开表的所做的扫描条件信息。而我们的openIndexEntrySet 函数所做的操作就是根据表的oid来打开一个表，此种的操作与传统的普通表的打开是一样的。 这里就不在详述了。然后对调用startEntrySetScan来完成对于ScanKey的初始化工作，这些工作最好都由fd_ScanKeyInitWithCallbackInfo函数来完成，其主要是设置比较函数，比较条件等信息。而这些比较条件在扫描的过程中会调用预先设置的回调函数句柄已经条件信息等来完成tuple的index搜索。按下这些不表，我们继续 startEntrySetScan函数的分析，而这些比较条件则存储在ScanKeyData类的sk_address和sk_arglen两个域中，而这两个域是pg原生代码中不存在的（具体pg的处理方式以后在论）。在完成索引条件的初始化(构建)和表的打开操作后，我们就可以开始进行索引扫描了，由函数index_beginscan 来完成索引扫描的操作，而该函数内部会调用btbeginscan函数来完成扫描，在此期间会完成IndexScanDesc的信息初始化工作，startEntrySetScan函数中第一次执行fd_index_beginscan时候并未设置相应的scan conditon的数据，而在在该函数中的第二次scan的时候进行设置，即调用fd_index_rescan时候将该scanConditon传入到IndexScanDesc类型中，因为第一次我们只是生成出一个初始的IndexScanDesc对象并对其进行相关简单参数的设置，第二次时候是进行相关Scan Condition的设置并调用btrescan进行重新扫描。在完成对于index表的打开已经初始扫描条件的初始化工作后，我们相当于已经打开了一个索引表并且已经获得了我们需要的扫描比较条件，那么我们就可以沿着这个b+tree的根节点进行遍历，每次遍历过程中都需要与我们所给出的条件进行相比较，该过程由函数 index_getnext来完成。

但是在扫描的过程中有一个问题需要我们尤为注意的是HOT链中的数据处理方式不同（有什么不同呢？何为HOT链？其用来解决什么问题？请大家思考）。在index_getnext函数中又会使用btgettuple的索引树的底层函数来根据我们的扫描条件来获取相应的数据，接下来就是调用_bt_first，_bt_next 等函数在b+树上进行遍历了，但在大家要主要在B+树上遍历的时候会有需要对元组的可见性进行判断的过程，这点大家又注意，同时索引树上可能存在着所谓的”dead”数据，这是由于我们在建立索引的过程中，这些数据可能对于本事务是属于dead，但是对于其它事务来说，这些dead数据又有可能是属于非dead数据，因此在创建过程中我们还是将这些数据建立在索引中， 这写函数最后归更到底总会通过SMgrRelation以及md.c中所定义的smgr中的bufferread落实到读盘操作的，该过程与上述的heapscan的最后落实的读盘操作类似，这里不再详述了。

在PostgreSQL中存在Tuple和Index Tuple两种数据存储格式，其中Tuple为我们组织普通数据的方式，而Index Tuple则是我们组织索引数据所采用的方式。

   存储的过程：

(1) 读取元组时所需要的cache,

存在着两种不同的cache一种存储系统表元组，另外一种存储表的基本信息和元组的模式结构（即元组的column信息）

(2) 元组的数据信息，需要用到缓冲区，因此我们需要对于缓冲区的管理模式需要有所了解。

(3) 当缓冲区没有数据时，需要从外存上进行数据读取，smgr模块需要认识。

(4) VFD

(5) FSM

下面是Tuple的组织形式（图片均来着网上，如果有侵权告知，删除）

而Tuple Head的组织形式如下图所示：

HeapTupleHeaderData来描述，元组的头信息。 到元组形成的过程中，在写向磁盘之前，我们对于元组的可见性不做要求，而在该数据结构中的第一个域：
union
{
HeapTupleFields t_heap ;
DatumTupleFileds t_datum ;
}

其中的t_heap 描述了该元组的可见性，其由 xmin, xmax , commandid 来描述，因为postgreSQL使用mvcc来描述了元组的可见性。 而mvcc则是由xmin, xmax, commandid来，进行heap visible check.

而 HeapTupleHeaderData中的 ItemPointerData t_ctid用来描述了该元组在磁盘中的数据位置（block中的位置，已经在该block中的偏移量）

由于postgresql使用mvcc方式来进行并发控制， 因此对于元组的更新操作，系统并不会真正的对该元组进行操作，而是新插入一个新元组， 此时便会使用该变量 t_ctid.

数据在存储的时候，会将数据的类型也保存。 数据在使用的过程中由于其对于其可见性和数据的类型(长度)等要求不同，故而可以将上述的两类信息进行分开处理，union。

Datums of composite types (row types) share the same general structure as on-disk tuples, so that the same routines can be used to build and examine them.

当数据形式的时候，将填充t_datum填充(In-memory时候)，但当数据插入到表中时候，则需要判断该数据的可见性。 Xmin和Xmax总是实际存在，而CMax和Xvac使用同一存储空间。

而t_ctid则永远指向新的数据位置。

表操作和元组操作:
表的操作并不是真正的打开表的物理文件，而是将描述该表的关系的relationdata返回。当打开表的时候其会首先咋relcache中进行插座在，当在cache中查询到相应的关系时候则其会直接从Relcache中返回其所对于的relcache并将其refcount加一，并根据其类型进行枷锁操作，并将该relationdata返回。 同样，更加表名打开表的操作相似，只不过是首先进行由表名到oid的转换，首先将表名转换为oid，然后在根据oid使用relation_open函数进行表的打开工作。

获取元组信息：
heap_beginscan函数进行元组的索引查找。而在该函数内部则使用heap_beginscan_internal来进行索引扫描。 一个完整的Tuple由HeapTupleData和一个TupleDesc来描述。 而HeapTupleData中又由一个HeapTupleHeaderData的结构来描述HeapTuple。

其中 HeapTupleDesc描述了，该relation中元组的属性关系，即该表的列的属性等信息的描述信息。 因为数据在磁盘上是属于无结构，因此如果需要让该数据具有相应的类型信息的话，则需要一个描述数据，来描述该数据的类型，例如：第一列是何种类型信息，第二列是何种信息。在插入元组之前，为了将所插入的数据格式化为所需要的信息，首先需要将这些数据按照tuple的格式进行格式化处理。

因此，调用函数heap_formtuple来将所给定的数据构造成相应的tuple。 对于空属性则使用字符’n’ 来描述，而对于非空属性则使用’ ‘一个空格符合来描述。

对于函数heap_formtuple函数的形式参数isnull数组描述了该条数据中那些属性为空，因为对于一张表，其中的某些属性可以为空，而在进行数据插入时候，对于属性可以为空的列，我们的无法使用某个具体的数据来描述这个null值。 因此我们使用了isnull数组来描述属性的是否为空的特性。 而函数heap_compute_data_size用来计算该元组所需要的内存大小，以该大小在内存中分配空间，而后进行tupleheader数据的填充，在完成这些元组的control info的时候，我们就可以使用heap_fill_tuple来进行真实数据的插入填充。在完成数据的填充后，我们就可以使用heap_insert来进行数据的插入。同理，当我删除元组时候，我们并不是真正的进行数据删除而是，在此基础上进行的标识，即mvcc方式，这些标识删除的数据并未真正的在磁盘被删除，而是在进行vaccume时候进行真正数据删除。

而该数据的删除由heap_delete来完成。

heap_delete 删除的流程：首先要根据tid在相关的缓冲区中进行加锁操作，由于其需要在对该缓冲区进行修改操作，因此需要对该缓冲区进行加排他锁(Exclusive Lock)。 当完成对于缓冲区的锁定后，需要判断所需要删除元组的可见性，并根据可见性决定后续的操作步骤。例如：当该元组被当前事务修改时或者已修改，则需要将该元组的ctid指向新的元组地址.

关于索引：(src\backend\access\nbtree文件夹中)

使用ambuild来创建一个新的索引，在使用ambuild之前，索引文件的物理文件以及创建，但是为空。需要通过ambuild来通过IndexBuildHeapScan来在基表中扫描出满足索引条件的tuple，然后再该索引文件上建立索引。

ambuild函数：创建一个索引。–call–> IndexBuildHeapScan ()

aminsert函数 : 向现有的索引中插入一个新的索引tuple，并根据option来判断该索引是否为唯一索引，当该索引要求为唯一索引，则在插入之前会检查该元组是否已经存在该索引中，当该tuple存在该索引中，则返回一个错误信息。

ambulkdelete：从索引中批量删除元组。该函数实际会调用 amvacuumcleanup来执行实际删除。其实质是调用vaccum来对无效元组进行清除操作。 其会在vacuum之后调用，进行一个额外处理：FSM文件清理。空闲文件清除工作。

amcostestimate：进行索引扫描代价估算。通过调用优化器的标准过程完成。

ambeginscan：开始一个扫描，通过构造一个indexscandescData，然后使用该描述符进行扫描。通过调用ambeginscan创建IndexScanDescDat。而该scan函数的主要作用是调用RelationGetIndexScan函数来获得IndexScanDescData。

amgettuple：来获取满足条件的下一个tuple，并通过使用方向标准来移动。同理，amgetbitmap则返回一个bitmap来表示。

amrescan：重启一个扫描。 RelationGetIndexScan。同样也可以进行索引扫描初始化工作。

amendscan 结束索引扫描。

ammarkpos标记当前的扫描函数。 当前的扫描符的opaque字段中。

索引的元组信息：即索引的信息，IndexTupleData 结构来描述了相应的索引元组数据。 在基表元组数据到索引元组数据的过程中，由BTBuildState结构用于保存索引元组。由于HOT链的存在，在进行扫描表的元组时，所获得元组可能是dead tuple，即通过mvcc方式所产生的旧的元组。对于这样的索引元组放在spool2中，因此对于对于唯一索引，不需要检查该元组是否唯一，可直接插入到索引中。（为何要将dead tuple也插入索引数据中？在mvcc机制下，当数据发生了更新后，会产生一个old数据，而该old数据，在执行vacuum时候将会被清除。那为何还要在索引的创建过程中将这些dead tuple建立在索引上？） [dead tuple相对于其它事务而言，本事务内可能是dead tuple但其它事务可能不是dead tuple，因此我们要将这些dead tuple也创建索引。当对于所有的事务都处于dead tuple时候，则可以使用。当该dead tuple对于所有的事务都是dead tuple时候，则可以使用vacuum来进行清除操作。请参考：两个函数中对于dead tuple的判读，HeapTupleSatisfiesVacuum， GetOldestXmin]

每个B-Tree所以都有一个metaPage，该改meta-page用来描述该b-tree的版本号，根节点的位置(所在的块号)以及根节点所以在树的层次信息，meta-page始终在b-tree 的第一页中，但是该meta-page的信息是在索引的创建过程中分步骤进行信息更新的，首先会预留位置，当索引创建完成后，将关于该索引所创建的信息进行赋值。 fastroot接的，当从root节点进行开始查找时候，当从root节点到叶子点之间存在着唯一的路径时候，由于其只有唯一的路径，为了加快到叶子节点的查询速度，可以将root到第一个存在分支路径的路径的中间路径忽略，在查询过程中，只要将从该分支节点开始查找。

btbuild函数：用来创建索引，btbuild首先使用indexBuildHeapScan对表进行扫描，将每个元组封装成索引元组，在封装的过程中还需要判断元组是否为dead tuple，如果非dead tuple则将该索引tuple放在spool中，否则将dead tuple所对于的索引元组放在spool2中。

在完成对基表数据的扫描后，即上述过程。创建一个BTWriteState结构对象，然后将BTBuildState结构中的spool和spool2中的元组进行排序，这样做是为了在索引构建过程中，不需在索引树上来回遍历，在排序完成后，会使用_bt_load函数顺序读取spool中的元组，然后对每个元组使用_bt_buildadd来添加索引元组：将这些数据插入到叶子节点上。当spool和spool2都不为空时候，使用merge方式来将这些spool和spool2数据进行创建索引。

当完成索引添加后，使用_bt_uppershutdown填充元数据。

通过，_bt_leafbuild函数来对已经排好序的元组进行索引构建。

btbeginscan函数，开始扫描。该函数按需要的扫描的索引相关信息生成一个IndexScanDesc结构。而该结构中保存了扫描键值，查询到的位置等信息。