KD树索引

如索引基础概念页面中介绍的，SmartEDB 支持KD树（ K维树）索引，非常适合多维键值搜索。

KD 树是一种用于组织k 维空间中点的数据结构。KD 树是一棵二叉树，其中每个节点都是一个 k 维点。每个非叶节点生成一个分割超平面，将空间划分为两个子空间。超平面左侧的点代表该节点的左子树，超平面右侧的点代表该节点的右子树。超平面的方向选择方式如下：每个分裂为子树的节点都与 k 维中的一个维度相关联，使得超平面垂直于该维度向量。

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

KD 树搜索示例

为了演示KD 树索引的用法，请考虑以下示例模式：

    class Car
    {
        string vendor;
        string model;
        string color;
        uint4 year;
        uint4 mileage;
        boolean automatic;
        boolean ac;
        uint4 price;
        char<3> state;
        string description;
         
        kdtree <year, mileage, color, model, vendor, automatic, ac, price> index;
    };

假设我们用以下的 Car 对象来填充数据库：

    ("Ford", "Mustang", "grey", 2005, 60000, true, true, 20000, "MT");
    ("Ford", "Explorer", "black", 2000, 80000, true, true, 15000, "MA");
    ("Toyota", "Corolla", "green", 2007, 100000, true, true, 12000, "CA");

精确匹配搜索

要执行KD 树搜索，与执行其他索引类型的搜索一样，首先必须创建一个游标。

然后，要搜索数据库中所有**“Ford Mustangs”，我们首先创建一个具有 vendor="Ford" 和 model="Mustang" 属性的 Car 对象。这个Car 类的搜索模式对象**将作为上下文传递给游标的搜索操作。搜索完成后，应用程序可以使用标准的游标操作 first、last、next 和 prev 遍历结果集。

请注意，结果集中对象的顺序是不可预测的，但仅返回符合指定搜索条件的对象。

范围搜索

范围查找与上述的精确匹配类似。在这种情况下，我们指定**“from”和“to”**的模式对象。

例如，我们可以创建具有 vendor="Ford" 和 Year=2000 的 FromCar 对象，以及具有 vendor="Ford" 和 Year=2006 的 ToCar 对象。将这两个“模式对象”传递给游标搜索操作，将找到 vendor="Ford" 的所有 Car 对象。

空间搜索

为了展示KD 树索引的另一种搜索能力，考虑以下模式：

    class SpatialObject 
    {
        Int4 left;
        Int4 top;
        int4 right;
        int4 bottom;
        int  type;
        …
        kdtree <left, top, right, bottom, type> index;
    };

再次，通过示例查询（QBE）方法，我们可以创建“模式对象”Low，其坐标为 left=LEFT，top=TOP，以及 High，其坐标为 right=RIGHT，bottom=BOTTOM。然后将 Low 和 High 传递给操作类型为 contains 的游标搜索，将选择位于指定矩形内的对象。

将操作类型指定为 overlaps 则会选择与指定矩形相交的对象。

请注意，KD 树索引本质上是不平衡的。虽然它们支持持久类，但由于不平衡，性能可能不是最优的，因此 KD 树索引对于临时（内存中）类最有用。