(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202210650145.0 (22)申请日 2022.06.10 (71)申请人 东北大学 地址 110819 辽宁省沈阳市和平区文化路 三号巷11号 申请人 东软集团股份有限公司 (72)发明人 信俊昌　姜吉宁　郝琨　姚钟铭　 刘红飞　王之琼　徐石成　黄敏　 (74)专利代理 机构 沈阳东大知识产权代理有限 公司 21109 专利代理师 李在川 (51)Int.Cl. G06F 16/22(2019.01) G06F 16/2455(2019.01) G06F 16/2458(2019.01)G06F 16/27(2019.01) G06F 21/62(2013.01) (54)发明名称 一种混合存储区块链环境下的时空关键字 查询方法 (57)摘要 本发明针对链上链下混合存储区块链的时 空关键字查询问题， 提出了一种混合存储区块链 环境下的时空关键字查询方法， 涉及计算机区块 链查询技术领域； 首先， 针对查询语义较弱， 构建 按属性分类且赋 予语义的区块链模型CSBM， 为区 块内的事务划分属性类型并添加语义； 其次， 针 对查询效率较低， 构建基于B2F‑BKM结构的链上 两级索引结构， 该结构能够对所有区块和事务进 行索引， 有效提升查询效率； 最后， 针对通信开销 较大， 设计链上链下时空关键字查询方法， 通过 遍历B2F‑BKM结构进行链上条件查询， 然后根据 连接属性值进行链上链下数据连接查询， 相比传 统查询方法减少了不必要的通信开销； 经试验证 明本发明索引具有良好稳定性， 查询效率大幅提 升并且通信开销明显降低。 权利要求书2页 说明书6页 附图5页 CN 115048377 A 2022.09.13 CN 115048377 A 1.一种混合存储区块链环境下的时空关键字查询方法， 其特征在于， 具体包括以下步 骤： 步骤1： 构建按属性分类且赋予语义的区块链模型即CSBM； 步骤2： 构建基于B2F‑BKM结构的链上两级索引结构； 该结构由两部分组成， 分别 为块间 B2F‑树和块内BKM ‑树， 完成对所有区块和事务的索引； 步骤3： 设计链上链下时空关键字查询方法； 获取查询条件， 根据链上两级索引结构B2F‑ BKM结构， 即B2F‑树和BKM‑树进行链上条件查询， 并提取查询到的事务的连接属性值， 根据 该值进行链上链下 连接查询并返回最终结果。 2.根据权利要求1所述的一种混合存储区块链环境下的时空关键字查询方法， 其特征 在于， 步骤1具体为： 步骤1.1： CSBM包含多个按属性分类且赋予语义的区块CS ‑B， CSBM＝CS ‑B1+CS‑B2 +···+CS‑Bn， 每个CS‑B包含区块头B  head和按属性分类且赋予语义的区块体CS ‑B body 两部分； 其中CS ‑B＝B head+CS‑B body； B head与传统区块链区块头结构基本相同； 而原本 区块头中的Merkle根Merkle  Root由步骤2中构建的BKM ‑树的根节点BKM ‑tree Root代替， 但同样基于块内事务的哈希 值生成， 用于保证块内事务的不可篡改； CS ‑B body中包含 该区 块内的全部事务， 为 这些事务划分属性类型并且添加语义； 步骤1.2： 定义Tx为CSBM中一条按属性分类且赋予语义的事务， Tx＝{Key＝v1,Time＝ {time＝v2},Coordinat e＝{longitude＝v3,latitude＝v4},Keywords＝{kw1,kw2,···, kwn},Others＝{oth1,oth2,···,othn}}， Key为该事务的主键， 通过计算该事务的哈希值 得到， 使用长度为64的16进制字符串来表示； Time为时间属性类型， time为该事务的时间 戳， Coordinate为空间属性类型， longitude为该事务的经度， latitude为该事务的纬度， vi 为属性值， Keywords为关键字属 性类型， kwi为该事务某个关键字的属 性名称； Others为其 他属性类型， othi为该事务的其他属性的名称； 针对不同应用场合和事务类型， 设定不同的 属性名称。 3.根据权利要求2所述的一种混合存储区块链环境下的时空关键字查询方法， 其特征 在于， 所述B ‑head包括将区块连接成链的前区块哈希值PrevHash、 记录当前区块在链上位 置的区块高度Block  Height、 记录区块生成时间的时间戳Timestamp以及挖矿难度Bits和 随机数Nonce。 4.根据权利要求1所述的一种混合存储区块链环境下的时空关键字查询方法， 其特征 在于， 步骤2具体为： 步骤2.1： 在每个区块内构建BKM ‑树替换原来的Merkle树； 在构建新区块过程中， 提取 该区块内所有事务空间属性类型值和关键字属性类型值； 模仿KD ‑树结构， 根据事务的空间 属性数据划分区域， 直至每个区域只包含一条事务， 事务只存储在叶子节点中， 非叶子节 点 存储与数据划分相关的信息； 然后为KD ‑树添加布隆过滤器字段， 根据事务的关键字属性数 据构造布隆过滤器， 非 叶子节点的布隆过滤器中包含其孩子节点的全部关键字； 最后按照 Merkle树的构 造方式自底向上计算每个节 点的哈希 值形成BKM ‑树， 并将根节 点记录在区块 头中； 步骤2.2： 构造基于块号、 区块创建时间以及块内关键字的区块间B2F‑树； 获取新的区块 数据， 构造B2F‑树节点， 叶节点中键的格式为 “block‑id,timestamp,bf ”， 其中block‑id来权　利　要　求　书 1/2 页 2 CN 115048377 A 2自位于区块头的区块高度Block  Height， timestamp来自位于区块头的时间戳Timestamp， bf与块内BKM ‑树根节点中的布隆过滤器相同； 叶节 点中的指针记录了区块位于区块链文件 中的地址偏移量； 非叶子节点的布隆过滤器中包含其子树的所有关键字， 用于过滤指针， 判 断该指针指向的节点是否含有相应的关键字， 根据block ‑id按照B+树节点插入方式更新 B2F‑树； 步骤2.3： 链上两级索引结构B2F‑BKM结构构建完成。 5.根据权利要求4所述的一种混合存储区块链环境下的时空关键字查询方法， 其特征 在于， 所述获取新的区块数据包括新区块的块号b lock‑id、 区块创建时间timestamp、 块内 关键字构成的布隆过 滤器bloomfilter‑bf、 区块位于区块链文件中的地址偏移量。 6.根据权利要求1所述的一种混合存储区块链环境下的时空关键字查询方法， 其特征 在于， 步骤3具体为： 步骤3.1： 定义混合存储区块链环境下 的时空关键字查询由四元组构成， Q＝[[Ts,Te], S,W,join‑attr]； 步骤3.2： 根据查询Q中的时间和关键字条件， 遍历B2F‑树； 基于B2F‑树节点中键的 “timestamp,bf ”部分从根节点开始， 根据时间条件选择分支指针， 然后根据布隆过滤器判 断该指针所指节点是否包含查询关键字W， 包含则继续遍历， 否则终止； 按此方法直到叶子 节点， 查找出包含查询关键字W且时间大于等于 ‘Ts’、 小于等于 ‘Te’的所有键并通过指针得 到这些块的位置； 步骤3.3： 查询到具体区块后， 根据查询Q中的空间和关键字条件， 依次遍历位于区块内 的BKM‑树； 按照KD ‑树的搜索方式从根节 点开始自顶向下选择子节 点， 并判断子节 点的布隆 过滤器中是否包含全部查询关键字， 若包含则遍历该子节点， 若不包含， 则放弃此分支； 按 照此方法直至叶子节点， 即找到块内满足空间和关键字条件的所有事务； 获取叶子节点中 的键数据， 即事务的哈希值Key， 再根据键数据得到原始数据， 若满足时间条件， 则将该数据 加入链上 结果集Onchain‑RS； 步骤3.4： 根据查询Q中的连接条件join ‑attr， 提取Onchain ‑RS中原始数据的连接属性 的值， 根据该值查询链下数据库表中的数据， 并加入链下结果集Offchain ‑RS； 读取 Offchain ‑RS和Onchain ‑RS内数据通过连接属性进行链上链下数据连接后， 将结果存入结 果集ResultSet； 步骤3.5： 返回ResultSet， 终止当前计算并等待下一次调用。 7.根据权利要求6所述的一种混合存储区块链环境下的时空关键字查询方法， 其特征 在于， 步骤3.1中[Ts,Te]为用户查询的时间范围， S为用户查询的空间范围， W为用户查询的 关键字数据集合， 包含若干关键字， join ‑attr为等式形式的连接条件， 等式左边为链上需 要连接的关键 字属性名， 等式右边 为链下数据库表中连接关键 字属性名。权　利　要　求　书 2/2 页 3 CN 115048377 A 3