一种面向内容网络中内容名存储结构的设计方法

摘要

本发明提供一种面向内容网络中内容名存储结构的设计方法，嵌套分段散列表的分层嵌套结构通过相同前缀的内容名聚合，减少存储空间的开销，作为嵌套分段散列表中的基础数据结构单元，分段散列表在散列表的基础上引入分段思想，通过添加布隆滤波器和Bit‑map作为索引结构，对进入对应子表散列计算的数据提供预处理，减少对存储表的直接操作次数，提高查找效率；同时使用基于内容热门度参数的链表法解决散列冲突，降低热门内容名的查找时间，引入分段散列表子表、嵌套分段散列表同层节点间的并列关系，在实现中有效利用多核CPU的计算能力，高效的完成分段散列表中数据的插入、查找和删除操作，提高内容名存储结构的处理能力。

主权项

一种面向内容网络中内容名存储结构的设计方法，其特征在于：包括以下步骤：构建嵌套散列表，将嵌套散列表中各散列表替换为分段散列表得到嵌套分段散列表，所述分段散列表内各子表以布隆滤波器和位数组作为索引结构，嵌套分段散列表总体上是一个前缀树结构，每个节点由一个分段散列表组成，内容名的每个前缀分层对应前缀树结构中的一个节点，节点内使用分段散列表完成对内容名前缀分层的存储；完整内容名在嵌套分段散列表中的插入包括以下步骤：1)对待插入的内容名第一分层使用嵌套分段散列表第一层分段散列表中的所有子表对应的散列函数进行散列寻址计算；2)在每个子表中的位数组中对比对应地址是否冲突，并选择出无冲突的子表，在所述无冲突的子表中选择对应布隆滤波器中非零位最少的子表对所述内容名第一分层进行存储；3)在存储内容名第一分层的子表索引结构中完成对存储位和校验信息的标记；4)参照步骤1)‑3)，使用内容名的其余分层在各自对应的嵌套分段散列表分层上依次进行散列寻址插入操作，直至插入完整内容名。