Symfoware数据库索引研究＊

2014-03-14魏明，贾亮

江苏海洋大学学报(自然科学版) 2014年2期

魏明，贾亮

（连云港市东方医院信息处，江苏连云港 222042）

Symfoware Server是富士通针对关键性在线交易的电子商务以及砖块构件业务模式的关系型数据库管理系统，同时它也具有强大的灵活的数据管理引擎，管理大量的数据仓库的解决方案。它提供高效的安全管理、高度的可靠性、高性能和吞吐量，同时也有高度的查询／装载功能。

索引作为数据库系统的一个关键组件，提供了快速访问和存取数据库中信息的途径。在Symfoware中，其索引不但有常见数据库系统的共同特点，还有着自身的一些特性和优势。

本文介绍了索引的基本概念和常见结构，研究了Symfoware的索引结构，最后对话题进行了讨论。

1 数据库系统索引技术

正如图书或文档的目录方便读者快速定位所需信息一样，数据库需要索引高效地实现基本数据操作。索引是对数据库表中一列或多列的值进行排序的一种结构，可将其理解为一种特殊目录。

假设没有索引，数据随机而无序地散放在存储器（如磁盘）上，那么即使用户提交十分简单的查询，系统也不得不扫描存储器的每个存储块，对于需要存储大规模信息的数据库来说，这是不能接受的。为此，需要在数据记录中建立索引结构，以便提高数据访问效率。常见的索引包括以下几类。

（1）顺序文件。最简单的索引结构要求文件按索引属性排序，称为顺序文件，当按照索引属性查找数据时这种结构特别有用。顺序文件的缺陷在于，如果想用另一个属性查找数据，索引将无效。

（2）稠密索引。在索引非顺序文件中，必须为每个记录建立一个索引项，这样的索引称为稠密索引。索引项是一系列存储块，块中只存放记录键及指向记录本身的指针（对于存储在磁盘上的记录，实际上可能是物理地址）。这里的索引是“稠密的”，因为数据文件中每个键在索引中都被表示出来。

（3）稀疏索引。稀疏索引是给每个数据块建立一个索引项，索引键值是数据块第一条记录对应键值。

（4）多级索引。索引文件可能占据多个存储块，若这些存储块不在已知的能找到它们的地方，如指定的磁盘柱面，就需要另一种数据结构找到这些索引存储块。即便能定位索引存储块，且能使用二分查找法找到所需索引项，但若索引块很多，仍需要执行多次I／O操作才能得到所需记录。

（5）B树。虽然一级或两级索引通常有助于加快查询，但在数据库系统中常使用一种被称为B树的更通用的结构，而其最常使用的变体称为B＋树。

B树很自然地推广了二叉查找树，即从“二叉”扩展成“多叉”。B树中，一个节点大小通常相当于一个完整磁盘页（也称桶，BUCKET），故一个B树节点可维护的子女数就由磁盘页大小决定。对存储在磁盘上的B树，通常采用的分支因子（填充因子）为50～2 000。分支因子越大，树高度越小，查找任意关键字所需的I／O操作次数就越少。

2 Symfoware的索引

2.1 DSO／DSI

DSO／DSI是Symfoware的表及其索引所特有的概念，用于定义和描述它们的存储结构。其中，DSO（data structure organization）从逻辑层次上定义存储结构，包括4种类型：SEQUENTIAL，RANDOM，OBJECT和BTREE。DOS的前3种是表的存储结构，而BTREE是表索引的存储结构。DSI（data structure instance）从物理层次上定义表的存储结构，即Database Space（Symfoware使用Database Space来定义磁盘）的分配方式。

在为表创建DSO时，可以指定表中数据的划分方式（通常是根据数据值的不同来定义划分条件），此时需要根据多种划分为表创建多个DSI，DSI会根据DSO中定义的数据划分方法将数据保存在不同的裸设备或文件中。相应的表索引也需要根据多个表DSI来创建相同数目的索引DSI。

分析可见，表及其索引的DSO和DSI是一对一或一对多的映射关系。即表或索引只有唯一的DSO定义其逻辑存储结构，但可对应到一个或多个DSI，图1给出这种关系的图示。Symfoware自诞生起就创造性地引入了DSO／DSI概念，并支持数据分区，这一点甚至领先了ORACLE数据库系统。

图1 DSO和DSI及其索引间的对应关系Fig.1 Corresponding relations between DSO and DSI and it indexes

2.2 B＋树

Symfoware的索引结构实际上是B＋树而非B树，即非叶节点（内节点）只保存关键字和子女节点指针，而叶节点才保存指向数据记录的指针。这么做的优势在于内节点能维护更多关键字和子女节点指针，最大化了分支因子，从而降低了树的高度。

以图2的STOCK－INFO数据库表为例，假定数据是按主键ITMNO顺序存储（表DSO为SEQUENTIAL类型）。若以WHCODE字段为索引，则构造的B＋树见图3。索引分成两部分：所有非叶节点构成索引区，叶节点构成数据区。每个叶节点包含索引字段的键值及相应记录的地址。不难看出，所有叶节点实际上构成了对表数据的稠密索引。

注意到Symfoware中B＋树有两点变化：①对任意内节点，子女数等于关键字数，而不是关键字数＋1；② 内节点最大可容纳关键字数（统称填充因子）和叶节点不一定相同。实际上，Symfoware很灵活，叶节点和内节点的填充因子均可自由指定。

图2 STOCK－INFO表结构样例Fig.2 Sample table structure of STOCK＿INFO

2.3 行标号的处理

和许多数据库系统一样，Symfoware也内建了行标号（ROW－ID）作为唯一标志表记录的“隐藏”列（也称伪列）。“隐藏”是用户无法通过类似“SELECT＊”的语句获取它，但可通过显式指定列名来获取。另外，行标号是只读的，不允许更新和删除。

一般来说，行标号指出了记录所在的数据文件、数据块以及记录在该块中的位置。因此B＋树的叶节点中所保存的记录地址，通常就是行标号。

行标号由48个16进制组成，共24字节。第1组8字节标记了记录的数据文件，第2组标记了所在数据块，最后8个字节标记了记录在块内的偏移。

图3 STOCK－INFO的B＋树结构Fig.3 B＋index constructed for the STOCK＿INFO table

3 Symfoware中B＋树索引的改进

3.1 索引的创建与删除

相对于查找，B＋树中节点的插入和删除相对复杂，因这两个操作可能破坏B＋树的结构，故要考虑随时调整结构。和查找一样，插入操作也是从树的根节点开始，自顶向下进行。Symfoware中向B＋树插入数据时，当B＋树数据区的某一个页块数据增长并超出页的指定大小时，就会创建一个新的页块，并将数据分散放在两个页块上，这就是叶节点的分裂。当其处在索引区的父节点也正好是一个满节点时，父节点也同时要分裂。以此类推，分裂动作递归地向上传播，直到根节点一分为二，树的高度增加1。

在分裂叶节点时，再递归回溯到其祖先节点进行分裂，显然不是好办法。由于B＋树的节点中没有保存父节点指针，因此为了回溯可能还需要使用如下策略：在自顶向下寻找插入节点时，将遍历过的节点按序压入堆栈。

改进的策略是在自顶向下寻找插入节点时，就将沿途遇到的满节点分裂。这样，每次分裂一个节点时，能保证其父节点不需要分裂。显然，改进后的策略不再需要回溯。以下给出Symfoware中B＋树中插入操作的伪代码。

与创建操作类似，可以构建相应的删除操作过程。删除算法中，如果要删除的关键字的路径上的节点有最小的关键字个数时，也可能需要回溯。改进算法的核心思想是，在寻找删除关键字时，如沿途遇到含有最小关键字数的节点，就提前将它和其兄弟节点合并。

3.2 索引的维护

Symfoware提供了两种选项对索引进行维护，以提高索引的效率和整体性能，即：①DEGENERATE选项：索引区空间的重用方法，②Relocation选项，索引区数据的动态重构。

一旦指定了DEGENERATE选项，当插入新数据需要增加索引项时，指向已删除数据的索引及其空间将会被重新利用。使用该选项可以提高索引空间的使用效率，并且缩减创建新索引的次数，但缺点是增加或删除数据时可能会增加几倍的处理时间。如果不指定该选项，那么索引空间不会被复用。

3.3 索引的使用

索引也有缺点，首先它需要占用磁盘空间。通常情况下，这个问题并不突出。但是，如果创建每一种可能列组合的索引，索引文件体积的增长速度将远远超过数据文件。如果有一个很大的表，索引文件就可能达到操作系统允许的最大文件限制。其次，对非查询操作即需要写入数据的操作，如删除、更新和插入等，由于除需写入数据外，还要相应地修改索引，这需要花费额外的时间。总之，索引并非越多越好，用索引也不一定比不用索引好，尤其是表数据不多的情况下，有时候全表扫描甚至比通过索引来查找更快。