問題タブ [radix-tree]

私は現在、基数ツリー データ構造から最長プレフィックス ルックアップ (LPM) を実行する実装をいくつか持っています。このデータ構造には IP プレフィックス (最大深さが 128 ビットの基数ツリー) が含まれており、現在は完全にメモリ内に保持されています。データは読み取り専用データであり、変更されることはありません。

残念ながら、データが大きくなり、メモリに保持できなくなりました。ディスク上に保持でき、効率的なルックアップを提供する効率的なデータ構造を探しています。その上でキャッシュメカニズムを使用する予定です。

フラッターアプリを書いています。このために、いくつかの場所をキャッシュする必要があり、名前を検索したいと考えています。この目的のために、基数トライを使用したいと思います。dart で実装を検索しましたが、有用なものは見つかりませんでした。

実装を見つけることができる場所を誰か知っていましたか? または、誰かが気にしたことがありますか？

挨拶ダゴバート

100 万の長さの複数のキー (文字列) を、それに関連付けられたオブジェクトと共に格納したいと考えています。そのため、データ構造 (rbtree または基数ツリー) に頻繁に挿入する必要があり、挿入に比べて非常に少ない時間で検索する必要があります。任意の推奨事項をいただければ幸いです。ありがとうございました。

パトリシアからノードを削除するにはどうすればよいですか? パトリシアとは、具体的には、検索を終了するためにツリー内で上向きのノードを持つ基数 2 ツリーを意味します。