一种能够实现高效更新和查询的空间数据管理方法

1.本发明涉及区块链领域，具体涉及一种能够实现高效更新和查询的空间数据管理方法。


背景技术：

2.随着智能设备的普及，使得越来越多的产品本身能够执行复杂的智能任务，比如智能汽车的广泛出现。另一方面，随着第五代通信技术的突破与大规模部署，使得万物互联也成为了触手可及的事情。在这样的时代背景下，智能产品间的自主协同开始进入研究者的视野中。在这些智能产品间自主协同的研究场景中，可以预见的一个重要的需求就是对空间数据的高效处理与应用。以智能汽车的自主协同为例，车辆之间共享各自的空间位置，同时汇报各种事件的发生地点。当该智能汽车协同集群中收到一个任务，需要前往特定的地点接送乘客，集群需要快速地调度最近的单位完成任务。在这样一个情境下，需要集群：1)能够可信的在集群的车辆间分享数据；2)能够高效地对空间数据进行索引并提供高效的空间查询能力；3)能够高效对位置信息进行更新。
3.区块链作为一种安全可信，不易篡改的去中心化技术，在近年来受到各界的关注。区块链可以保证节点之间在不可信任的网络环境下实现的安全和透明的信息交换而不需要可信的第三方。同时区块链使用哈希链的块链式结构，更准确地说是一个链接的块列表，每一个块包含上一个块的哈希值。区块链的块链式结构保证了区块链上数据的难以篡改。同时区块链上的默克尔树的结构为区块链上的数据提供了可信证明。在一些研究中，研究人员已经将区块链应用于保障车辆间的可信数据共享。
4.传统的区块链能够解决数据的可信共享，但是不能很好的支持空间查询高效地空间数据的索引的更新。因此需要针对区块链的场景打造一个高效的，低成本的可验证空间数据结构来管理空间数据。


技术实现要素：

5.本发明针对传统区块链上可验证数据结构在空间数据管理能力上的不足，结合了默克尔树和r树的综合优势，提供了可验证的空间数据管理方法；利用不同粒度分层网格的划分，提高了对空间数据的更新效率；通过空间范围查询范围任务细分和整合，保证了高效的空间范围查询效率。
6.本发明的目的是通过如下技术方案实现的：
7.一种能够实现高效更新和查询的空间数据管理方法，
8.所述空间数据为多层的数据结构，数据结构的每一层都是对整个空间范围进行不同细粒度的划分而形成的网格；低层级的网格的细粒度小于高层级的网格的细粒度；在每一个网格中，所述数据结构都维护着一棵用以管理空间数据的默克尔r树，所有的数据更新都优先发生在最小粒度的网格维护的默克尔r树中；
9.空间数据管理包括新空间数据插入、原空间数据删除、空间数据更新和空间范围
查询；
10.所述新空间数据插入具体为：确定要插入的新空间数据应该插入的最低层级的网格，然后将空间数据插入到该最低层级的网格维护的默克尔r树中；
11.所述原空间数据删除具体为：确定要删除的原空间数据所在的网格，在该网格所维护的默克尔r树中搜索要删除的空间数据，为其设置删除标志实现删除；
12.所述空间数据更新具体为：首先对原空间数据执行删除操作，然后对新空间数据执行插入操作；
13.所述空间范围查询具体为：将空间范围查询任务细分到不同层，对每一层进行空间范围查询，并整合每一层的查询结果，组成所述空间范围查询任务的可验证查询结果。
14.进一步地，其特征在于，新空间数据插入时，通过新空间数据在上层网格中的相对位置关系，计算得到所述新空间数据所在的下层网格，并根据新空间数据所在下层网格中的相对位置计算得到新空间数据所在的更下层网格，直到找到新空间数据所在的最低层级的网格，将所述新空间数据插入到默克尔r树中。
15.进一步地，将新空间数据插入到默克尔r树中时，若存在已删除的空间数据，则替换它；插入后，若默克尔r树的大小超过设置的上限，则需要将该默克尔r树合并到上层中去。
16.进一步地，当网格中默克尔r树的大小超过指定的上限时，需要向上一层合并；合并时通过在上一层的默克尔r树中找到与待合并的默克尔r树相同高度的子树，将待合并的默克尔r树与找到的默克尔r树的子树进行展开，并丢弃被标记为删除的空间数据，之后将所有的空间数据重新组织成一个默克尔r树并插入到上一层的默克尔r树中。
17.进一步地，相邻的两个层级的网格中，高一层级网格中默克尔r树的大小上限设定为相邻的低一层级网格中默克尔r树的大小上限的整数倍。
18.进一步地，确定要删除的原空间数据所在的网格时，通过原空间数据在上层网格中的相对位置关系，可以计算得到所述原空间数据所在的下一层网格，并可根据空间数据所在下一层网格中的相对位置计算得到原空间数据所在的更下一层网格，直到找到空间数据存在的网格，在该网格的默克尔r树中进行搜索并找到该原空间数据，通过将该原空间数据所在叶子节点的设置为删除来进行删除。
19.进一步地，进行空间范围查询时，将空间查询的范围与每一层的网格进行相交判定，对每一层中所有相交的网格中的默克尔r树进行空间范围查询并生成可验证的子查询结果；将所述子查询结果收集并形成针对空间范围查询的完整的可验证查询结果。
20.本发明的有益效果如下：
21.本发明的能够实现高效更新和查询的空间数据管理方法，充分结合默克尔树和r树的综合优势，通过默克尔树的性质提供了可验证的查询能力；通过r树的性质提供了高效的空间数据管理方法；本发明利用不同粒度分层网格的划分，提高了对空间数据的更新效率；通过空间范围查询范围任务细分和整合，保证了高效的空间范围查询效率，为区块链在未来自能设备的自主协同场景中的应用打下了一个坚实的基础。
附图说明
22.图1为本发明实施例的能够实现高效更新和查询的空间数据管理方法的流程图。
具体实施方式
23.下面根据附图和优选实施例详细描述本发明，本发明的目的和效果将变得更加明白，应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。
24.如图1所示，本发明实施例的能够实现高效更新和查询的空间数据管理方法，空间数据为多层的数据结构，数据结构的每一层都是对整个空间范围进行不同细粒度的划分而形成的网格，不同粒度的网格之间连接进行多层的结构。低层级的网格的细粒度小于高层级的网格的细粒度，低层级的网格可以视为对高层级网格所表示空间范围的进一步划分；在每一个网格中，所述数据结构都维护着一棵用以管理空间数据的默克尔r树，所有的数据插入都优先发生在最小粒度的网格维护的默克尔r树中。对于任意空间数据，有且只有一份数据存在于某一层级网格所管理的默克尔r树中。
25.随着网格中管理的默克尔r树的大小的逐渐增大，较低层级网格中的默克尔r树会被高效的合并到上层网格的默克尔r树中。
26.默克尔r树是将默克尔树与r树相结合，通过r树的方式来管理空间数据，并使用默克尔树的方式提供可验证的空间查询。默克尔r树设有中间节点和叶子节点，中间节点的字段包含第一哈希值、第一范围数据、第一数组。第一哈希值由中间节点的所有子节点共同获得；第一范围则是中间节点所表示的最小边界矩形的范围；第一数组包含了中间节点的所有孩子节点。叶子节点的字段包括第二哈希值、第二范围数据、第一搜索键、第一指针和第一标志。第二哈希值由叶子节点的所有子节点共同获得，第二范围则是叶子节点所表示的最小边界矩形的范围，第一搜索键是该叶子节点表示资源的搜索键值，第一指针包含了叶子节点的资源节点，第一标志表示叶子节点的状态。
27.空间数据管理包括新空间数据插入、原空间数据删除、空间数据更新和空间范围查询。
28.其中，新空间数据插入具体为：确定要插入的新空间数据应该插入的最低层级的网格，然后将空间数据插入到该最低层级的网格维护的默克尔r树中。
29.示例性地，确定要插入的新空间数据应该插入的最低层级的网格时，从最高层级的网格开始，按照该层级网格的划分规则，可以计算得到新空间数据在该层级的所有网格中所应该位于的网格，通过进一步计算新空间数据在上层网格中的相对位置关系，计算得到所述新空间数据所在的下层网格，并根据新空间数据所在下层网格中的相对位置计算得到新空间数据所在的更下层网格，直到找到新空间数据所在的最低层级的网格，将所述新空间数据插入到该计算得到的网格的默克尔r树中。插入时，若在目标叶子节点中存在已删除的空间数据，则替换它，若不存在则直接插入。插入后若默克尔r树的大小超过设置的上限，则需要将该默克尔r树合并到上层中去。
30.当网格中默克尔r树的大小超过指定的上限时，需要向上一层合并；合并前需要通过计算默克尔r树所在网格在整个空间区域的相对位置来计算得到上一层级的所有网格中需要合并的网格；合并时，将当前默克尔r树视作一个具有一定高度的空间数据，插入到上一层级的网格中的默克尔r树中；在插入过程中，找到与待合并的默克尔r树相同高度的子树且两棵默克尔r树表示最小边界矩形的重叠面积最大，将待合并的默克尔r树与找到的默克尔r树的子树进行展开，收集两棵默克尔r树的所有空间数据，并丢弃被标记为删除的空间数据，之后将收集到的所有空间数据进行排序，并按照默克尔r树的节点的组织的模式，
迭代地将所有的空间数据重新组织成一个默克尔r树，并根据重新组织的默克尔r树的高度插入到上一层的默克尔r树中。
31.因此，相邻的两个层级的网格中，高一层级网格中默克尔r树的大小上限设定为相邻的低一层级网格中默克尔r树的大小上限的整数倍。
32.原空间数据删除具体为：确定要删除的原空间数据所在的网格，在该网格所维护的默克尔r树中搜索要删除的空间数据，为其设置删除标志实现删除。
33.示例性地，确定要删除的原空间数据所在的网格的方式和前面确定要插入的新空间数据应该插入的最低层级的网格的方式相同，即，从最高层级的网格开始，按照该层级网格的划分规则，可以计算得到新空间数据在该层级的所有网格中所应该位于的网格，通过进一步计算原空间数据在上层网格中的相对位置关系，可以计算得到所述原空间数据所在的下一层网格，并可根据空间数据所在下一层网格中的相对位置计算得到原空间数据所在的更下一层网格，直到找到空间数据存在的网格，在该网格的默克尔r树中进行搜索并找到该原空间数据所在的叶子节点，通过将该原空间数据所在叶子节点中的该原空间数据设置为删除来进行删除。
34.空间数据更新具体为：首先确定原空间数据所在的网格，然后在该网格中维护的默克尔r树中搜索要删除的空间数据，为其设置删除标志实现删除；然后对于要插入的新空间数据，确定新空间数据应该插入的最低层级的网格，然后将空间数据插入到该最低层级的网格维护的默克尔r树中。即更新操作为首先对原空间数据执行删除操作，然后对新空间数据执行插入操作。
35.当网格中的默克尔r树的大小达到设置的上限时，将大小超出上限的默克尔r树合并到上一层的网格中，如果上一层网格的默克尔r树因为合并也达到了大小的上限，也会继续合并到更上一层的网格中。
36.空间范围查询具体为：将空间范围查询任务细分到不同层，对每一层进行空间范围查询，并整合每一层的查询结果，组成空间范围查询任务的可验证查询结果。
37.进行空间范围查询时，将空间查询的范围与每一层的网格进行相交判定，对每一层中所有相交的网格中的默克尔r树进行空间范围查询并生成可验证的子查询结果；将子查询结果收集并形成针对空间范围查询的完整的可验证查询结果。
38.本领域普通技术人员可以理解，以上所述仅为发明的优选实例而已，并不用于限制发明，尽管参照前述实例对发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在发明的精神和原则之内，所做的修改、等同替换等均应包含在发明的保护范围之内。

技术特征：
1.一种能够实现高效更新和查询的空间数据管理方法，其特征在于，所述空间数据为多层的数据结构，数据结构的每一层都是对整个空间范围进行不同细粒度的划分而形成的网格；低层级的网格的细粒度小于高层级的网格的细粒度；在每一个网格中，所述数据结构都维护着一棵用以管理空间数据的默克尔r树，所有的数据更新都优先发生在最小粒度的网格维护的默克尔r树中；空间数据管理包括新空间数据插入、原空间数据删除、空间数据更新和空间范围查询；所述新空间数据插入具体为：确定要插入的新空间数据应该插入的最低层级的网格，然后将空间数据插入到该最低层级的网格维护的默克尔r树中；所述原空间数据删除具体为：确定要删除的原空间数据所在的网格，在该网格所维护的默克尔r树中搜索要删除的空间数据，为其设置删除标志实现删除；所述空间数据更新具体为：首先对原空间数据执行删除操作，然后对新空间数据执行插入操作；所述空间范围查询具体为：将空间范围查询任务细分到不同层，对每一层进行空间范围查询，并整合每一层的查询结果，组成所述空间范围查询任务的可验证查询结果。2.根据权利要求1所述的能够实现高效更新和查询的空间数据管理方法，其特征在于，新空间数据插入时，通过新空间数据在上层网格中的相对位置关系，计算得到所述新空间数据所在的下层网格，并根据新空间数据所在下层网格中的相对位置计算得到新空间数据所在的更下层网格，直到找到新空间数据所在的最低层级的网格，将所述新空间数据插入到默克尔r树中。3.根据权利要求2所述的能够实现高效更新和查询的空间数据管理方法，其特征在于，将新空间数据插入到默克尔r树中时，若存在已删除的空间数据，则替换它；插入后，若默克尔r树的大小超过设置的上限，则需要将该默克尔r树合并到上层中去。4.根据权利要求3所述的能够实现高效更新和查询的空间数据管理方法，其特征在于，当网格中默克尔r树的大小超过指定的上限时，需要向上一层合并；合并时通过在上一层的默克尔r树中找到与待合并的默克尔r树相同高度的子树，将待合并的默克尔r树与找到的默克尔r树的子树进行展开，并丢弃被标记为删除的空间数据，之后将所有的空间数据重新组织成一个默克尔r树并插入到上一层的默克尔r树中。5.根据权利要求1所述的能够实现高效更新和查询的空间数据管理方法，其特征在于，相邻的两个层级的网格中，高一层级网格中默克尔r树的大小上限设定为相邻的低一层级网格中默克尔r树的大小上限的整数倍。6.根据权利要求1所述的能够实现高效更新和查询的空间数据管理方法，其特征在于，确定要删除的原空间数据所在的网格时，通过原空间数据在上层网格中的相对位置关系，可以计算得到所述原空间数据所在的下一层网格，并可根据空间数据所在下一层网格中的相对位置计算得到原空间数据所在的更下一层网格，直到找到空间数据存在的网格，在该网格的默克尔r树中进行搜索并找到该原空间数据，通过将该原空间数据所在叶子节点的设置为删除来进行删除。7.根据权利要求1所述的能够实现高效更新和查询的空间数据管理方法，其特征在于，进行空间范围查询时，将空间查询的范围与每一层的网格进行相交判定，对每一层中所有相交的网格中的默克尔r树进行空间范围查询并生成可验证的子查询结果；将所述子查询
结果收集并形成针对空间范围查询的完整的可验证查询结果。

技术总结
本发明公开一种能够实现高效更新和查询的空间数据管理方法，空间数据为多层的数据结构，数据结构的每一层都是对整个空间范围进行不同细粒度的划分而形成的网格；在每一个网格中，数据结构都维护着一棵用以管理空间数据的默克尔R树，所有的数据更新都优先发生在最小粒度的网格维护的默克尔R树中；新空间数据插入和原空间数据删除具体为：确定要空间数据应该插入删除的最低层级的网格，然后将空间数据插入或删除；空间数据更新为连续执行删除和插入操作。空间范围查询为将空间范围查询任务细分到不同层，对每一层进行空间范围查询，并整合每一层的查询结果，组成空间范围查询任务的可验证查询结果。本发明对空间数据的更新和查询效率高。询效率高。询效率高。


技术研发人员：方誉州 蔡亮
受保护的技术使用者：浙江大学
技术研发日：2023.04.26
技术公布日：2023/8/9