面向对象数据库中的索引实现技术

摘要：首先介绍主要的3种嵌套属性上的索引实现技术及其操作算法，并分析和比较了它们的优缺点，然后介绍了面向对象工程数据库管理系统OSCAR中的索引实现技术。
关键词：面向对象工程数据库管理系统；查询优化：复杂对象

Index Implementation Techniques in the Object-oriented Databases

Cheng Sheng Chen Qian Dong Jinxiang
（1.CAD/CAM Center of China Aerospace Corporation, Beijing 100037;2.Artificial Intelligence Institute of Zhejiang University,Hangzhou 310027)

【Abstract】This paper firstly introduces the implemetation technique and operation algorithms of three main indexs，analysing and comparing them form the dimensions of feasibility and performance.Then the index implementation techniques in OSCAR,which is an object-oriented engineering database mangement system,were presented
【Key words】Object-oriented engineering database mangement system;Query optimization;Complex object

　　建立在类聚集层次上的索引方法大致可分为3类：嵌套索引 (Nested Index) ，路径索引 (Path Index) ，多索引(Multi-index)。本文详细讨论了3类索引的实现方法和操作算法，并对这3种索引方法从实现方法和操作性能上进行了分析和比较。文章最后介绍了我们自主开发的、面向对象的工程数据库管理系统OSCAR中的路径索引实现技术。

1  建立在类聚集层次上的3类索引
1.1  基本概念
　　定义 1　设 H 是一类聚集层次 C₁ .C₂ … C_n，H上的一条路径定义为 P=C₁.A₁.A₂…A_n(n>1)，其中
　　· C_i是H中的一个类，A_i是中C_i的一个属性，
　　· C_i是类C_i-1的一个属性A_i-1的值域(1<i≤n)。
　　定义 2　设有路径 P=C₁.A₁.A₂…A_n,P上的一个实例定义为n+1个对象的序列O₁.O₂…O_n+1，其中
　　· O₁是P上类C₁的一个实例 ,
　　· O_i是类O_i-1的属性的一个值(1<i≤n)。
　　定义 3　设有路径P=C₁.A₁.A₂…A_n，P的一个部分实例定义为对象序列O₁.O₂…O_j，j<n+1，其中
　　· O₁是P上的一个类C_k的一个实例(k=n-j+2)，并且
　　· O_i是对象O_i-1的属性A_i-1的一个值(1<i≤j)。
　　为更清楚地说明这几种索引方法，在以下的讨论中以图1中的对象数据库模式片段和图2中的一些对象实例为例来说明这3类索引。

图1  一个对象数据库模式

图2  一些对象实例

1.2  嵌套索引
1.2.1 定义
　　设有路径P=C₁.A₁.A₂…A_n，在P上的嵌套索引定义为(O,S)的集合，其中
　　· S={O' 使得存在P的实例O₁.O₂…O_n+1，其中O'=O₁，O=O_n+1},
　　^.(O,S)对中的O是索引关键字。
　　下面是建立在路径P=公民 .拥有汽车.制造商.股票价值上的嵌套索引：
　　^.(200，{教授A})
　　^.(500，{经理A})
　　^.(3000，{经理A教授B，经理B})
　　为方便起见，在以下的讨论中将路径实例中第一个对象和最后一个对象分别称为起始对象和结尾对象。
1.2.2 嵌套索引的操作算法
　　给定一路径P=C₁.A₁.A₂…A_n以及一个定义在该路径上的嵌套索引，
　　(1) 检索算法　对类C₁的嵌套属性A_n上的谓词的计算需要查找索引。对于嵌套索引的查找与一般索引的查找是相同的，即通过关键字直接找到相应的起始对象的标识(OID)。
　　(2) 索引更新算法　设对象O_i(1≤i≤n)是路径上类C_i的一个实例，对象O_i的属性A_i的值是O_i+1，并且A_i的值要被O'_i+1替代。下面是嵌套索引更新的算法：
　　1)根据O_i+1查找出所有A_n的值放入集合S.old，查找是一个从O_i+1开始到A_n的正向游历过程。通常S.old只包含一个元素，除非路径上某个A_i是多值的；
　　2)根据O'_i+1找出所有A_n的值放入集合S.new。如果S.new=S.old，则说明索引不必更新。否则，转3)；
　　3)找出所有直接或间接引用O_i+1的类C_i的实例。这是一个从O_i+1开始的反向游历过程，如果 i=1，则R={O_i}.
　　4)索引更新步骤如下：
　　①如果S.new≤S.old,则△=S.old-S.new；对于△中的每个关键字k，从k的索引纪录中删去所有在R中的的OID；②如果S.old≤S.new，则△=S.new-S.old；对于△中的每个关键字k，将△中的OID加入到k的索引纪录中去；③否则△.1=S.old-S.new并且△.2=S.new-S.old；对于△.1 中的每个关键字k，从其索引纪录中删去R中的OID；对于△.2中的每个关键字k，把R中的OID加入到其索引纪录中去。
1.2.3 实现方法及分析
　　嵌套索引提供了路径的起始对象和结尾对象间的直接关联。嵌套索引可以用B+树结构或哈希算法实现。如果用B+树实现，则需要用两棵B+树来分别实现主、副索引。其中主索引包含与关键字对应的路径上的所有类的对象标识，副索引把主索引纪录中的这些对象标识作为关键字，它将每个对象标识与一列该对象的直接祖先相关联。
　　注意到建立和维护嵌套索引时都要对路径进行反向游历，这要求对象的反向引用的存在，但在实际的对象数据库模式中这种双向引用关系并不多。如果用户建立的数据库模式中不存在反向引用，一个解决方法是由数据库管理系统把所有的单向对象引用关系变为双向的对象引用关系，系统添加的引用关系对用户是不可见的，它的作用仅仅是使系统能够更有效地在对象空间中游历。但这种方法使系统必须对这种关系进行维护而增添很多额外的开销，结果导致系统整体性能的下降，很有可能是得不偿失。而且嵌套索引本身的实现结构已经很复杂，维护也比较困难，所以如果数据库模式中不存在足够的双向引用关系，一般不宜建立嵌套索引。
1.3 多索引
1.3.1 定义
　　设有路径P=C₁.A₁.A₂…A_n，多索引定义为
　　∪₁≤i≤n{I₁,I₂,…,I_i}，
　　其中I_i(1≤i≤n)是定义于路径上的单索引。
　　C_i.A_i 上的单索引是指(O,S)对的集合，O是属于A_i值域的一个值，并且S={O'|O'A_i=O}。
　　注意，在单索引中，关键字可以是基本类型(如整型，字符串等)，也可以是对象标识。
　　建立在路径P=公民.拥有汽车.制造商.股票价值上的多索引如下：
　　(1)　建立在子路径经理.拥有汽车的单索引有：①(轿车A，{经理B})；②(轿车B，{经理A})；③(轿车C，{教授A})；④(轿车D，{教授B})；⑤(轿车E，{经理A})。
　　(2)　建立在子路径拥有汽车.制造商的单索引有：①(公司A，{轿车C})；②(公司B，{轿车A，轿车D，轿车E})；③(公司C，{轿车B，轿车F})。
　　3)　建立在子路径制造商.股票价值的单索引有：
　　①(200，{公司A})；②(3000，{公司B})；③(500，{公司C})；
1.3.2　主要操作算法
　　设有路径P=C₁.A₁.A₂…A_n，对类C_i(1≤i≤n)的嵌套属性A_n上谓词计算需要查找(n-i+1)个单索引。先要查找索引I_n，然后是I_n-1直到I_i，这是一个对路径的反向游历的过程，但这个过程的反向游历并不需要对象反向引用的存在，因为根据索引就可以找到路径中的前一个对象。可以看出，利用多索引并不能直接根据关键字找到相应的对象，而是要查找路径上的每个单索引，所以多索引的检索性能一般不如嵌套索引(当路径长度大于2时)。
　　对多索引的维护就是对每个单索引的维护，对单索引的维护算法是比较简单的。
1.3.3　实现方法及分析
　　多索引可以用多棵B+树分别实现各个单索引。虽然多索引的结构不复杂，维护也比较简单，但其检索性能并不理想(在路径长度大于2时)，所以如果查询中的路径表达式的长度一般都大于 2时，实现多索引并不是很划算。
1.4　路径索引
1.4.1　定义
　　设有路径P=C₁.A₁.A₂…A_n，路径索引定义为(O,S)对的集合，其中
　　· O是A_n值域的一个值，
　　· S={Π_n+1-j(P_i)|P_i=O_i.O_i+1….O_n+1是一个路径的无冗余或完全实例，并且O_n+1=O}。
　　路径索引所在的每个与以为要结尾的所有路径实例间建立了联系。
　　根据图1,图2，建立在路径P=公民.拥有汽车.制造商.股票价值上的路径索引如下：
　　· (200,{教授A.轿车C.公司A})
　　· (500,{轿车E.公司B，教授B.轿车D.公司B，经理B.轿车A.公司B，经理A.轿车E.公司B })
　　· (3000,{ 轿车 F. 公司 C ，经理 A. 轿车 B. 公司 C})
1.4.2　主要操作算法
　　在以下操作算法的讨论中，假设索引是以页面为单位组织的，每个页面由若干个索引纪录组成，每个索引纪录又由若干个路径实例组成，路径实例都是以长度等于路径表达式长度的数组形式存储。
　　给定一个路径P=C₁.A₁.A₂…A_n以及定义在P上的路径索引，
　　(1)检索算法　对于类C_i，1≤i≤n的属性A_n上的嵌套谓词的计算，只需要对索引的一次查找，只要找到与关键字相关的路径实例，其第i个元素就是要找的类C_i的实例OID。对路径索引的查找一般要比嵌套索引的查找涉及更多的页，这是因为路径索引的索引纪录包含了比嵌套索引相应纪录更多的信息。
　　(2)索引更新算法　 设路径上类C_i的一个实例O_i，1≤i≤n，其属性A_i的值O_i+1被 O'_i+1所取代。其索引更新算法如下：
　　①根据O_i+1找出相应的A_n的值并放入集合S.old，一般S.old只包含一个元素，除非路径上的某些属性是多值的；
　　②找出从O'_i+1到属性A_n的部分实例并将其放入集合 SP.new，将从O'_i+1开始遍历找到的A_n的值放入S.new；
　　③对于S.old中的每个关键字k, 找出其索引纪录，对于纪录中的每个路径实例P ,如果其第i 个元素为O_n，第i+1个元素为O_i+1，则执行以下步骤：
　　·　将P的从第1个到第i-1个的部分实例放入临时集合T，
　　·　将P从纪录中删除；
　　④生成第i个元素为O_i，第i+1个元素为O'_i+1的新路径实例，设新实例为pnew，则pnew为T的一个元素，及O_i，O'_i+1和SP.new中一个元素的串接。pnew的总数为n₁*n₂、n₁、n₂分别为T、 SP.new中元素的个数；
　　⑤对于S.new中的每个关键字k，找到相应的时索引纪录，将所有pnew加入到纪录中去。
　　从以上索引更新算法可以看出，路径索引不需要反向游历，而它在嵌套索引中是必需的，因此路径索引比嵌套索引有更好的可用性。
1.4.3　实现方法及分析
　　路径索引可以一棵B+树实现，所以就实现来说路径索引最为方便。但根据文献[3]中的代价模型分析，当路径长度大于1时，路径索引的检索性能并不是最好的，嵌套索引的检索性能最好，多索引的检索性能最差；就维护代价来说，多索引最优，路径索引次之，嵌套索引最差。当路径长度等于1时，3种索引都退化为简单索引。
　　经过对索引性能、维护代价、实现技术复杂度的综合权衡，OSCAR中采用了路径索引。由于 B+树查找效率比较高(一般访问三层树结点就可找到所需纪录)，所以目前大部分商用数据库系统中索引的物理实现主要采用B+树或其变种(如H树等)，OSCAR中也主要采用B+树实现其索引。

2　OSCAR中路径索引的实现方法
　　面向对象工程数据库管理系统OSCAR是由浙江大学人工智能所和中国航天工业总公司CAD/CAM 中心合作研制的、CAD/CAPP/CAM集成环境下的数据库支撑软件产品。为提高系统的查询处理能力，OSCAR中采用了多种索引技术，其中就有为支持嵌套谓词优化的路径索引。为了实现在并发条件下对索引树的操作，OSCAR的索引操作算法中采用了特殊的并发控制策略。索引操作的并发控制是一个复杂的问题，本文不对该问题进行探讨。
2.1　索引纪录结构
　　如前所述，OSCAR中的路径索引用B+树实现。B+树的结点以页面为单位组织，对于非叶结点每个结点占一个页面；而对于叶结点则占有一个或一个以上的页面，具体的页面数取决于插入该页面的索引纪录数以及每个索引纪录中的路径实例数目。
　　B+树的阶数等于页面大小除以非页面索引纪录的大小。为实现高效的I/O操作，页面一般取磁盘块大小的整数倍。在OSCAR中，页面为4kB。
　　在以下的讨论中，用以下的符号表示相应的参数：
　　RL表示纪录长度；KL表示关键字长；KV表示关键字长；IN表示路径实例个数；INSTi表示路径实例i；PNEXT表示指向索引树中一个结点的指针；DIR表示纪录各个路径实例的地址的目录项。
　　索引树非叶面结点中的索引纪录在页面中是根据关键字值大小按照升序排列的，一个非叶结点的纪录结构是这样的：

　　对于索引树叶面结点中的索引纪录，
　　(1)　当纪录长度不超过一个页面的大小时，纪录是这样组织的：

　　其中路径实例以数组形式存放，数组中的元素为按照路径正向游历顺序存放的，路径实例中的对象的OID，数组的长度都为路径表达式的长度，开始时整个数组初始化为空。如果路径实例不是完全路径实例，则数组中有一部分元素为空。
　　(2)　当纪录长度超过一个页面的大小时，一个纪录的路径实例要存储在多个页面上，这时要在纪录头上增加一个目录项，用来纪录每个路径实例的地址，路径实例的地址是二元组(页面号，页内偏移)。纪录结构为如下形式(其中ADDRi表示INSTi的地址)：

3　 结束语
　　本文介绍了目前面向对象数据库中建立在复杂对象上的3类索引，并分析和比较了它们的实现方法和主要操作算法，还介绍了OSCAR中路径索引的实现方法。但目前这几种索引技术还未见有商用系统实现它们的报道。就OSCAR中实现的路径索引来看，其实现的技术难度不大，索引的操作性能也比较令人满意。

基金项目：国家自然科学基金资助
作者简介：程胜（1976～），男，研究生，主要从事面向对象数据库查询处理研究
作者单位：程胜　谌潜（中国航天工业总公司CAD/CAM中心，北京100037）
　　　　　董金祥（浙江大学人工智能所，杭州310027）

参考文献
1 Bertino E,Catania B,Chiesa L. Definition and Analysis of Index Organization for Object-oriented Database Systems.Technical Report, University of Milano, 1996:162-196
2 Bertino E,Foscoli P.Index Organizations for Object-oriented Database Systems.IEEE Trans.on Knowledge and Data Engineering,1995,7(2):193-209
3 Bertino E,Kim W.Indexing Techniques for Queries on Nested Objects. IEEE Trans. on Knowledge and Data Engineering,1989,1(2):196-214

收稿日期：1999-01-04