This seemed to work for me on Perl 5.6 on Win32 and 5.8 on Linux

#!/usr/bin/perl -w
use Data::Dumper;

use strict;

my %index = ( 
    'node'            => 1,
    'node-cat'        => 2,
    'node-cat-cat'        => 3,
    'node-cat-cat-cat'    => 4,
    'node-bat-bat-cat'    => 4,
    'node-cat-cat-cat-cat'    => 5,
    'node-cat-bat-bat-bat'    => 5,
    'node-cat-cat-bat-bat'    => 2,
);

my $key;
my $test='node-cat-cat';

print Dumper \%index;

#
# DELETE all child nodes.
#
print "\nDelete children of $test\n";
foreach $key (sort keys %index){
  if ($key =~ /$test.+/){
    print "Deleting $key\n";
    delete $index{$key};
  }
}

print "\nFinal Hash:\n";
print Dumper \%index;
[download]

It outputted

$VAR1 = {
          'node-cat-bat-bat-bat' => 5,
          'node-bat-bat-cat' => 4,
          'node-cat-cat-bat-bat' => 2,
          'node-cat-cat-cat' => 4,
          'node-cat' => 2,
          'node-cat-cat-cat-cat' => 5,
          'node-cat-cat' => 3,
          'node' => 1
        };

Delete children of node-cat-cat
Deleting node-cat-cat-bat-bat
Deleting node-cat-cat-cat
Deleting node-cat-cat-cat-cat

Final Hash:
$VAR1 = {
          'node-cat-bat-bat-bat' => 5,
          'node-bat-bat-cat' => 4,
          'node-cat' => 2,
          'node-cat-cat' => 3,
          'node' => 1
        };
[download]

which is what you would expect.