B-tree (balanced however you like), or a sorted list of elements, or a skip list of sorted elements. You could also do a hash table of elements if there aren't

B-tree (balanced however you like), or a sorted list of elements, or a skip list of sorted elements. You could also do a hash table of elements if there aren't too many unique elements i.e. O(sqrt(totalElems) Those are the traditional things I can come up with. I couldn't tell you how to balance a B-tree, just that red-black trees are apparently great for it. I couldn't tell you which database uses what, and I wouldn't dare claim my list is complete. I'd say the question is so open as to be unclear.