> Ideally need a balanced tree like Red Black or AVL, the Perl hash takes 4 seconds

Not surprisingly, the Perl hash, at 4 seconds, is a lot faster than the (pure Perl) Tree::RB, at 33 seconds, when running your (unpublished) benchmark.

Is there any functional reason why you can't just use a hash?

Since you mentioned AVL, have you tried AVLTree from CPAN? It uses a XS wrapper around Julienne Walker's AVL Tree C library, so should be a lot faster than Tree::RB.

References

• AVL tree (wikipedia)
• Red Black tree vs AVL Tree (SO)
• AVLTree on CPAN (Perl XS wrapper around a C library)
• AVLTree latest source code (github)
• Tree::BPTree on CPAN (implements a B+ Tree in pure Perl)

Disclaimer: I have no experience using any of these, just did a quick google for you.