数据库可扩展索引技术解析

# 数据库可扩展索引技术解析 ## 1. 数据库索引技术概述 随着数据库应用的发展，对复杂数据的管理和查询需求日益增长。传统的数据库索引技术，如 B - 树索引，在处理用户自定义类型的数据时存在诸多限制。而新兴的可扩展索引技术为解决这些问题提供了新的思路。 ### 1.1 Oracle8i 的可扩展索引架构 在 Oracle8i 中，对于图像数据的处理展示了可扩展索引的优势。在 Oracle8i 之前，图像插件没有索引支持，图像查询只能通过全表扫描进行，需要对每一行进行图像比较，效率极低。 例如，对于图像查询，在 Oracle8i 中，使用可扩展索引框架，VIRSimilar 操作符的执行分为三个阶段： 1. **第一阶段**：对索引数据表进行范围查询的过滤器。 2. **第二阶段**：计算距离度量的另一个过滤器。 3. **第三阶段**：进行实际的图像比较。 通过这种多级过滤过程，避免了对每一行进行图像比较，同时优化了索引数据表上的范围查询，大大提高了图像查询的性能。现在可以在存储数百万行的表上进行图像比较，这在之前的版本中是无法实现的。 示例查询： ```sql SELECT * FROM images T WHERE VIRSimilar(T.img.Signature, querySignature, ‘globalcolor=0.5, localcolor=0.0, texture=0.5, structure=0.0’, 10,1); ``` ### 1.2 DB2 通用数据库的可扩展索引支持 IBM 的 DB2 通用数据库实现了重要的对象 - 关系概念，如结构化类型、子类型、继承和值可替换性等。通过提供关系扩展器，DB2 可以轻松支持对新数据类型（如文本、图像、视频、音频和空间数据）的基于内容的搜索。 然而，现有的商业数据库在支持用户自定义对象的访问和索引方面较为原始。B - 树通常是唯一的索引访问方法，索引创建和扫描存在诸多限制。例如，只能在访问方法能理解的数据类型的表列上创建索引，并且索引扫描只能利用访问方法能理解的谓词。 为了解决这些问题，提出了一个用于用户自定义类型的高级索引框架。该框架允许用户专注于应用程序的语义和用户自定义谓词，而无需关注锁、恢复、缓冲区管理或平衡搜索树更新等底层细节。它与数据库引擎紧密集成，支持对新数据类型进行索引和使用新谓词进行索引扫描，增强了底层访问方法的价值。 ## 2. 现有数据库系统索引的局限性 ### 2.1 B - 树索引的工作原理 B - 树是关系数据库中最流行的索引访问方法。在使用 B - 树作为内置索引访问方法时，大多数数据库系统只支持原始索引。索引通过指定表名、索引列集、排序顺序和唯一约束来定义。 例如： ```sql CREATE TABLE employee (empno Char(6), name Char(20), title Char(20), salary Integer); CREATE INDEX salary_index on employee (salary ASC); ``` B - 树索引是一种平衡树，每个节点包含一组排序范围 - 指针对。排序范围由索引键值标识，用于确定 B - 树的遍历路径。指针用于从 B - 树的一层到另一层。插入或删除元组时，会根据索引列的值拼接成索引键来操作索引。 ### 2.2 现有索引支持的隐式假设及局限性 现有数据库系统在索引支持方面存在以下隐式假设和局限性： 1. **直接基于表列值创建索引**：索引键是索引列值的拼接，这对于用户自定义对象（如大二进制对象或文本文档）不适用。即使索引列是内置类型，用户可能也想基于索引列值的派生值创建索引，如基于工资的补偿级别或书籍标题中的关键字。 2. **假设索引键值域存在全序关系**：索引搜索受单个索引键值范围的限制，对于用户自定义谓词（如在特定位置一定距离内的搜索）可能不够。 3. **仅考虑简单关系运算符的谓词**：查询优化器在索引利用时，只考虑简单的关系运算符谓词。而用户自定义谓词可能包含外部函数，查询编译器需要能够识别这些谓词并推导相应的搜索空间，以利用用户自定义类型的索引进行高效查询执行。 ## 3. 用户自定义类型的高级索引框架 ### 3.1 索引维护 为了解决索引键与索引列值绑定的问题，引入了用户自定义的键转换（key transform）。给定索引列的值，键转换返回一个或多个索引键值。键转换通常是一个返回集合的函数，可以在对象 - 关系数据库管理系统中实现为表函数，结果表中的每一行形成一个索引键。 键转换带来了以下好处： 1. **逻辑分离索引键和索引列值的域**：由于索引列可以是任何用户自定义类型，其值可能是大对象或结构丰富的文本文档，无法直接存储在索引中。但通过键转换派生的索引键可以创建索引。 2. **优化索引特性**：即使索引列的值都是内置类型，使用键转换派生的索引键也可能具有更好的特性，如将高维空间映射到线性有序空间，保持多维聚类。 3. **抽象索引键**：从抽象解释的角度看，索引键可以看作是索引列对应值的抽象，更简单且占用空间更少。 4. **多对多映射**：一个索引列的值可以映射到多个索引键，不同索引列的值可以有相同的索引键，一个索引列的值也可以有多个关联的索引键。 定义 1：设 S 是一个具体域，I 是一组索引键。从 S 到 I 的键转换是一个类型为 S → 2I 的函数 K。K 的键查找是一个从 I 到 2S 的函数 L，定义为 L(i) = {s | i ∈ K(s)}。我们称四元组 (S, I, K, L) 为索引抽象。 示例： - K1：恒等函数。 - K2：将地理对象映射到一组固定大小的网格。 - K3：将 XML 文档映射到一组路径。 - K4：将文本文档映射到一组关键字。 ### 3.2 用户自定义谓词和搜索键生成 现有数据库系统支持简单的关系运算符谓词，其搜索范围可以根据运算符和绑定参数轻松确定。为了提供对用户自定义对象的可扩展索引，需要解决两个问题： 1. 用户自定义类型可能不支持标准的关系比较，即使支持，这些关系也可能无法直接转换为索引键上的搜索范围。 2. 用户自定义谓词可能是一个复杂的条件，需要复杂的计算来确定相应的搜索范围。 为了解决这些问题，引入了搜索方法的概念。每个搜索方法是一个用户自定义函数，给定用户自定义对象上的语义关系和其搜索模式之一，返回一组搜索键。 定义 2：设 A = (S, I, K, L) 是一个索引抽象。关于 A 的索引是一个从 2S × I 到 2S 的（搜索）函数 f，其中 f 的第一个参数是 S 的一个有限子集，表示当前索引中的对象集。如果对于每个有限集 O ⊆ S（索引对象）和每个索引键 i ∈ I，f(O, i) ⊆ O ∩ L(i)（分别地，f(O, i) ⊇ O ∩ L(i)），则索引 f 是健全的（分别地，完整的）。 示例： ```sql CREATE TABLE customer (name varchar(20), id integer, ..., xyloc location); CREATE INDEX locationIdx on custom ```