索引支持

SmartEDB支持哈希索引和以下类型的树索引：tree (b-tree), patricia (Patricia Trie), rtree (R-tree spatial), kdtree (kd-tree multi-dimensional), trigram (text substring) and user-defined (“custom”)。哈希和唯一树索引也可用于唯一标识数据库中的对象。此外，还提供了 oid 和 autoid 类型的专用哈希索引作为唯一对象标识符。然而，与 oid 和 autoid 不同，哈希和树索引值仅需要在一个类中是唯一的；可以使用非唯一声明允许哈希或树索引有重复值。

（有关以下描述的每种索引类型的详细描述和实现细节，请参阅“索引和游标”页面。）

树索引

SmartEDB树索引是应用程序内存中的一种类似树的结构，包含一组键。键可以是简单的（基于单个字段）或复合的（包含多个字段）。树索引以排序顺序存储键。为了支持排序，树索引必须具有比较函数。无论键类型（简单或复合）如何，比较函数必须能够比较两个键，并确定第一个键是否小于（比较返回 -1）、等于（0）或大于（1）第二个键。树索引算法根据此比较对键进行排序。

搜索方法

mcocomp 模式编译器生成搜索 API，通过唯一标识符或索引来定位所需的对象或对象组。虽然通过唯一标识符（唯一树或哈希索引、oid 和 autoid）使用生成的 _find()函数进行精确匹配查找对于定位单个对象非常高效，但上述丰富的专用索引使用游标将一组对象作为有序或无序的结果集进行导航。

查找

根据定义，对唯一索引的精确匹配查找返回恰好一个结果，如果未找到匹配项则返回零。因此，对于 C 和 C++应用程序，mcocomp 模式编译器为每个唯一索引生成一个 _find()函数。Java 和 C#应用程序使用 Cursor.Find()方法。

搜索

游标本质上是结果集中对象集合的迭代器。对于模式定义中为一个类声明的每个索引，DDL 编译器生成函数来实例化游标，根据某些值对其进行定位，并从游标获取数据库对象的句柄。列表和非唯一基于哈希的游标允许按顺序（从第一个到最后一个，或从最后一个到第一个）进行导航，尽管序列的顺序未定义；它只是一种迭代类的无序对象列表的机制。

对于 C 或 C++应用程序，mcocomp 为模式中的每个非唯一索引生成一个 _search()函数。Java 和 C#应用程序使用 Cursor.Search()方法。每当需要确定以下情况时，就使用搜索函数：

在具有已知起始值的排序列表中确定起始位置，并可选地以升序或降序获取后续结果。
在仅知道部分起始值的排序列表中确定起始位置，找到最接近的匹配项，并可选地以升序或降序获取后续结果。
如上所述确定起始位置，以升序或降序在排序列表中迭代，直到达到下限/上限，使用 _compare()方法确定何时达到范围限制。
具有已知起始值的起始位置，迭代列表以获取每个重复项，使用 _compare()方法确定何时获取到最后一个重复项。

模式搜索

SmartEDB还支持“通配符”模式匹配能力。这是搜索与使用通配符指定的模式匹配的树索引条目的能力，用于单字符和多字符匹配。默认情况下，问号“?”将匹配模式中指定位置的任何单个字符，而星号“”将匹配该位置的任何字符组合（包括无字符）。如果需要匹配字符“?”或“”，可以在模式搜索策略中指定不同的字符来修改通配符本身（见下文）。

例如，“Ge”将返回“Graves”和“Gorine”，而“Gr?ve”将匹配“Graves”、“Grove”、“Grover”等......在这个例子中，''匹配零个、一个或多个字符，而'?'恰好匹配一个字符。此外，模式“GE”将匹配所有大写条目，如“GRAVES”、“GORINE”。但是，由于用于将索引值与搜索键进行匹配的标准比较函数使用区分大小写的比较函数，因此搜索模式中指定的大小写将影响搜索结果。

键值包含索引

SmartEDB允许对内存（瞬态）数据库类进行“键值包含”或“缓存无关”实现。这加快了某些访问模式的访问速度。特别是对非常大的 B 树索引的实验显示出显著的性能改进。此外，三元组索引（如下所述）通过“键值包含”树实现，因为在索引页上保留 3 个额外字节（三元组）比简单存储 8 字节对象地址（需要进一步的访问步骤）要高效得多。

覆盖索引

如果索引搜索中请求的所有字段都在索引树节点中可用，那么运行时不必再次查找索引所涵盖的对象。这可以显著提高搜索性能。由于所有请求的字段都在索引中可用，因此该索引称为“覆盖索引”。此外，“覆盖”索引也可以声明为包含以利用 CPU 缓存使用。

Patricia Trie索引

Patricias索引使用基于基数为 2 的基数树的Patricia Trie结构。“trie”一词源自“retrieval”（检索）一词。Patricia 代表“Practical Algorithm to Retrieve Information Coded as Alphanumeric”（用于检索编码为字母数字信息的实用算法）。此算法经过优化，可快速执行 IP 地址前缀匹配，用于 IP 子网、网络或路由表查找。因此，帕特里夏树索引对于网络和电信应用特别有用。

帕特里夏索引可以针对标量和布尔数据类型以及这些类型的数组和向量进行声明。实际上，引入布尔数据类型是为了便于实现帕特里夏索引，其中位阵列用于存储 IP 地址。

R 树索引

R 树索引通常用于加速空间搜索，例如，查找包含此点的矩形、查找与此矩形重叠的所有矩形，或查找此点附近的所有矩形。

可以使用 R 树索引存储和搜索各种形状。例如，一个点表示为宽度和高度均为 1 的矩形，一条具有起始和结束坐标为 15, 844 和 0, 3647 的线存储为左上角为 15, 844 右下角为 0, 3647 的矩形。

要确定两条线是否相交，或者一个点是否在给定区域（由圆、矩形等描述）内，将执行 R 树搜索以查找所有重叠的矩形。

KD 树索引

KD 树是一种用于在 k 维空间中组织点的数据结构。KD 树对于涉及多维搜索键的查找等多种应用是一种有用的数据结构。KD 树是一棵二叉树，其中每个节点都是一个 k 维点。每个非叶节点生成一个分割超平面，将空间划分为两个子空间。超平面左侧的点表示该节点的左子树，超平面右侧的点表示右子树。超平面的方向选择如下：与每个将子树分割的节点关联一个 k 维，使得超平面垂直于该维度向量。

KD 树使用示例查询方法来定位与给定搜索条件匹配的对象。应用程序创建模式对象并为包含在搜索条件中的字段分配值。KD 树支持简单的精确匹配以及范围查找。在后一种情况下，将指定两个模式对象：一个用于下限，一个用于上限的搜索条件。如果仅为一个边界定义了字段值，则它被视为一个开放区间，对应于大于或等于或小于或等于搜索条件。

三元组索引

三元组搜索是一种在不知道目标对象的确切语法或拼写时搜索文本的方法。它查找与输入搜索词中最大数量的三个字符字符串匹配的对象，即近似匹配。经典的 B 树索引允许精确匹配查询（例如 x='qqq'）、范围查询（例如“x >= 10 和 x <= 100”）和前缀匹配查询（例如“x >= 'abc'）。

然而，对于更复杂的正则表达式，如“%xyz%”，B 树索引需要顺序搜索，这要慢得多。在这种情况下，三元组索引可能是理想的。

三元组索引的想法相当简单。假设我们有一个字符串键'qwerty'。该字符串被拆分为三元组：三个连续字符的序列：“qwe”、“wer”、“ert”、“rty”。这些三元组存储在一个普通的 B 树索引中。现在考虑查找子字符串“wert”的查询。查询条件也被拆分为三元组：“wer”和“ert”。然后搜索在索引中查找这些三元组。查找的结果是两个对象列表 - 所谓的逆列表。下一步是连接这些列表：即找到同时存在于两个列表中的对象。