Question on searchable database project design

I am working on a project that involves creating a database from entries containing a name, phone number, birthday, and other related information. My current design is to create a Record class to hold all of the info and then place objects into nodes in a binary search tree. Currently I am reading everything in as a string and sorting alphabetically. I am having difficulty conceptualizing how to make the database searchable by any of the fields. The only thing I have been able to come up with is creating multiple trees, but this seems inefficient from both a time and memory perspective. I am pretty new to C++ and this is my first data structures class, so I am only familiar with the most common data structures.

Any suggestions are appreciated. Thanks!