索引方法及装置

摘要

本发明公开了一种索引方法及装置。该方法包括：响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以面片编码为索引获取数据集合。通过本发明，解决了相关技术中在对空间对象进行查询时，查询效率低的问题。

权利要求

1.一种索引方法，其特征在于，包括：

响应框选指令，其中，所述框选指令用于指示在多维空间上框选出目标区域，所述多维空间包括多个层级的子空间；

查询目标面片的面片编码，其中，所述目标区域被所述目标面片完全覆盖，所述子空间包括一个层级内的多个面片，每个面片对应一个面片编码；

以所述面片编码为索引获取数据集合；

其中，在以所述面片编码为索引获取数据集合之后，所述方法还包括：判断待查询范围是否与所述目标区域有交集；

在判断出所述待查询范围与所述目标区域有交集的情况下，确定所述待查询范围对应的目标数值范围；

判断所述目标数值范围中的所有数据是否被所述数据集合所表示的数据范围全部包含；

在判断出所述目标数值范围中的所有数据未被所述数据集合所表示的数据范围全部包含的情况下，采用逻辑索引在所述数据集合所表示的数据范围进行查询。

2.根据权利要求1所述的方法，其特征在于，查询目标面片的面片编码包括：确定所述目标区域对应的最小外包矩形，其中，所述最小外包矩形是由所述目标区域生成的面状数据在横坐标方向上的最大值和最小值、以及所述面状数据在纵坐标方向上的最大值和最小值确定的矩形；

获取长度数值L，其中，所述长度数值L为所述最小外包矩形中横坐标方向或是纵坐标方向上的最大长度的数值；

选取长度大于所述长度数值L的最小的面片边长所对应的层级作为目标层级；

判断在所述目标层级中是否存在覆盖所述最小外包矩形的面片；

在判断出所述目标层级中存在覆盖所述最小外包矩形的面片的情况下，将所述覆盖所述最小外包矩形的面片的编码作为所述面片编码。

3.根据权利要求2所述的方法，其特征在于，在判断在所述目标层级中是否存在覆盖所述最小外包矩形的面片之后，所述方法还包括：在判断出所述目标层级中不存在包含所述最小外包矩形的面片的情况下，确定所述目标层级的上一层级；

在所述目标层级的上一层级中确定能够覆盖所述最小外包矩形的组合面片，其中，所述组合面片由至少一片面片组成；

将所述组合面片对应的编码作为所述目标面片的所述面片编码。

4.根据权利要求3所述的方法，其特征在于，在将所述组合面片对应的编码作为所述目标面片的所述面片编码之后，所述方法还包括：生成与数据文件同名的XML文件，其中，所述XML文件为逻辑索引文件，所述数据文件为存储所述面状数据的文件。

5.根据权利要求2所述的方法，其特征在于，在确定所述目标区域对应的最小外包矩形之后，且在获取所述长度数值L之前，所述方法还包括：按照四叉划分的方式将所述面状数据存入数据库，其中，所述数据库中存储以下信息中的至少之一：数据库中的唯一标识、文件名、剖分编码和所述最小外包矩形。

6.根据权利要求1所述的方法，其特征在于，采用逻辑索引在所述数据集合所表示的数据范围进行查询包括：确定所述面片编码对应的父编码；

获取包含所述父编码对应的各个数据的XML文件，得到XML文件集合；

判断在所述XML文件集合中是否存在包含所述面片编码的子编码的XML文件；

在存在包含所述面片编码的子编码的XML文件的情况下，查询所述XML文件对应的数据与所述数据集合所表示的数据范围是否有交集。

7.一种索引装置，其特征在于，包括：

响应单元，用于响应框选指令，其中，所述框选指令用于指示在多维空间上框选出目标区域，所述多维空间包括多个层级的子空间；

查询单元，用于查询目标面片的面片编码，其中，所述目标区域被所述目标面片完全覆盖，所述子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以及索引单元，用于以所述面片编码为索引获取数据集合；

其中，所述装置还用于：在以所述面片编码为索引获取数据集合之后，判断待查询范围是否与所述目标区域有交集；在判断出所述待查询范围与所述目标区域有交集的情况下，确定所述待查询范围对应的目标数值范围；判断所述目标数值范围中的所有数据是否被所述数据集合所表示的数据范围全部包含；在判断出所述目标数值范围中的所有数据未被所述数据集合所表示的数据范围全部包含的情况下，采用逻辑索引在所述数据集合所表示的数据范围进行查询。

8.根据权利要求7所述的装置，其特征在于，所述查询单元包括：第一确定模块，用于确定所述目标区域对应的最小外包矩形，其中，所述最小外包矩形是由所述目标区域生成的面状数据在横坐标方向上的最大值和最小值、以及所述面状数据在纵坐标方向上的最大值和最小值确定的矩形；

获取模块，用于获取长度数值L，其中，所述长度数值L为所述最小外包矩形中横坐标方向或是纵坐标方向上的最大长度的数值；

选取模块，用于选取长度大于所述长度数值L的最小的面片边长所对应的层级作为目标层级；

判断模块，用于判断在所述目标层级中是否存在覆盖所述最小外包矩形的面片；

第二确定模块，用于在判断出所述目标层级中存在覆盖所述最小外包矩形的面片的情况下，将所述覆盖所述最小外包矩形的面片的编码作为所述面片编码。

9.根据权利要求8所述的装置，其特征在于，所述装置还包括：第一确定单元，用于在判断出所述目标层级中不存在包含所述最小外包矩形的面片的情况下，确定所述目标层级的上一层级；

第二确定单元，用于在所述目标层级的上一层级中确定能够覆盖所述最小外包矩形的组合面片，其中，所述组合面片由至少一片面片组成；

第三确定单元，用于将所述组合面片对应的编码作为所述目标面片的所述面片编码。

说明书

索引方法及装置

技术领域

[0001] 本发明涉及空间索引技术领域，具体而言，涉及一种索引方法及装置。

背景技术

[0002] 目前，在已有的各类空间索引结构中，格网索引是一类常见的规则索引形式，但是其采取单一尺度的索引方式，在面对尺度差异较大的空间对象的情况时，查询效率较低；而四叉树索引和其相关的混合索引是另一类常见的索引形式，常用的线性四叉树索引结构在对空间进行编码的时候，其编码的空间连续性较差，在对尺度差异较大的空间对象进行查询时，查询效率会受到影响，因此，相关技术中在对空间对象进行查询时，查询效率较低。

[0003] 针对相关技术中在对空间对象进行查询时，查询效率低的问题，目前尚未提出有效的解决方案。

发明内容

[0004] 本发明的主要目的在于提供一种索引方法及装置，以解决相关技术中在对空间对象进行查询时，查询效率低的问题。

[0005] 为了实现上述目的，根据本发明的一个方面，提供了一种索引方法。该方法包括：响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以面片编码为索引获取数据集合。

[0006] 进一步地，查询目标面片的面片编码包括：确定目标区域对应的最小外包矩形，其中，最小外包矩形是由目标区域生成的面状数据在横坐标方向上的最大值和最小值、以及面状数据在纵坐标方向上的最大值和最小值确定的矩形；获取长度数值L，其中，长度数值L为最小外包矩形中横坐标方向或是纵坐标方向上的最大长度的数值；选取长度大于长度数值L的最小的面片边长所对应的层级作为目标层级；判断在目标层级中是否存在覆盖最小外包矩形的面片；在判断出目标层级中存在覆盖最小外包矩形的面片的情况下，将覆盖最小外包矩形的面片的编码作为面片编码。

[0007] 进一步地，在判断在目标层级中是否存在覆盖最小外包矩形的面片之后，该方法还包括：在判断出目标层级中不存在包含最小外包矩形的面片的情况下，确定目标层级的上一层级；在目标层级的上一层级中确定能够覆盖最小外包矩形的组合面片，其中，组合面片由至少一片面片组成；将组合面片对应的编码作为目标面片的面片编码。

[0008] 进一步地，在将组合面片对应的编码作为目标面片的面片编码之后，该方法还包括：生成与数据文件同名的XML文件，其中，XML文件为逻辑索引文件，数据文件为存储面状数据的文件。

[0009] 进一步地，在确定目标区域对应的最小外包矩形之后，且在获取长度数值L之前，该方法还包括：按照四叉划分的方式将面状数据存入数据库，其中，数据库中存储以下信息中的至少之一：数据库中的唯一标识、文件名、剖分编码和最小外包矩形。

[0010] 进一步地，在以面片编码为索引获取数据集合之后，该方法还包括：判断待查询范围是否与目标区域有交集；在判断出待查询范围与目标区域有交集的情况下，确定待查询范围对应的目标数值范围；判断目标数值范围中的所有数据是否被数据集合所表示的数据范围全部包含；在判断出目标数值范围中的所有数据未被数据集合所表示的数据范围全部包含的情况下，采用逻辑索引在数据集合所表示的数据范围进行查询。

[0011] 进一步地，采用逻辑索引在数据集合所表示的数据范围进行查询包括：确定面片编码对应的父编码；获取包含父编码对应的各个数据的XML文件，得到XML文件集合；判断在XML文件集合中是否存在包含面片编码的子编码的XML文件；在存在包含面片编码的子编码的XML文件的情况下，查询XML文件对应的数据与数据集合所表示的数据范围是否有交集。

[0012] 为了实现上述目的，根据本发明的另一方面，提供了一种索引装置。该装置包括：响应单元，用于响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询单元，用于查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以及索引单元，用于以面片编码为索引获取数据集合。

[0013] 进一步地，查询单元包括：第一确定模块，用于确定目标区域对应的最小外包矩形，其中，最小外包矩形是由目标区域生成的面状数据在横坐标方向上的最大值和最小值、以及面状数据在纵坐标方向上的最大值和最小值确定的矩形；获取模块，用于获取长度数值L，其中，长度数值L为最小外包矩形中横坐标方向或是纵坐标方向上的最大长度的数值；选取模块，用于选取长度大于长度数值L的最小的面片边长所对应的层级作为目标层级；判断模块，用于判断在目标层级中是否存在覆盖最小外包矩形的面片；第二确定模块，用于在判断出目标层级中存在覆盖最小外包矩形的面片的情况下，将覆盖最小外包矩形的面片的编码作为面片编码。

[0014] 进一步地，该装置还包括：第一确定单元，用于在判断出目标层级中不存在包含最小外包矩形的面片的情况下，确定目标层级的上一层级；第二确定单元，用于在目标层级的上一层级中确定能够覆盖最小外包矩形的组合面片，其中，组合面片由至少一片面片组成；第三确定单元，用于将组合面片对应的编码作为目标面片的面片编码。

[0015] 通过本发明，采用以下步骤：响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以面片编码为索引获取数据集合。由于面片编码是多尺度编码，也即本索引所采取的多尺度编码方式。通过多尺度的编码方式，实现了每一个较低层级面片的编码均为其所对应的高层级面片的均值这一特征，保证了能够根据一个面片的编码直接确定出其较高层次的所有子面片的编码所在范围，因而在查询的时候能够实现不同尺度统一查询；同时，由于这种特性，该编码和其所有子编码的数值之间不存在其它编码，因而查询的数值上的区域范围是连续的，因此查询效率更高。即解决了相关技术中在对空间对象进行查询时，查询效率低的问题。进而达到了提高编码的空间连续性，从而提高了对空间对象的查询效率的效果。

附图说明

[0016] 构成本申请的一部分的附图用来提供对本发明的进一步理解，本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：

[0017] 图1是根据本发明实施例的索引方法的流程图；

[0018] 图2是根据本发明实施例的索引方法中N＝2时的对应方式的示意图；

[0019] 图3是根据本发明实施例的索引方法中一维的对应方式的示意图；

[0020] 图4是根据本发明实施例的索引方法中N＝3时h函数处理后的对应结果的示意图；以及

[0021] 图5是根据本发明实施例的索引装置的示意图。

具体实施方式

[0022] 需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。下面将参考附图并结合实施例来详细说明本发明。

[0023] 为了使本技术领域的人员更好地理解本申请方案，下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本申请一部分的实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都应当属于本申请保护的范围。

[0024] 需要说明的是，本申请的说明书和权利要求书及上述附图中的术语“第一”、“第二”等是用于区别类似的对象，而不必用于描述特定的顺序或先后次序。应该理解这样使用的数据在适当情况下可以互换，以便这里描述的本申请的实施例。此外，术语“包括”和“具有”以及他们的任何变形，意图在于覆盖不排他的包含，例如，包含了一系列步骤或单元的过程、方法、系统、产品或设备不必限于清楚地列出的那些步骤或单元，而是可包括没有清楚地列出的或对于这些过程、方法、产品或设备固有的其它步骤或单元。

[0025] 为了便于描述，以下对本申请实施例涉及的部分名词或术语进行说明：

[0026] XML是可扩展标记语言(Extensible Markup Language，XML)缩写，用于标记电子文件使其具有结构性的标记语言，可以用来标记数据、定义数据类型，是一种允许用户对自己的标记语言进行定义的源语言。XML是标准通用标记语言(SGML)的子集，非常适合Web传输。XML提供统一的方法来描述和交换独立于应用程序或供应商的结构化数据。XML文件一般用用记事本或都是IE都可以打开。

[0027] 根据本发明的实施例，提供了一种索引方法。

[0028] 图1是根据本发明实施例的索引方法的流程图。如图1所示，该方法包括以下步骤：

[0029] 步骤S101，响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间。

[0030] 接收到外部传入的用于指示在多维空间上框选目标区域的框选指令，并执行该框选指令，在多维空间上框选出目标区域。其中，多维空间包括多个层级的子空间，每个子空间对应多个数据编码。在本发明中涉及的多维空间为二维空间。三维空间也通用，在此不作限定。

[0031] 步骤S102，查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码。

[0032] 需要说明的是，本申请中涉及到的目标面片可以为一个面片或多个面片，一般情况下，覆盖目标区域时由多个面片覆盖，在本申请中，将多个覆盖目标区域的面片统称为目标面片，每个面片对应一个面片编码。因此，查询目标面片的面片编码，查询出多个面片编码。

[0033] 本发明实施例提供的索引方法采用的划分方式：对整个二维的研究空间(定义为0级空间)进行四叉划分，将空间等分成四个相同的子空间，再将每个子空间继续划分为四个相同的更高级别的子空间，如此递归下去，直到达到规定的最高层级N-1级，共N级。这样递归划分的空间集合具有横向、纵向、尺度向三个维度，能够作为空间索引的基本架构。假设整体空间范围是L*L，此时0级索引面片所对应的空间范围是L*L，1级索引面片对应L/2*L/2，2级索引面片对应L/4*L/4……k级索引面片对应L/(2^k)*L/(2^k)；因而在0级索引中共有1*1个面片，在1级索引中共有2*2个面片,在2级索引中共有4*4个面片……在k级索引中共有2^k-1*2^k-1个面片。

[0034] 可选地，在本发明实施例提供的索引方法中，查询目标面片的面片编码包括：确定目标区域对应的最小外包矩形，其中，最小外包矩形是由目标区域生成的面状数据在横坐标方向上的最大值和最小值、以及面状数据在纵坐标方向上的最大值和最小值确定的矩形；获取长度数值L，其中，长度数值L为最小外包矩形中横坐标方向或是纵坐标方向上的最大长度的数值；选取长度大于长度数值L的最小的面片边长所对应的层级作为目标层级；判断在目标层级中是否存在覆盖最小外包矩形的面片；在判断出目标层级中存在覆盖最小外包矩形的面片的情况下，将覆盖最小外包矩形的面片的编码作为面片编码。

[0035] 可选地，在本发明实施例提供的索引方法中，在判断在编码层级中是否存在包含最小外包矩形的目标面片之后，该方法还包括：在判断出目标层级中不存在包含最小外包矩形的面片的情况下，确定目标层级的上一层级；在目标层级的上一层级中确定能够覆盖最小外包矩形的组合面片，其中，组合面片由至少一片面片组成；将组合面片对应的编码作为目标面片的面片编码。

[0036] 可选地，在本发明实施例提供的索引方法中，在将组合面片对应的编码作为目标面片的面片编码之后，该方法还包括：生成与数据文件同名的XML文件，其中，XML文件为逻辑索引文件，数据文件为存储面状数据的文件。

[0037] 可选地，在本发明实施例提供的索引方法中，在确定目标区域对应的最小外包矩形之后，且在获取长度数值L之前，该方法还包括：按照四叉划分的方式将面状数据存入数据库，其中，数据库中存储以下信息中的至少之一：数据库中的唯一标识、文件名、剖分编码和最小外包矩形。对应编码是指该数据集合所表示的数据范围所对应的剖分编码。

[0038] 具体地，在本发明实施例提供的索引方法中，首先将目标区域生成的面状数据的最小外包矩形(简称MBR)，即空间对象在x、y两个方向上的最大值和最小值，也即：Xmin、Ymin、Xmax和Ymax，然后按照四分划分的方式将面状数据存入数据库中，数据库中记录：1、id，2、文件名，3、对应编码，4、最小外包(根据面积占优的方式判断一个面状数据存几条数据，可以是1、2、4)；数据在存放时的面积占优策略说明：获得MBR在x方向或是y方向上的最大长度L，即Lm＝max(abs(Xmax-Xmin),ab s(Ymax-Ymin))，然后选取长度小于L的最大的网格边长所对应的层级作为编码层级，如果该MBR整个处于某单一面片内部，则选取该单一面片的编码做索引，如果不处于单一面片内部，则选取更高一层级的两个或者四个面片来完全覆盖该MBR，然后将这两个或者四个面片所对应点编码作为索引。同时，生成面状数据的同名XML文件，XML文件为逻辑索引文件，例如，成面状数据的数据文件是name.jpg，那么逻辑索引文件就是name.xml，逻辑索引文件内部包含多个较高层级的子编码。其形式如下所示：

[0039]

[0040] 步骤S103，以面片编码为索引获取数据集合。

[0041] 需要说明的是，本申请中提及的数据集合指的是框选出目标区域对应的数据范围。以面片编码为索引获取数据集合，可以首先确定面片编码的层级，设面片编码＝p*4^n，其中p％4！＝0，则n为层级。那么面片编码对应的数据集合即为((p-1)*4^n，(p+1)*4^n)。

[0042] 需要说明的是，在本发明实施例提供的索引方法中涉及到的基本关系简单介绍如下：i层上相邻编码的数值间隔：ΔTi＝2*4^(N-i-1)，i层上的第一个编码：OTi＝4^(N-i-1)；i层上的第k个编码：KTi＝OTi+ΔTi*(k-1)＝(2k+2)*4^(N-i-1)；层级的计算：对于一个编码，根据其相应的二进制形式来查看末位的0的个数，如果有2*i个0，那么该编码所对应的层级即为N-i-1级，例如编码7＝(111)2对应N-1级；编码16＝(10000)2对应N-3级，需要注意的是，末尾的连续0的个数一定是偶数个，不可能有奇数个0，即例如8＝(1000)2这样的数字是不符合编码规则的。多尺度编码所对应的上下界范围：根据这个上下界范围可以直接确定出该编码所对应的所有子编码的数值范围，查询的时候可以用到。code所对应的范围是：(code-4^(N-i-1)，code+4^(N-i-1))，其中i是code所对应的层级。多尺度编码所对应的子编码：给定多尺度编码MTc(整数)，对应的层级为i，计算其包含的第i’层的时间码ST，i’≥i(多尺度整数编码在整数排序上，满足包含关系)的算法如下公式1所示：

[0043]

[0044] 多尺度编码所对应的父编码：给定多尺度编码MTc(整数)，对应的层级为i，计算其包含的第i’层的码ST，i’≤i(多尺度整数编码在整数排序上，满足时间被包含关系)的算法如下公式2所示：

[0045]

[0046] 需要说明的是，是先移位再确定最后一位改零。

[0047] 编码邻域计算：给定多尺度编码c(整数)，计算K个整数单位(当前层级i)前(后)的编码c’，c’＝c±K*ΔTi

[0048] 编码方式：首先，设f(x，y，n)是空间填充曲线在二维的对应情况。函数的参数含义：n表示覆盖的2n*2n的全部范围(n取0，1，2，……)；x，y表示第在这种情况中第x行第y列的点。示例如图2和图3所示，图2中即为n＝2时的对应方式。图3为一维的对应方式。其次，采取全覆盖方式，保证上一层级的编码是下一层级所有编码的均值，对多层级的区域按照统一格式编码。h函数是对f函数进行了代数变换如公式3所示：

[0049] h(x,y,n,N)＝(2*f(x,y,n)+1)*4N-n-1公式3

[0050] 图4是N＝3时h函数处理后的对应结果。

[0051] 可选地，在本发明实施例提供的索引方法中，在以面片编码为索引获取数据集合之后，该方法还包括：判断待查询范围是否与目标区域有交集；在判断出待查询范围与目标区域有交集的情况下，确定待查询范围对应的目标数值范围；判断目标数值范围中的所有数据是否被数据集合所表示的数据范围全部包含；在判断出目标数值范围中的所有数据未被数据集合所表示的数据范围全部包含的情况下，采用逻辑索引在数据集合所表示的数据范围进行查询。

[0052] 可选地，在本发明实施例提供的索引方法中，采用逻辑索引在数据集合所表示的数据范围进行查询包括：确定面片编码对应的父编码；获取包含父编码对应的各个数据的XML文件，得到XML文件集合；判断在XML文件集合中是否存在包含面片编码的子编码的XML文件；在存在包含面片编码的子编码的XML文件的情况下，查询XML文件对应的数据与数据集合所表示的数据范围是否有交集。

[0053] 具体地，找到在数据集合内该面片编码对应的所有子编码{A’}，则这些子编码所对应的数据即为被框选编码所完全包含的数据。同时，如果待查询范围与目标区域有交集而并不是被其完全包含的数据，则需要用到逻辑索引。具体的：首先找面片编码的若干个层级的父编码(假设为三层)，例如，19的三个层级的父编码为20，16，64。然后，找出这些父编码所对应的各条数据的XML文件，查询XML文件中是否有能包含{A’}的，如果有的话，查询这条数据和框选范围(目标区域)是否有交集，如果有交集，返回查询结果。

[0054] 由于获取到多个面片编码(假设都是整数)，例如：1、2、3、4、5、6、7、8、10、11、12、13、14、15，然后将查询数据库中编码与上述面片编码有对应的部分，则只需比对1<＝code<＝8or 10<＝code<＝15的部分(分两段，连续性较高)。在查询的时候连续性较高的方法在数据库中查询的快，因此提高了查询效率。

[0055] 综上所述，通过多尺度的编码方式，实现了“每一个较低层级面片的编码均为其所对应的高层级面片的均值”这一特征，保证了能够根据一个面片的编码直接确定出其较高层次的所有子面片的编码所在范围，因而在查询的时候能够实现不同尺度统一查询；同时，由于这种特性，该编码和其所有子编码的数值之间不存在其他编码，因而查询的数值上的区域范围是连续的，效率更高。例如对于图2中编号为16的面片，其所有子面片的对应范围是(0，32)，而这一范围内并不包含其它的任何面片，因而当需要查询该面片及其所有子面片所对应的空间对象时，可以直接搜索索引值在0到32之间的对象即可。同一层级内部的编码方式不同，比如可以是Hilbert曲线编码方式。已经从理论上说明了在各类查询不同尺度的查询方式中，本发明实施例提供的索引方法的编码方式的连续性更强，查询效率会大幅提高。

[0056] 本发明实施例提供的索引方法，通过响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以面片编码为索引获取数据集合。由于面片编码是多尺度编码，也即本索引所采取的多尺度编码方式。通过多尺度的编码方式，实现了每一个较低层级面片的编码均为其所对应的高层级面片的均值这一特征，保证了能够根据一个面片的编码直接确定出其较高层次的所有子面片的编码所在范围，因而在查询的时候能够实现不同尺度统一查询；同时，由于这种特性，该编码和其所有子编码的数值之间不存在其它编码，因而查询的数值上的区域范围是连续的，因此查询效率更高。即解决了相关技术中在对空间对象进行查询时，查询效率低的问题。进而达到了提高编码的空间连续性，从而提高了对空间对象的查询效率的效果。

[0057] 需要说明的是，在附图的流程图示出的步骤可以在诸如一组计算机可执行指令的计算机系统中执行，并且，虽然在流程图中示出了逻辑顺序，但是在某些情况下，可以以不同于此处的顺序执行所示出或描述的步骤。

[0058] 本发明实施例还提供了一种索引装置，需要说明的是，本发明实施例的索引装置可以用于执行本发明实施例所提供的用于索引方法。以下对本发明实施例提供的索引装置进行介绍。

[0059] 图5是根据本发明实施例的索引装置的示意图。如图5所示，该装置包括：响应单元10、查询单元20和索引单元30。

[0060] 具体地，响应单元10，用于响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间。

[0061] 查询单元20，用于查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码。

[0062] 索引单元30，用于以面片编码为索引获取数据集合。

[0063] 本发明实施例的索引装置，通过响应单元10响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询单元20查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以及索引单元30以面片编码为索引获取数据集合。由于面片编码是多尺度编码，也即本索引所采取的多尺度编码方式。通过多尺度的编码方式，实现了每一个较低层级面片的编码均为其所对应的高层级面片的均值这一特征，保证了能够根据一个面片的编码直接确定出其较高层次的所有子面片的编码所在范围，因而在查询的时候能够实现不同尺度统一查询；同时，由于这种特性，该编码和其所有子编码的数值之间不存在其它编码，因而查询的数值上的区域范围是连续的，因此查询效率更高。即解决了相关技术中在对空间对象进行查询时，查询效率低的问题。进而达到了提高编码的空间连续性，从而提高了对空间对象的查询效率的效果。

[0064] 可选地，在本发明实施例提供的索引装置中，该查询单元20包括：第一确定模块，用于确定目标区域对应的最小外包矩形，其中，最小外包矩形是由目标区域生成的面状数据在横坐标方向上的最大值和最小值、以及面状数据在纵坐标方向上的最大值和最小值确定的矩形；获取模块，用于获取长度数值L，其中，长度数值L为最小外包矩形中横坐标方向或是纵坐标方向上的最大长度的数值；选取模块，用于选取长度大于长度数值L的最小的面片边长所对应的层级作为目标层级；判断模块，用于判断在目标层级中是否存在覆盖最小外包矩形的面片；第二确定模块，用于在判断出目标层级中存在覆盖最小外包矩形的面片的情况下，将覆盖最小外包矩形的面片的编码作为面片编码。

[0065] 可选地，在本发明实施例提供的索引装置中，该装置还包括：第一确定单元，用于在判断出目标层级中不存在包含最小外包矩形的面片的情况下，确定目标层级的上一层级；第二确定单元，用于在目标层级的上一层级中确定能够覆盖最小外包矩形的组合面片，其中，组合面片由至少一片面片组成；第三确定单元，用于将组合面片对应的编码作为目标面片的面片编码。

[0066] 所述索引装置包括处理器和存储器，上述响应单元10、查询单元20和索引单元30等均作为程序单元存储在存储器中，由处理器执行存储在存储器中的上述程序单元实现相应功能。

[0067] 处理器中包含内核，由内核去存储器中调取相应的程序单元。内核可以设置一个或以上，通过调整内核参数进行索引。

[0068] 存储器可能包括计算机可读介质中的非永久性存储器，随机存取存储器(RAM)和/或非易失性内存等形式，如只读存储器(ROM)或闪存(flash RAM)，存储器包括至少一个存储芯片。

[0069] 本申请还提供了一种计算机程序产品的实施例，当在数据处理设备上执行时，适于执行初始化有如下方法步骤的程序代码：响应框选指令，其中，框选指令用于指示在多维空间上框选出目标区域，多维空间包括多个层级的子空间；查询目标面片的面片编码，其中，目标区域被目标面片完全覆盖，子空间包括一个层级内的多个面片，每个面片对应一个面片编码；以面片编码为索引获取数据集合。

[0070] 需要说明的是，对于前述的各方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本申请并不受所描述的动作顺序的限制，因为依据本申请，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和模块并不一定是本申请所必须的。

[0071] 在上述实施例中，对各个实施例的描述都各有侧重，某个实施例中没有详述的部分，可以参见其他实施例的相关描述。

[0072] 在本申请所提供的几个实施例中，应该理解到，所揭露的装置，可通过其它的方式实现。例如，以上所描述的装置实施例仅仅是示意性的，例如所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，例如多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。

[0073] 所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施例方案的目的。

[0074] 另外，在本申请各个实施例中的各功能单元可以集成在一个处理单元中，也可以是各个单元单独物理存在，也可以两个或两个以上单元集成在一个单元中。上述集成的单元既可以采用硬件的形式实现，也可以采用软件功能单元的形式实现。

[0075] 显然，本领域的技术人员应该明白，上述的本申请的各模块或各步骤可以用通用的计算装置来实现，它们可以集中在单个的计算装置上，或者分布在多个计算装置所组成的网络上，可选地，它们可以用计算装置可执行的程序代码来实现，从而，可以将它们存储在存储装置中由计算装置来执行，或者将它们分别制作成各个集成电路模块，或者将它们中的多个模块或步骤制作成单个集成电路模块来实现。这样，本申请不限制于任何特定的硬件和软件结合。

[0076] 以上所述仅为本申请的优选实施例，并不用于限制本申请，对于本领域的技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。