用于产生和使用改进的树形位图数据结构的方法和装置

摘要

公开了用来在例如路由器、包交换系统中，在确定最长前缀匹配时，产生和使用一种改进的树形位图数据结构的方法和装置。一个实现组织树形位图，以最小化在一个查找操作过程中必须被访问的内部节点的数量。在TRIE或搜索节点的每一个中都包含有一个指向叶或结果数组中迄今最佳匹配条目的指针，这允许对这个结果的直接访问而不用必须分析相应的内部节点。而且，一个实现将特定级别的内部节点存储为在它的子数组中的第一个单元。此外，一个实现使用能够同时遍历多个树形位图或其他数据结构的通用搜索引擎，并且执行完全搜索、部分搜索和例如在接收到要搜索的额外数据后重新开始部分搜索。

主权项

1.一种基于一个输入搜索数据串、用来遍历存储在一个或多个计算机可读介质中的树形数据结构的方法，该方法包括对输入搜索数据串的多个部分中的每一部分都执行一套步骤，这套步骤包括：(a)接收一个部分完成的树遍历的搜索进程上下文，搜索进程上下文包括下一个节点地址；(b)重新开始所述对树形数据结构的遍历，包括重复执行步骤(i)到(iv)，用来遍历对应输入搜索数据串的多个部分中的下一个的树形数据结构：(i)将包括下一个节点地址的查找请求分送到多个存储设备中的一个；(ii)从所述多个存储设备中的一个中接收查找结果，查找结果包括一个搜索节点；(iii)响应确定一个新的最佳匹配是否存在，更新当前最佳匹配标识符；(iv)索引到搜索节点的当前级别扩展位图，以确定一个匹配的下一级别节点是否存在；(v)产生下一个节点地址的新值；和(c)产生搜索进程上下文的新值。