Patricia 树索引

如索引基础概念页面中介绍的，SmartEDB 的Patricia 树索引可用于对 IP 地址及类似的字母数字字符串进行最佳访问。

在 Patricia 索引上执行的搜索操作使用的是特定于 Patricia 的搜索方法：最长匹配（LongestMatch）、精确匹配（ExactMatch）、前缀匹配（PrefixMatch）和下一个匹配（NextMatch）。

最长匹配

最长匹配（LongestMatch）搜索会定位索引值与键值从右开始匹配的字符或位数最多的记录，即匹配的字符或位数最多的记录。

例如，考虑一个名为 Operators 的类，其中包含字符串字段 prefix 和 operator，并且在 prefix 字段上有一个 Patricia 索引，以及以下值：

请注意，光标会定位在与键值匹配的最后一条记录上。为了遍历结果集以访问所有与键值匹配的记录，应用程序将使用 nextMatch 函数或方法。

精确匹配（ExactMatch）搜索会定位索引值与所提供的键值完全匹配的第一条记录。如果未找到完全匹配项，则返回 MCO_S_NOTFOUND。

例如，使用上述表格：

前缀匹配（PrefixMatch）搜索与最长匹配搜索类似，不同之处在于前缀匹配搜索会找到索引与键值匹配的第一个对象，而最长匹配搜索则返回匹配程度最长（最深）的对象。

因此，根据上述表格：

在将光标定位在结果集内之后，可使用下一个匹配（NextMatch）搜索在结果集中遍历以访问所有与键值匹配的记录。若要按顺序遍历数据库对象，应用程序可以使用标准的光标 next 或 prev 操作，但这些函数不受用于执行初始搜索的键值的约束；因此，迭代可能会超出键中指定的范围。

与返回 <0、0 或 >0 的其他索引比较函数不同，基于 Patricia 的比较函数会返回键与游标所指向对象之间第一个不同位的编号。这允许以类似于“标准”比较 API 的方式中断游标遍历。此外，应用程序能够细化游标遍历。

例如，考虑包含以下值的路由表：

    128.1.1.0
    128.1.1.10
    128.1.1.20
    128.1.2.0
    128.1.2.10
    128.1.3.0

存储在一个名为 Nodes 的数据库类中，该类在整数位数组字段 ipaddr 上使用了 Patricia 索引。假设应用程序正在查找整个子网 128.1.1。搜索键值将作为参数传入：

    10000000|00000001|00000001 binary or 8388865

使用此键值和长度 24（即 24 位）调用前缀匹配搜索，将游标定位到 ipaddr 等于 128.1.1.0 的对象。
现在调用 NextMatch 函数以推进到记录 128.1.1.10，而 Patricia 比较函数返回值 28，这意味着记录的 ipaddr 与键值匹配了 28 位。
游标下一次操作会移动到记录 128.1.1.20，此时 Patricia 比较函数返回 27；
然后游标下一次操作会移动到记录 128.1.2.0，此时 Patricia 比较函数返回 22。

此时应用程序会得出结论，已离开感兴趣区域，因为密钥大小为 24 位，而在第 22 位检测到了不匹配。换句话说，密钥不再是当前由游标指向的对象中值的前缀。