Searching a name field

I currently manage a MySQL database with about 30000 records. I've given my users the ability to search the name field by pattern. For example, the name field can hold 36 characters and contains first name, middle initial and last name. example: NAME John D Miller Jr. Harry B Davis Angela De La Cruz Users can search for "Miller" or "B Davis" or "a De La" Our company is getting ready to purchase a database with 20 million records. I've been told that this type of reach will take too long and that I need to parse out the name field into First name, MI, Last name and suffix. Then allow users to search by first name or last name or both. Is this true? Do I need to parse out the name into different fields? Is there any way to do a pattern search and do it efficiently inside of 1 name field?