You can't naively store 2^63 indices, else you'll get exponential run time to insert or lookup. Using a random access memory structure like a binary tree gives

You can't naively store 2^63 indices, else you'll get exponential run time to insert or lookup. Using a random access memory structure like a binary tree gives you logarithmic run time, but for a 64-bit index and 64-bit pointers will cost you 3x the space, so now your index is larger than your source data. And since you probably don't have random access memory, but instead have random block access, you'll need to use something like a b-tree to avoid getting destroyed by seek times, and this has a further space overhead - you're now more like 6-8 times larger than the source data. You may as well merge sort the 64-bit source data (indices) at O(nlogn) time and constant space costs.