0

IPアドレスの高速検索にAVLツリーを使用する大規模なシステムがあります。

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;
}

各「structlist」は、呼び出し元のプライベートデータへの「void *data」ポインタを埋め込むstructlistnodeであり、これは「structnhlfe_key」です。

だから私の質問は-リストからの複数の要素に基づいてキーを生成し、ツリー内のノードを格納/検索する方法です（そうでなければ、リストを導入した後、 1つ のネクストホップのみに基づいてキーを持つことはできません）住所）。また、同じ質問が検索にも当てはまります。

また、リストに新しいノードを追加した後、この操作によってキーが変更され、ツリーのバランスが崩れる可能性があるため、ツリーを再構築する必要がありますか？（または、正しく実装されたAVLツリーを再構築する必要はありませんか？）

すべてのリストノードでCRCを生成し、合計することを考えています。これはキーの一意性を保証できますか？（欠点は、listnodeを追加/削除するたびに、キーを再生成し、treからノードを削除して、新しいキーで再追加する必要があることです）。

ありがとう！

4

1 に答える 1

2

IPアドレスの高速検索にAVLツリーを使用する大規模なシステムがあります。

多数のIPアドレスの場合、通常は基数木が必要です。バイナリツリーは機能しますが、プレフィックスを使用してアドレスの範囲を格納する機能はありません10.*。ルーティングに似たものにこれを使用していない場合、またはサブネット全体を何かにマッピングするスペースを節約する必要がない場合。

だから私の質問は-リストからの複数の要素に基づいてキーを生成し、ツリー内のノードを格納/検索する方法です（そうでなければ、リストを導入した後、1つのネクストホップのみに基づいてキーを持つことはできません）住所）。また、同じ質問が検索にも当てはまります。

関数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の順序関係はおそらく無意味です。バイナリ検索ツリーは、コレクションをキーの順序関係で順序付けする必要がある場合に使用されます。

于 2012-04-04T23:47:59.473 に答える