如果组的第一个字节符合0xxxxxxx（x表示”可能为0或1”）这种位模式，则该组只包含该字节，该字节被0扩展（zero-extended）以形成一个字符。

如果组的第一个字节符合110xxxxx这种位模式，则该组包含该字节a以及下一个字节b。如果不存在字节b（由于字节a是被读取的最后一个字节），或字节b不符合位模式10xxxxxx，则抛出一个UTFDataFormatException异常。否则，该组被转换为字符 (char)(((a & 0x1F) << 6) | (b & 0x3F))

    如果组的第一个字节符合1110xxxx这种位模式，则该组包含该字节a以及其后的两个字节b和c。如果不存在字节c（由于字节a是最后两个被读取字节中的一个）或者字节b或c不符合位模式10xxxxxx，则抛出一个UTFDataFormatException异常。否则，该组被转换为字符(char)(((a & 0x0F) << 12) | ((b & 0x3F) << 6) | (c & 0x3F))

       如果组的第一个字节符合模式1111xxxx或模式10xxxxxx，则抛出一个UTFDataFormatException异常。

       如果在整个过程中的任何时候遇到文件末尾（end of file），则抛出一个EOFException异常。

       当该过程把所有的组都转换为对应的字符之后，所有的字符被按照它们所对应的组从输入流中被读取的顺序收集起来，最后形成一个返回的字符串。

    由上可知，当一个字符的UNICODE编码值在0-127之间时(ASCII字符)，该字符的编码占用一个字节。当UNICODE编码值在128-2047之间时，该字符的编码占用两个字

节。否则，该字符的编码占用3个字节。

u 提供事务管理但不需要编写大量特定的崩溃恢复（crash recovery）代码

u 使用一次写多次读（WORM）的光盘保存数据库的历史状态，而在普通磁盘上保存当前状态

u 利用专门的硬件

事务系统

每一个事务被赋予一个唯一的事务标识（XID），长度为40位。另外，一个48位交互标识（IID）中的其余8位作为该事务中命令的标识（CID）。

       在事务日志（transaction log）中使用2位来指示每一个事务的当前状态：已提交（committed）、已异常终止（aborted）或正在执行（in progress）。提交一个事务的操作如下：把它在事务日志中的状态从正在执行改变为已提交，并把包含该段日志的块（block）写入到持久性的存储器（stable storage）中。

事务日志尾（tail of the log）是指事务日志中记录从最老的（oldest）活动事务（active transaction）状态直到当前事务状态的这一段日志。事务日志体（body of the log）是指事务日志中的其余部分，这部分日志中的事务状态不可能为正在执行，所以只需要分配1位来表示它们的状态。

       对于事务频繁的应用程序，事务日志体可能在内存中放不下，则POSTGRES应用了一个可选的压缩技术。由于多数事务的结束状态都为已提交，所以事务日志体中包含的几乎都是“提交”位。因此，对于异常终止的事务，POSTGRES有一个可选的bloom filter[STON86]。事务日志尾是一个占用内存很小的数据结构。

当一个新的关系（relation）被创建时，POSTGRES分配一个文件用于存放该关系的记录（records）。如果一个文件中的空间被耗尽，则POSTGRES扩展该文件，扩展尺寸为多个8K的页面。

磁盘中的每条记录都有一个位掩码（bit mask）指示哪些字段（field）是非空（non-null）的，并且只有这些字段被实际存储。每条记录还包含另外的八个字段：

       OID        一个系统赋予的唯一记录标识

       Xmin      插入该记录的交互（interaction）的事务标识

       Tmin       Xmin的提交时间（该记录成为合法记录的时间）

       Cmin       插入该记录的交互（interaction）的命令标识

       Xmax      删除该记录的交互（interaction）的事务标识

       Tmax      Xmax的提交时间（该记录成为非法记录的时间）

       Cmax      删除该记录的交互（interaction）的命令标识

       PTR        一个向前指针（a forward pointer）

当一条记录被插入时，它被赋予一个唯一的OID，Xmin和Cmin则被设置为当前交互的标识，其余五个字段保留为空。

当一条记录被更新时，新版本和老版本通常只有少量字段会不同。为了避免存储一条全新记录的空间耗费，采用了以下所述的压缩技术。初始记录以未压缩的形式存储，并称它为锚点（anchor point）。而对于已被更新的记录，只有那些和锚点中不相同的字段才被存储。此外，锚点中的PTR字段被修改为指向已被更新的记录，它被称为一个差分记录（delta record）。连续的记录更新最终形成了一条从锚点出发的差分记录的单向链表。由于差分记录一般来说是小尺寸的对象，所以它们中的大多数很可能和锚点处于同一操作系统页面中。

一般而言，一条记录在时间T是合法的（valid at time T），如果以下条件为真：

Tmin < T and Xmin is a committed transaction and either:

Xmax is not a committed transaction or

Xmax is null or

Tmax > T

 实际上，为了使用户能够读取当前事务中其它命令所写入的还未提交的记录，实际的合法性测试是以下更为复杂的条件。

Xmin = my-transaction and Cmin != my-command and T = “now”

or

Tmin < T and Xmin is a committed transaction and either:

(Xmax is not a committed transaction and Xmax != my-transaction) or

(Xmax = my-transaction and Cmax = my-command) or

Xmax is null or

Tmax > T

如果没有指定T，那么T = “now”是其缺省值，并且一条记录在时间“now”是合法的，如果：

Xmin = my-transaction and Cmin != my-command

or

Xmin is a committed transaction and either:

(Xmax is not a committed transaction and Xmax != my-transaction) or

(Xmax = my-transaction and Cmax = my-command) or

Xmax is null

一般而言，一条记录在时间段[T1, T2]是合法的（valid in the interval [T1, T2]），如果：

Xmin = my-transaction and Cmin != my-command and T2 >= “now”

or

Tmin < T2 and Xmin is a committed transaction and either:

(Xmax is not a committed transaction and Xmax != my-transaction) or

(Xmax = my-transaction and Cmax = my-command) or

Xmax is null or

Tmax > T1

T1和T2都可以被省略，其相应的缺省值为T1 = 0 以及 T2 = +infinity

并发控制和时间戳管理

POSTGRES使用传统的内存锁表（main memory lock table）实现了一个标准的两段式加锁策略。

POSTGRES使用如下的技术来异步地填充Tmin和Tmax字段。POSTGRES包含一个TIME关系（relation）用于存储每一个事务的提交时间。由于时间戳是32位无符号整数，所以字节4*j到4*j+3用于存储事务j的提交时间。当事务提交时，系统读取当前时间并存入TIME关系相应的槽（slot）中。

POSTGRES中的每一个关系创建时都会被标记为以下三种指示之一：

u       no archive: 指示不需要对关系的历史记录进行访问

u       light archive: 指示需要一个存档（archive）但期望很少对它进行访问

u       heavy archive: 指示需要经常对存档进行访问

对于“no archive”状态的关系，Tmin和Tmax永远不会被填充，因为从不需要对历史记录进行访问。

       如果指定了“light archive”，则允许对历史记录进行访问。当Tmin或Tmax必须和某些特定的值进行比较时，系统从TIME关系中取出相应事务的提交时间以进行比较。

       当处于“heavy archive”条件时，运行时系统使用和“light archive”的情况相同的方法来查找事务的提交时间。然而，它随之把该值写入记录的Tmin或Tmax中，因而把对历史记录的读取操作转变为了写入操作。随后任何访问该记录的合法性验证都不再需要对TIME关系的额外访问。

记录访问

通过顺序扫描可以访问关系中的记录。每个包含记录的页都有一个前向和后向指针，分别指向前一页和后一页。每一页中都有一个行表（line table）[STON76]，由指向该页中锚点起始位置的指针组成。

当插入一条记录时，系统构造一个新的锚点并在所有二级索引（secondary index）中插入相应的索引条目（index entry）。每一个索引记录包含键值以及指向被索引记录所在页中行表中的一个入口。该行表入口指向实际的记录。该单级间接访问方式允许锚点在数据页中移动而不必对二级索引进行维护。

当更新一条已存在的记录时，系统构造一个差分记录并链接入相应的锚点记录。如果更新不涉及被索引的字段，则不需要对二级索引进行维护。如果有被索引字段的更新，则会在相应的索引中插入一个新的条目（entry），该条目包含键值和指向锚点记录的指针。在二级索引中不包含直接指向差分记录的指针。因此，只能通过获取相应的锚点并通过向前链接来访问一个差分记录。

使用该技术保证了在更新记录时，只有当二级索引中的键值被改变时才会产生I/O活动。因为一般来说不会改变被索引字段的值，所以确保了二级索引只需要进行少量的插入操作。

归档系统（THE ARCHIVAL SYSTEM）

系统使用一个后台进程（daemon）把不再合法的记录清扫入存档中。该被称为真空吸尘器（vacuum cleaner）的后台进程通过以下的命令被调用：

       vacuum  rel-name  after  T

其中T是相对于现在（“now”）的时间差。

该真空吸尘器查找满足以下条件中某个条件的归档候选记录：

       Xmax is non empty and is a committed transaction and “now” - Tmax >= T

Xmax is non empty and is an aborted transaction

Xmin is non empty and is an aborted transaction

在上述第二和第三钟情况下，该真空吸尘器仅单纯地回收被记录使用的空间。在第一种情况下，记录必须被拷贝到存档中，除非其所属的关系设置了“no-archive”状态。另外，如果关系被指定了“heavy-archive”，而且在以前的访问中Tmin和Tmax字段还没有被赋值，那么在归档过程中该真空吸尘器必须填充它们。而且，如果可以将锚点和多个差分记录

一起清扫，那么真空化（vacuuming）过程会更有效率。因此，一般来说真空吸尘器会一次性清扫多个记录的链表（chain）。

真空化过程（The Vacuum Process）

真空化过程包括三个阶段，也即：

       阶段1： 写入一个归档记录以及相关的索引记录

下文译自 http://developer.postgresql.org/docs/pgsql/src/tools/backend/index.html

一个查询通过TCP/IP或Unix Domain socket的数据包到达后端（backend）。它被保存到一个字符串中并传送到parser，在那儿，扫描器 scan.l 把该查询分解为一个个的单词（token or words）。该parser使用gram.y 和分解后的单词来标识查询的类型，并装载正确的跟特定查询相关的数据结构，象CreateStmt或SelectStmt。

       然后该查询被标识为一个Utility查询或一个更复杂的查询。一个Utility查询由commands中跟该查询对应的函数处理。一个更复杂的查询，例如SELECT，UPDATE和DELETE则需要更多的处理工作。

       对于一个复杂查询，parser创建一个Query结构用于包含所有会被该查询使用到的元素。Query.qual包含WHERE子句限定，它由transformWhereClause()进行填充。在查询中引用到的每个表都被表示为一个RangeTableEntry，并且它们通过互相连接（linked together）形成了该查询的range table，此range table由transformFromClause()生成。Query.rtable用于存放该查询的range table。

特定的查询，象是SELECT，返回列的数据。其它查询，象是INSERT和UPDATE，指定所需要修改的列。这些对列的引用都被转换为放置于target list entries中的Resdom条目（entry），并且通过互相连接形成该查询的目标列表（target list）。该目标列表保存于Query.targetList中，并由transformTargetList()生成。

其它的查询元素，象是aggregates（SUM()），GROUP BY，和ORDER BY也都存放于它们自己对应的Query字段中。

下一步是使用任何可以应用到该查询上的VIEWS和RULES对它进行修改。该任务由rewrite系统完成。

然后，optimizer接手该Query结构并由此生成一个optimal Plan，其中包含完成该查询所需要执行的操作。RangeTable中每一个表最优化的连接（join）顺序和连接（join）类型由path模块决定，它也使用Query.qual（WHERE子句）来考虑优化的索引使用。

该Plan随之被传送到executor进行实际的执行，并把结果返回给客户端。该Plan实际是一个节点（node）的集合，它被整合为一个树形的结构：有一个顶端节点和一些不同的子节点作为它的儿子。

另外还有许多其它模块以支持该基本功能的实现。