用树状分段改善树搜索性能和存储器带宽的方法和系统

摘要

公开了一种用于改善表查找的性能的数据结构和对应搜索方法。使用具有指向树状分段的散列表条目的散列表来利用该表的数据结构，所述树状分段在主存储器内相邻并可被有效载入本地数据存储或高速缓冲存储器。树状分段的叶节点包含数据记录的标记，或另一树状分段的标记。采用该数据结构和对应搜索算法来基于一个网际路由表的最长前缀匹配而进行搜索。

主权项

1.一种对使用散列表和多个树状分段的数据结构进行初始化的方法，包括：创建该散列表；创建该多个树状分段；该多个树状分段的每一个树状分段在存储器片段中被相邻地存储；对应于每一树状分段散列至少一个表条目，由此创建至少一个散列关键字和至少一个散列表条目；和将所述每一个树状分段分配给至少一个散列表条目。