什麼是有效的數據結構來讀取/寫入IPv6地址範圍以快速查找時間？

我試圖想到一個有效的數據結構，我可以用它來存儲IPv6地址範圍。查找時間應該很快。也就是說，給定一個IPv6地址，我應該能夠快速確定它來自哪個時間間隔。就我而言，地址範圍不會重疊。什麼是有效的數據結構來讀取/寫入IPv6地址範圍以快速查找時間？

一種有效的方法是創建一個簡單的二叉搜索樹，並且每個非葉節點只是「重定向查找流量」。然而，使用這種方法的問題在於，BST的大小會非常大，可能大約爲2^128個節點，我可能無法讀取/寫入文件。

那麼，我可以使用哪種數據結構進行快速IPv6地址查找，該文件也具有較低的文件大小上限？

我正在使用Java的方式。

來源

2017-08-07 Ahmad

你可以使用第三方庫？番石榴的RangeSet適用於此。 –

如果範圍不重疊，則可以使用散列表。 –

不是我的專業領域，但是... Postgres數據庫具有內置的本地[網絡地址數據類型]（https://www.postgresql.org/docs/current/static/datatype-net-types.html）提供[與這些地址一起工作的功能]（https://www.postgresql.org/docs/current/static/functions-net.html），我猜測可以執行範圍搜索。 –

這裏有一個非常好的數據結構，稱爲區間樹。它基於一個普通的二叉搜索樹。但是，它不是存儲密鑰，而是存儲間隔。並支持查找值。它可以返回找到密鑰的節點。由於節點包含其邊界，因此可以輕鬆實現您的用例。

看一看https://en.wikipedia.org/wiki/Interval_tree

來源

2017-08-07 19:15:00

謝謝。任何想法什麼是最多需要的節點數目的理論上限？ – Ahmad

我不知道心臟的上限。不過，我已經看到維基百科文章中有示例java代碼。你可以隨時複製/粘貼代碼，並簡單地寫一個測試來找出界限。或者做一些Google搜索。 –

如果你沒有定義有關IPv6的間隔，那麼你可以使用特里數據結構，我相信。

一些關於嘗試實現的文檔。

來源

2017-08-07 19:57:01 Oguz

什麼是有效的數據結構來讀取/寫入IPv6地址範圍以快速查找時間？

回答

相關問題