Something like a radix trie can give you the in-order traversal and range query aspect, while still keeping some of the nice properties of HAMTs. In practice though (for my domain, scientific floating point data), I have found that b-trees and simple sorted arrays with binary search (sadly) outperform radix tries and cleverer solutions.