(19)中华 人民共和国 国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210024027.9 (22)申请日 2022.01.10 (71)申请人 北京新华夏信息技 术有限公司 地址 100000 北京市海淀区北四环中路2 29 号海泰大厦11层1107室-3 (72)发明人 钱滨冰　罗玲　丁良　孙路　 方誉州　李超林　李智　雷志刚　 (74)专利代理 机构 郑州欧凯专利代理事务所 (普通合伙) 41166 代理人 毛志强 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/23(2019.01) (54)发明名称 一种空间数据管理方法、 装置、 存储介质及 区块链系统 (57)摘要 本发明属于区块链 技术领域， 尤其为一种空 间数据管理方法、 装置、 存储介质及区块链系统， 该空间数据管理方法将建立的空间默克尔树通 过将默克尔树与R树相结合， 在R树的结构中加入 哈希字段， 使得建立的空间默克尔树既能为空间 数据建立高效的空间索引， 同时又保留默克尔树 的认证功能， 用于在区块链中验证所获取数据的 完整性和正确性； 该空间默克尔树的叶子节点存 储资源节 点， 而不是直接存储区块链上的空间数 据资源， 资源节点中所包含的字段内容是区块链 上空间数据资源在内存中的轻量化表 示， 可以减 少空间默克尔树在内存中占用的空间大小， 减小 区块链系统的内存压力， 能够 有效提升区块链系 统的计算效率， 降低合约执 行等任务的时延。 权利要求书2页 说明书10页 附图1页 CN 114372058 A 2022.04.19 CN 114372058 A 1.一种空间数据管理方法， 其特征在于， 包括： 建立底层KV数据库和空间默克尔树， 空 间数据存 储在所述底层KV数据库中， 所述空间默克尔树用于管理所述空间数据； 所述空间默克尔树中设有中间节点、 叶子节点和资源节点， 其中： 所述中间节点中的字段包含第 一哈希值、 第一范围数据、 第 一指针数组、 孩子节点的数 量、 第一父节点指针， 所述第一哈希 值由所述中间节点的所有孩子节点共同获取， 所述第一 范围数据为所述中间节点所表示的最小边界矩形的范围， 所述第一指 针数组中的元素为指 向该中间节点的各孩子节点的第一指针， 所述孩子节点的数量是指该中间节点所指向的孩 子节点的数量， 所述第一父节点指针为指向该中间节点的父节点的指针； 所述叶子节点中的字段包含第二哈希值、 第二范围数据、 keys数组、 资源节点的数量、 第二父节点指针， 所述第二哈希值由所述叶子节点的所有资源节点共同获取， 所述第二范 围数据为所述叶子节 点所表示的最小边界矩形的范围， 所述keys数组中的元素分别代表所 述叶子节点的各资源节点中的资源， 所述资源节 点的数量是指该叶子节点所拥有的资源节 点的数量， 所述第二父节点指针为指向该叶子节点的父节点的指针； 所述资源节点中的字段包含第三哈希值、 空间位置信息、 key， 所述第三哈希值为资源 节点所表示资源的哈希值， 所述空间位置信息用于定位该资源节点在空间默克尔树中的位 置， 所述key为资源节点所表示资源在所述底层KV数据库中的键值。 2.根据权利要求1所述的空间数据管理方法， 其特征在于： 所述空间默克尔 树设有两个 参数M、 m， 其中， M表示所述空间默克尔树中非叶子节点所能容纳的孩子节点的最大数量， m 表示所述空间默克尔树中非叶子节点所需要容纳的最小孩子节点数量； 所述第一指 针数组 以及keys数组是一个容量为M的固定大小的数组， 所述孩子节点的数量以及所述资源节点 的数量的最小值 为m。 3.根据权利要求1所述的空间数据管理方法， 其特征在于： 所述第 一哈希值通过所述中 间节点的所有孩子节 点的哈希值经过哈希计算获得， 所述第二哈希值通过所述叶子节点的 所有资源节点的哈希值经 过哈希计算获得； 所述第一哈希值的计算公式为： 所述第二哈希值采用与计算所述第 一哈希值相同的哈希函数， 所述二哈希值的计算公 式为： 其中， h为哈希值， H为哈希函数， |表示将两个哈希值按照字符串 的方式拼接在一起的 拼接符。 4.根据权利要求1所述的空间数据管理方法， 其特征在于， 还包括对所述空间默克尔 树 的状态更新， 所述对所述空间默克尔树的状态更新包括： (1)资源节点的状态更新： (a)资源节点的插入、 删除； (b)对资源节点进行空间位置信 息更新， 即更新资源节点在空间默克尔树中的位置； (c)对资源节点进行资源数据更新； (2)由于资源节点的状态更新， 引起的对相应叶子节点的第二哈希值的更新， 以及引起 的对相应中间节点的第一哈希值的更新。 5.根据权利 要求1所述的空间数据管理方法， 其特征在于， 还包括提供数组Proof， 所述 数组Proof用于对被验证资源节 点中空间数据的完整性和正确性进 行证明， 所述数 组Proof权　利　要　求　书 1/2 页 2 CN 114372058 A 2的获取方式如下： (1)初始化 一个存放证明的数组Pro of； (2)从底层KV数据库中获得key所对应的空间数据资源的空间位置信息， 构造资源节点 rn； (3)找到资源节点rn所在的叶子节点 L； (4)令P＝L， N＝rn， 确定N在P数组中的下标i， 按下标升序顺序， 构造N的兄弟节点的哈 希值的数组SV； (5)构造元组t＝(i， SV)， 将t插 入到数组Pro of的最后； (6)如果P是根节点， 则结束操作； 否则获得P节点的父节点P P， 令N＝P， P＝P P； 重复2‑6； 所述数组Proof包含从空间默克尔树的根节点到被验证资源节点路径上所有节点的兄 弟节点的哈希值。 6.一种空间数据管理装置， 其特 征在于， 包括： 底层KV数据库模块， 空间数据存 储在所述底层KV数据库模块中； 空间默克尔 树模块， 所述空间默克尔 树模块中设有中间节点、 叶子节点和资源节点， 其 中： 所述中间节点中的字段包含第 一哈希值、 第一范围数据、 第 一指针数组、 孩子节点的数 量、 第一父节点指针， 所述第一哈希 值由所述中间节点的所有孩子节点共同获取， 所述第一 范围数据为所述中间节点所表示的最小边界矩形的范围， 所述第一指 针数组中的元素为指 向该中间节点的各孩子节点的第一指针， 所述孩子节点的数量是指该中间节点所指向的孩 子节点的数量， 所述第一父节点指针为指向该中间节点的父节点的指针； 所述叶子节点中的字段包含第二哈希值、 第二范围数据、 keys数组、 资源节点的数量、 第二父节点指针， 所述第二哈希值由所述叶子节点的所有资源节点共同获取， 所述第二范 围数据为所述叶子节 点所表示的最小边界矩形的范围， 所述keys数组中的元素分别代表所 述叶子节点的各资源节点中的资源， 所述资源节 点的数量是指该叶子节点所拥有的资源节 点的数量， 所述第二父节点指针为指向该叶子节点的父节点的指针； 所述资源节点中的字段包含第三哈希值、 空间位置信息、 key， 所述第三哈希值为资源 节点所表示资源的哈希值， 所述空间位置信息用于定位该资源节点在空间默克尔树中的位 置， 所述key为资源节点所表示资源在所述底层KV数据库中的键值。 7.一种计算机可读存 储介质， 其特 征在于： 所述计算机可读存储介质存储有底层KV数据库， 所述底层KV数据库中存储有空间数 据； 所述计算机可读存储介质还存储有用于处理空间数据的程序指令， 用于被处理器执行 时， 实现如权利要求1至 5中任意一项所述的空间数据管理方法。 8.一种区块链系统， 其特征在于： 所述 区块链系统中设有权利要求6所述的空间数据 管 理装置。权　利　要　求　书 2/2 页 3 CN 114372058 A 3