java - 存储多个数字范围以供将来搜索的有效方法

Question

我有一个包含 IP 地址范围的文本文件。我使用 ip2long 将地址转换为 long，这样我就有了一种简单的方法来检查给定地址是否在范围内。但是，我正在寻找一种有效的方法来存储这些范围，然后搜索以查看 IP 地址是否存在于任何范围内。

我正在考虑的当前方法是创建一个对象，该对象具有范围的低端和高端，并具有检查值是否在范围内的功能。我会将这些对象存储在一个列表中并检查每个对象。但是，我觉得这可能有点低效，并且随着列表的增加会变慢。

有没有比我想的更好的方法？

Answer 1

以下数据结构之一可能对您有所帮助:

线段树

来自 Wikipedia ( Implementation ):

Is a tree data structure for storing intervals, or segments. It allows querying which of the stored segments contain a given point.

---

区间树

来自 Wikipedia ( Implementation ):

Is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point.

---

范围树

来自 Wikipedia ( Implementation ):

Is an ordered tree data structure to hold a list of points. It allows all points within a given range to be reported efficiently.