I'd be tempted to throw this thing into three hashes: one keyed by category, one by name, one by address. You can throw them into a closures to give you controlled access to them:

{
  my %n;
  my %c;
  my %a;

  sub addrecord ($$$) {
    my ($n,$c,$a) = @_;
    my $r = [$n,$c,$a];
    push @$n{$n},$r;
    push @$c{$c},$r;
    push @$a{$a},$r;
  }
  sub getbyname($) {
    my $n = shift;
    return @$n{$n};
  }
  sub getbycat($) {
    my $c = shift;
    return @$c{$c};
  }
  sub getbyaddress($) {
    my $a = shift;
    return @$a{$a};
  }
}
[download]

I haven't tested the above, and I might have some of the reference syntax wrong, but it should be clear how that works, and that you can lookup by any of category, name, and address, and allows a many-to-many-to-many relationship.

Would this serve your need?