What's the most efficient database method to add and query usermeta?

Question

What's the most efficient way - concerning the database - to add and query extra usermeta fields to a profile?

I need to add four additional fields of numeric and text data to a user profile and then query that to compile the data for display in a template. And there are potentially thousands of users.

There are lots of examples to store the data in usermeta. But should this amount of data be stored in the usermeta table?

Or should I store it all in a new database table? And if so, how do I initialize a new table and then write to it?