I upgraded debian to wheezy and got errors with mysql-server so I removed it. Now I can't reinstall it. I get:

$ sudo apt-get install mysql-server
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  mysql-server-5.5
Suggested packages:
  tinyca
The following NEW packages will be installed:
  mysql-server mysql-server-5.5
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 0 B/2065 kB of archives.
After this operation, 31.6 MB of additional disk space will be used.
Do you want to continue [Y/n]? 
Preconfiguring packages ...
Selecting previously unselected package mysql-server-5.5.
(Reading database ... 33290 files and directories currently installed.)
Unpacking mysql-server-5.5 (from .../mysql-server-5.5_5.5.30+dfsg-1.1_i386.deb) ...
Selecting previously unselected package mysql-server.
Unpacking mysql-server (from .../mysql-server_5.5.30+dfsg-1.1_all.deb) ...
Processing triggers for man-db ...
gdbm fatal: malloc error
Setting up mysql-server-5.5 (5.5.30+dfsg-1.1) ...
[ ok ] Stopping MySQL database server: mysqld.
insserv: warning: script 'K01exim' missing LSB tags and overrides
insserv: warning: script 'K01sendmail' missing LSB tags and overrides
insserv: warning: script 'S16libdevmapper1.02' missing LSB tags and overrides
insserv: warning: script 'exim' missing LSB tags and overrides
insserv: warning: script 'iptables' missing LSB tags and overrides
insserv: warning: script 'sendmail' missing LSB tags and overrides
insserv: warning: script 'apache' missing LSB tags and overrides
insserv: warning: script 'libdevmapper1.02' missing LSB tags and overrides
[FAIL] Starting MySQL database server: mysqld . . . . . . . . . . . . . . failed!
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.5 (--configure):
 subprocess installed post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.5; however:
  Package mysql-server-5.5 is not configured yet.

dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mysql-server-5.5
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)
$ 

Notice the somewhat worrying "gdbm fatal: malloc error".

How do I get mysql back?

Are you using dotdeb? If so, you may be SOL. (Third-party repos generally make distribution upgrades unlikely.)

If you weren't using dotdeb, this would probably be a good thing to search Debian's bug tracker for... if no bug exists, open one.

_________________

/* TODO: need to add signature to posts */

Looks like the error is that it cannot start.

What is your /etc/mysql/my.cnf ?

The upgrade to 5.5 might have some hiccups with something in your existing my.cnf that 5.5 doesn't like for some reason.

your mysql error log in /var/log/mysql* something will tell you why it didn't start.

Its likely as a consequence of apt-get install running out of memory and not completing a configure setup. Stop a few services and do the apt-get install again to see if it completes the configure step. Then look at the mysql.log.

If apt is having trouble installing perhaps you are running on too small a linode for your use. There are parameters in /etc/mysql/my.cnf that dramaticly affect memory usage. Some elements also became obsolete so there's a chance you may need to change some settings.

But hey, I use Mariadb anyway for many reasons https://downloads.mariadb.org/mariadb/repositories/

I ran into the same problem.
The following steps solved my problem for mysql-server in debian wheezy.

1. Go to http://debgen.simplylinux.ch/ to generate the source list.

2.Generate the source list.

3. Copy and paste the generated list into your /etc/apt/sources.list file. (Make a backup first!)

4.After that, run #apt-get update

Hope it helps.