in reply to Anyone with XS experience willing to create a high performance data type for Perl?

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];