@bossek,
Brilliant idea with binary search! Thank you very much. I already adopted it in my code, searching time is now about 4us (was 20ms in the corner case).
I just would like to mention the usage of radix trees (or patricia trees) as the best solution for IP maps. It turns out that a search in this structure is at most O(K) where K is the number of bits of the input key. Compare this with the usual binary tree search O(N) where N is the number of tree nodes.
For static databases, this library may help: http://github.com/balena/radixdb
3 Likes
