一种基于树形数据结构的最长前缀匹配方法和装置

摘要

本发明公开了最长前缀匹配方法和装置，该方法包括：A.读取一个搜索节点；B.确定读出的搜索节点的偏移量域是否指示上一级别的节点内存在匹配的前缀，如果存在，将上一级别的节点内指向叶子节点数组的指针加上该搜索节点的偏移量域，更新当前最佳匹配指针，并执行步骤C；如果不存在，执行步骤C；C.确定该搜索节点的分支指示域和搜索关键字的对应比特匹配时，确定该搜索节点是否存在子节点；D.确定该搜索节点不存在子节点时，读取该搜索节点的内部位图，根据内部位图和搜索节点内指向叶子节点数组的指针，计算该搜索节点内存在的最长匹配前缀，更新当前最佳匹配指针，计算当前最佳匹配指针对应的叶子节点的地址。该方法可以提高查询速度。

主权项

一种基于树形数据结构的最长前缀匹配方法，其特征在于，所述树形数据结构代表多个前缀，前缀被区分为至少一个步，每个节点表示一步，所述方法包括：A.读取所述树形数据结构中当前级别的一个搜索节点；B.确定读出的所述搜索节点的偏移量域是否指示上一级别的节点内存在匹配的前缀，如果存在匹配的前缀，则将上一级别的节点内指向叶子节点数组的指针和所述搜索节点的偏移量域相加，更新当前最佳匹配指针，并执行步骤C；如果不存在匹配的前缀，直接执行步骤C，其中，如果当前节点的父节点内存在匹配的前缀，所述偏移量域用于指出该前缀对应的下一跳信息的地址相对于父节点内所存储的指向叶子节点数组的指针的偏移量，所述最佳匹配指针为：匹配的长度最长的前缀所对应的下一跳信息的地址；C.当确定所述搜索节点的分支指示域和搜索关键字的对应比特匹配时，根据子节点位图确定所述搜索节点是否存在子节点，其中，所述分支指示域用于指示当前路径延伸出本节点的父节点时，本节点位于路径的左分支还是右分支；D.当确定所述搜索节点不存在子节点时，读取所述搜索节点的内部位图，并根据所述内部位图和所述搜索节点内指向叶子节点数组的指针，计算所述搜索节点内存在的匹配的长度最长的前缀，用计算结果更新当前最佳匹配指针，并计算所述当前最佳匹配指针所对应的叶子节点的地址，其中，所述内部位图用于指示该内部节点所对应的搜索节点内存在的前缀。