To store million keys of million length which will be better red black tree or radix tree?

Question

I want to store multiple keys(String) of million length with their objects associated with it. Such that I have to insert in the data structure(rbtree or radix tree) very frequently and have to search quite a low number of time as compared to insert. Any reccommendations will be appreciated. Thank you.

Answer 1

Since insertion is your primary concern, then you should use a red-black tree because its insertion time complexity is logarithmically in the input size, that is O(k*log n) with log being base 2 logarithm, k is the size or length of each input and n is the amount of inputs. The radix tree's insert is linear in the size k of each input and in the amount n of inputs , that is O(k*n), which is worse than for red-black trees, unless many of the string keys share sufficiently long prefixes in order to transform n in a sub-logarithmic expression of n.