dict is usually close enough – what do you want that it doesn’t do?
If the answer is “provide order”, then what’s actually wrong with for k in sorted(d.keys())? Uses too much memory, maybe? If you’re doing lots of ordered traversals interspersed with inserts then OK, point taken, you really do want a tree.
dict is actually a hash table rather than a b-tree. But then map isn’t defined to be a b-tree, so it doesn’t let you do things like detaching sub-trees as a new map, it just has the same performance complexities. All that’s really left to worry about is what happens to dict when there are large numbers of hash collisions, but it must be pretty rare to use Python in situations where you want tight worst-case performance guarantees.