密钥生成

Question

我使用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; 
} 

所以搜索是基于“结构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树 不需要重建？）

我正在考虑在每个listnode上生成CRC，然后总结。这可以保证钥匙的唯一性吗？ （缺点是，无论何时添加/删除listnode，我都必须重新生成密钥，从tre删除节点并用新密钥重新添加）。

谢谢！

Answer 1

我使用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)。

此外，在列表中添加一个新的节点后，我是否需要重新编译树...

如果要更新平衡搜索树中的节点以便更改密钥，最好的办法可能是删除它并重新插入它。

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

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

不，CRC是一种哈希函数。它的位数比被哈希的对象少，因此多个对象可以哈希到相同的CRC。 （当一组元素找到“完美哈希函数”时，例外情况是这样，但动态数据很少出现这种情况：对于某些静态数据集合，完美哈希函数是有效的）。使用哈希方法，您可能会以及使用哈希表。 CRC的排序关系可能没有意义。当集合必须通过关键字的排序关系进行排序时，使用二元搜索树。