> Could the AVL tree approach be extended to apply to dictionaries
> containing keys of any single type that supports comparison?  That
> approach would autodetect UserString or similar and support it
> properly.

I think we would need a place to store the single key type, which,
from an ABI point of view, might be difficult to find (but we could
overload ma_smalltable for that, or reserve ma_table[0]).

In addition, I think it is difficult to determine whether a type
supports comparison, at least in 2.x. For example,

class X:
  def __eq__(self, o):
    return self.a == o.a

allows to create objects x and y so that x<y<z, yet x==z.

For 3.x, we could assume that a failure to support comparison
raises an exception, in which case we could just wait for the
exception to happen, and then flatten the dictionary and start
over with the lookup. This would extend even to mixed key
types.