Okay, a bit less of a copout:

Store the data in a linear array of records. Also, have a hash of
{[axis, value] => bitvector}, where the bitvector is 1 for every
record containing that value on that axis (e.g. {[boy, jim] =>
1100000} means that of the seven records, the first two have boy:jim)

Then you simply and together the bitvectors for all your criteria and
traverse the resultant bitvector, picking out array indices.

Add/delete a record: for every axis in your new record, hash[axis,
value].bitvector.toggle(record.index)

Note that deletion leaves gaps you cannot compact, though you can
maintain a subsidiary datastructure pointing to deleted records so
they can be reclaimed one by one

martin