> it requires keys to be ordered (i.e. there must be a function that can tell whether one key is less than, greater than, or equal to another)

It doesn't, you can order by hash value. However, it's a separate question on whether the hash value is stored with each item or not.