三元索引

如索引基础概念页面中介绍的，SmartEDB 的三元索引在无法确切知晓目标对象的准确拼写时，对于文本搜索而言是理想的选择。它能找出与输入的搜索词中最大数量的三字符字符串相匹配的对象，即近似匹配。传统的树索引允许精确匹配查询（例如 x='qqq'）、范围查询（例如 x >= 10 且 x <= 100）以及前缀匹配查询（例如 x >= 'abc'）。

然而，对于像**“%xyz%”**这样更复杂的正则表达式，树形索引需要进行顺序搜索，这会慢很多。在这种情况下，三元索引可能是最优选择。

假设我们有一个字符串键**“qwerty”**。该字符串被拆分为三元组：即三个连续字符的序列：“qwe”、“wer”、“ert”、“rty”。

这些三元组被存储在一个普通的树形索引中。现在考虑一个查找子字符串“wert”的查询。查询条件也被拆分为三元组：“wer”和“ert”。然后在索引中查找这些三元组。查找的结果是两个对象列表——即所谓的反向列表。接下来的步骤是合并这些列表：即找出同时存在于两个列表中的对象。

通过此算法找到的对象尚不能保证实际包含“wert”子串。例如，它可能是“werrert”。因此，查找过程的下一步是重新检查该对象是否确实与给定的正则表达式匹配。

从上述描述中可以清楚地看出三元组索引的主要局限性：它不能用于长度小于 3 的子字符串。例如，即使存在三元组索引，模式 '%01%' 仍需要进行顺序搜索。

三元组索引可用于定位包含指定子字符串的对象以及正则表达式匹配；类似于 SQL 中的 LIKE 操作符。对于 LIKE 操作符，运行时仅从模式中提取最长的不含通配符的子字符串，并对此子字符串进行搜索，然后对所有选定的对象执行正则表达式匹配。如果数据集未声明其他索引，也可以使用三元组索引进行精确匹配查找。