0

我有一个使用 AVL 树快速搜索 IP 地址的大型系统:

struct avl_node
{
   struct avl_node *left;
   struct avl_node *right;
   ...
   void *info; /* point to nhlfe_entry describing nexthop */
}

struct nhlfe_entry
{
  u_int32_t nhlfe_ix;
  u_char opcode;
  ...
  struct nhlfe_key key;
}

/* defines a search key. */
struct nhlfe_key
{
  struct in_addr nh_addr;
  u_int32_t oif_ix;
  u_int32_t out_label;
}

所以搜索基于'struct nhlfe_key',即AVL树中的比较器函数如下所示:

static int
mpls_cmp_nhlfe_ipv4_key (void *data1, void* data2)
{
   struct nhlfe_entry *nh1, *nh2;
   struct nhlfe_key *key1, *key2;
   int ret;

   nh1 = (struct nhlfe_entry *) data1;
   nh2 = (struct nhlfe_entry *) data2;

   key1 = (struct nhlfe_key *) nh1->nkey;
   key2 = (struct nhlfe_key *) nh2->nkey;

   ret = memcmp (&key1->nh_addr, &key2->nh_addr, sizeof (struct in_addr));
   if (ret != 0)
     return ret;

   if (key1->oif_ix > key2->oif_ix)
     return 1;
   else if (key1->oif_ix < key2->oif_ix)
     return -1;

   if (key1->out_label > key2->out_label)
     return 1;
   else if (key1->out_label < key2->out_label)
     return -1;

   return 0;
}

现在,我要做的是添加对多个下一跳的支持,即我在 nhlfe_entry 中添加一个链表:

struct nhlfe_entry
{
  u_int32_t nhlfe_ix;
  u_char opcode;
  ...
  struct list *nhkey_list;
}

每个'struct list'都是struct listnode,它嵌入'void *data'指针到调用者的私有数据,这就是'struct nhlfe_key'。

所以我的问题是——如何基于列表中的多个元素生成密钥以存储/搜索树中的节点(因为否则现在在引入列表之后,将不可能仅基于一个 下一跳地址)。此外,他们同样的问题适用于搜索。

另外,在列表中添加新节点后,是否需要重新构建树,因为我认为此操作会更改键,因此树可能会变得不平衡?(或者正确实现的AVL树自然不需要重建?)

我正在考虑在每个列表节点上生成 CRC,然后进行总结。这可以保证密钥的唯一性吗?(缺点是每当我添加/删除列表节点时,我必须重新生成密钥,从树中删除节点并使用新密钥重新添加)。

谢谢!

4

1 回答 1

2

我有一个使用 AVL 树快速搜索 IP 地址的大型系统:

对于大量 IP 地址,您通常需要一个基数树。二叉树可以工作,但您无法使用前缀存储地址范围,例如10.*. 如果您没有将它用于任何类似于路由的东西,或者您不需要节省空间将整个子网映射到某些东西。

所以我的问题是——如何根据列表中的多个元素生成密钥以存储/搜索树中的节点(因为否则现在在引入列表之后,将不可能仅基于一个下一跳来获得密钥地址)。此外,他们同样的问题适用于搜索。

您的mpls_cmp_nhlfe_ipv4_key函数只需比较可能是地址列表的键。显然(1 2 3)比较等于(1 2 3)。此外,(1 2 3)比较大于(1 2),但小于(1 3)(1 2 4)

另外,在列表中添加新节点后,是否需要重新构建树...

如果要更新平衡搜索树中的节点以使键发生变化,最好的办法可能是删除它并重新插入它。

可能有优化它的方法。例如,假设一个键发生了变化,但它在树中仍然具有完全相同的后继者和前任者。在这种情况下,它可以就地完成。或者密钥可以以这样一种方式改变,即节点只需要与前任或后继者交换。在尝试这样的技巧之前,我会做对的。

[a CRC] 可以保证密钥的唯一性吗?

不,CRC 是一个散列函数。它比被散列的对象具有更少的位,因此多个对象可以散列到相同的 CRC。(例外情况是为一组元素找到“完美散列函数”,但动态数据很少发生这种情况:完美散列函数是为某些静态数据集设计的。)使用散列方法,您可能会很好地使用哈希表。CRC 上的排序关系可能毫无意义。当必须通过键上的排序关系对集合进行排序时,使用二叉搜索树。

于 2012-04-04T23:47:59.473 回答