> "records should be sorted by date of birth."

What's wrong with C#'s:

    System.Collections.Generic.SortedList<DoBDateTime, PersonRecord>

?