Have you considered the performance of using [Adaptive-Radix-Tree] to further improve the performance of the IP address search? about ipaddress HOT 3 CLOSED

There are a lot of nuances to your question.

Firstly, you can easily use https://github.com/rohansuri/adaptive-radix-tree today. To use it you need keys to satisfy the following interface provided by that project:

public interface BinaryComparable<K> {
	byte[] get(K key);
}

That is easy with all the address, range, and other types in IPAddress because they all satisfy the interface AddressItem which has the method:

byte[] getBytes();

So you can use it today, easily, with all the address types in this library.

Additionally, since all address items have hashcodes, you can use them with java.util.HashSet and java.util.HashMap.

And since all address items are comparable, you can use then with java.util.TreeSet and java.util.TreeMap.

So you can use those today, easily, with all the address types in this library.

That being said, what you want to use depends on the purpose for the given collection. adaptive-radix-tree gives you a radix tree in which you can search for exact matches of addresses, and the same is true for the java collections framework types.

But that is not what you would typically want to do with IP addresses. Typically you would be testing containment in CIDR subnets, which requires matching prefixes to elements in the trie, not exact matches. Then you can do a longestPrefixMatch operation. adaptive-radix-tree does not seem to have that capability, nor does the java collections framework types.

It's possible to add such functionality to a radix trie that is not binary. But I'm not so sure there is a big advantage to that. At least, I'd need to understand the more specific requirements.

Another thing to consider is that using an "adaptive" radix trie is not such a benefit to reduce space when the radix is two, it's not much of a benefit at all. It is possible to group bits together to use a different radix, but the tries here already save space by being compact binary tries. Also, you can only save the space of one pointer per node when the trie is binary, when making it adaptive. So any spacial advantage is small. There might be performance advantages in very dense tries, but that might be quite small as well, and it might depend on address type, IPv4 vs IPv6. So I don't know what kind of advantage you'd get from an adaptive radix trie.

So you should be more specific when you say performance. Prefix match and/or containment lookup? Exact match? Of groups of what size? What is the performance difference today, if any? You need to consider these factors when improving performance. So, I would need a more specific request, rather than just a general intent to "improve the performance". Additionally, I don't see much benefit to using an "adaptive" binary trie, or a trie using a radix other than two.

from ipaddress.

Sorry for not replying to your question in time. What I want to express is that from the research results, it seems that adaptive-radix-tree has been optimized in terms of search efficiency and memory usage. If possible, is there help and optimization for these areas of use such as querying the associated object by specifying the IP address?
@seancfoley

from ipaddress.

As I said, there is very little benefit in memory usage when the radix is 2. It's not worth the effort to save a few bytes.

As for search efficiency, since the implementation in this library is a compact binary trie, the adaptive radix trie is not superior in terms of efficiency either.

But you can use it if you want, go ahead. I don't see any reason to do that, however.

And I don't understand what you mean by "querying the associated object by specifying the IP address?". You'd need to provide a concrete request, not something so vague.

from ipaddress.