一种数据查找的方法及装置

摘要

本发明公开了一种数据查找的方法，该方法包括：根据当前与搜索数据串匹配的节点的第二条目，查找是否有与所述搜索数据串匹配的子节点；当有与所述搜索数据串匹配的子节点时，以所述子节点为下一个与搜索数据串匹配的节点继续查找；当没有与所述搜索数据串匹配的子节点时，根据所述第二条目，查找对应的第一条目，得到所述搜索数据串的最长匹配前缀。及一种数据查找的装置，根据每个节点中的项数不同，采用一个或多个长度为L的数据结构表示每个节点，通过这种灵活的表示方式，提高内存的利用率，进一步的提高网络容量。

主权项

一种数据查找的方法，用于查找最长匹配前缀，系统硬件支持的最大步长为N，N为自然数，步长N对应的数据结构长度为L；其特征在于，根据路由表构造步长为M的查找树，所述查找树的每个节点包括第一条目和第二条目，所述第一条目用于表示所述第一条目对应节点的前缀节点，所述第二条目用于表示所述第二条目对应节点的子节点，所述第二条目包括指向所述第一条目的指针；其中，M为大于N的自然数；当所述节点的前缀节点中的项数不小于2N/M时，所述第一条目采用二的M‑N次幂个长度为L的数据结构表示，对应的第一条目的数据结构类型为第一类型；当所述节点的前缀节点中的项数小于2N/M时，所述第一条目采用一个长度为L的数据结构表示，对应的第一条目的数据结构类型为第二类型；当所述节点的子节点中的项数不小于2N/M时，所述第二条目采用二的M‑N次幂个长度为L的数据结构表示，对应的第二条目的数据结构类型为第一类型；当所述节点的子节点中的项数小于2N/M时，所述第二条目采用一个长度为L的数据结构表示，对应的第二条目的数据结构类型为第二类型；该方法包括：根据当前与搜索数据串匹配的节点的第二条目，查找是否有与所述搜索数据串匹配的子节点；当有与所述搜索数据串匹配的子节点时，以所述子节点为下一个与搜索数据串匹配的节点继续查找；当没有与所述搜索数据串匹配的子节点时，根据所述第二条目，查找对应的第一条目，得到所述搜索数据串的最长匹配前缀。