With the command:
sudo apt-get remove --purge mysql\*
you can delete anything related to packages named mysql. Those commands are only valid on debian / debian-based linux distributions (Ubuntu for example).
You can list all installed mysql packages with the command:
sudo dpkg -l | grep -i mysql
For more cleanup of the package cache, you can use the command:
sudo apt-get clean
Also, remember to use the command:
sudo updatedb
Otherwise the "locate" command will display old data.
To install mysql again, use the following command:
sudo apt-get install libmysqlclient-dev mysql-client
This will install the mysql client, libmysql and its headers files.
To install the mysql server, use the command:
sudo apt-get install mysql-server