(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211159072.1 (22)申请日 2022.09.22 (71)申请人 上海电科市政工程有限公司 地址 200333 上海市普陀区中江路938号 803室 (72)发明人 郑文　邱晓东　王玲　王洋洋　 史强强　朱国磊　 (74)专利代理 机构 上海璀汇知识产权代理事务 所(普通合伙) 31367 专利代理师 王文颖 (51)Int.Cl. G06F 16/22(2019.01) G07B 15/06(2011.01) (54)发明名称 一种基于B+树的ETC收费系统用户卡状态名 单存取方法 (57)摘要 相较于内存加载结合hash表的存 取方法， 本 发明提供的一种基于B+树的用户卡状态名单存 取方式取消了hash计算操作， 解决因hash碰撞 造 成的数据冲突。 本发明引入用户卡槽的聚合模 型， 对相同槽下的b+树可以实现并发写入， 极大 地提升数据写入性能， 加载完成4450万用户卡状 态名单耗时仅需110秒。 结合b+树的存取特性， 将 用户卡状态名单单条记录压缩到28字节， 全量加 载完仅需1.16G内存空间， 有效的降低了ETC收费 系统的建设成本， 提升了系统的健壮性和鲁棒 性。 在查询效率方面， 采用本发明提供的技术方 案后， 单记录命中耗时不到1ms， 相较于hash查找 算法耗时略有增加， 但依然能够满足ETC收费系 统的高效运作。 权利要求书2页 说明书5页 附图2页 CN 115510059 A 2022.12.23 CN 115510059 A 1.一种基于B+树的ETC收费系统用户卡状态名单存取方法， 其特征在于， 包括以下步 骤： 第一步、 将用户卡状态名单转化为单链数据结构dictionary实例， 其中， 链数据结构 dictionary包括用于记录用户卡号的key字段、 用于记录用户卡状态信息的value字段以及 用于存储指向其它单链数据结构dicti onary实例的指针的next字段； 第二步、 在写入用户卡状态名单时， 对于当前单链数据结构dictionary实例的处理包 括以下步骤： 步骤1、 获得当前单链数据结构dictionary实例的key字段的值Key， 查找与当前用户卡 槽对应的B+树实例中各叶子节点的key数组每 个key元素值： 若在当前key数组中存在等于值Key的key元素值， 则将等于值Key的key元素值定义为 当前key元 素值， 进入步骤6； 若在当前B+树实例中未查找到等于值Key的key元素值， 但在当前key数组中存在小于 值Key的key元 素值， 则将与当前key数组对应的叶子节点作为当前叶子节点， 进入步骤3； 若在当前B+树实例中未查找到小于等于值K ey的key元 素值， 则进入步骤2； 步骤2、 新建叶子节点， 将新建的叶子节点作为当前叶子节点， 进入步骤3； 步骤3、 判断当前叶子节点是否已满： 若当前叶子节点已满， 则分裂当前叶子节点， 将分 裂得到的叶子节点作为新的当前叶子节点， 进入步骤4； 若当前叶子节点未满， 则直接进入 步骤4； 步骤4、 将值Key作为一个key元素值存入当前叶子节点的key数组中， 并对key数组中所 有key元素值重组排序， 获得重组排序后值K ey在当前key数组中的排序 序号k， 进入步骤5； 步骤5、 新建第k个value数组， 依据当前单链数据结构dictionary实例的next字段， 在 第k个value 数组的对应位置存 入当前单链数据结构dicti onary实例； 步骤6、 获取当前key元素值所对应的value数组及其中存储的第一个单链数据结构 dictionary实例， 将该单链数据结构dictionary实例定义为上一个单链数据结构 dictionary实例， 进入步骤7； 步骤7、 若上一个单链数据结构dictionary实例的next字段为空， 则将上一个单链数据 结构dictionary实例的next字段指向当前单链数据结构dictionary实例， 在当前单链数据 结构dictionary实例存入当前v alue数组中， 且当前单链数据结构dictionary实例在当前 value数组中的位置位于上一个单链数据结构dictionary实例之后； 若上一个单链数据结 构dictionary实例的next 字段非空， 则进一步获得单链数据结构dictionary实例的next字 段指向的下一个单链数据结构dictionary实例， 将所获得的下一个单链数据结构 dictionary实例定义 为新的上一个单链数据结构dicti onary实例后， 返回步骤7循环执 行； 在查询查询用户卡状态名单时， 在 B+树实例中进行查询。 2.如权利要求1所述的一种基于B+树的ETC收费系统用户卡状态名单存取方法， 其特征 在于， 第一步中， 进 行用户卡状态名单转化时， 将用户卡号的前N个字 符截取作为用户卡槽， 同一用户卡槽对应一个B+树实例， 则用户卡 号前四位相同的数据聚合在一个B+树中； 第二步中， 在查询查询用户卡状态名单时， 先将用户卡号前N个字符截取， 命中与其对 应的用户卡槽的B+树实例， 然后在该B+树实例中进行查询。 3.如权利要求1所述的一种基于B+树的ETC收费系统用户卡状态名单存取方法， 其特征权　利　要　求　书 1/2 页 2 CN 115510059 A 2在于， 用户卡号为长度20的数字字符串， 则取用户卡号的前4个字符作为卡槽标记， 用户卡 号的后16字符为用户卡标记， 将用户卡标记转为long类型， 将卡槽标记及转为long类型的 用户卡标记存 储在所述 key字段中。 4.如权利要求1所述的一种基于B+树的ETC收费系统用户卡状态名单存取方法， 其特征 在于， 所述value字段仅用于记录用户卡状态信息中的状态生效时间、 操作类型和操作状 态， 且使用计算状态生效时间+操作状态*10+操作类型得到长度所得到的15位的long值类 型数据存储在所述value字段中。权　利　要　求　书 2/2 页 3 CN 115510059 A 3