vdsadmin

apt-get update
apt-get install mysql-server mysql-client libmysqlclient15-dev
Если на сервере менее 150мб памяти, установка не закончится и вылетит большой и страшный fail.
Это не страшно. Правим конфиг редактором nano
nano /etc/mysql/my.cnf
Приведу изменённые части конфига:

#
# * Fine Tuning
#
key_buffer              = 16K
max_allowed_packet      = 2M
thread_stack            = 64K
thread_cache_size       = 4

И самое главное, что нужно сделать - раскомментировать строку #skip-innodb
skip-innodb

Если у вас Mysql на предыдущем шаге не запустился, сделайте следующее
apt-get install mysql-server mysql-client libmysqlclient15-dev –reinstall
если это не помогло, удаляем записи по данным пакетам и «ставим» их снова

cd /var/lib/dpkg/info
rm mysql*
apt-get -f install 
dpkg --configure -a

Проверяем:
apt-get install mysql-server mysql-client libmysqlclient15-dev - Должно сказать, что все уже установлено и ставить нечего :)
Обезопасим mysql:
mysql_secure_installation