What are your actual requirements? Do you need a balanced tree, or on-disk storage or what? For example could you just use a perl hash and track min/max key values during insertion? Or just from time to time process a sorted list of the hash keys? The following trivial code on my laptop takes 1.2s to create the hash and a further 1.2s to find the current smallest and largest keys.

my %data;
for (1..2_000_000) {
    $data{$_} = "some random text $_";
}
my ($min, $max) = (sort { $a <=> $b } keys %data)[0,-1];
[download]

Dave.