There numerous ways to speed up the database one way is just to optimize the my.cnf file.
If you have access to this file here are some key areas I found to speed up Civi. I especially have seen huge improvements in Importing Contacts.
For example we have three servers that are all the same specs
Intel(R) Core(TM)2 CPU 6600 @ 2.40GHz
2 gigs of memory and standard sata drives (one may be NCQ for multi processing)
But out of the box the settings for in this case Ubuntu was somewhat slow. We installed CentOS on the third server
and it came out of the box a bit faster but not perfect either.
They all now benefit from this mysql setup as well as additions to php settings.
in ubuntu or debian /etc/mysql/my.cnf
in centos /etc/my.cnf
key_buffer = 64M
key_buffer_size = 32M
thread_cache_size = 64
query_cache_limit = 8M
query_cache_size = 64M
query_cache_type = 1
max_connections = 150
long_query_time = 5
log-slow-queries = /var/log/mysql/mysql-slow.log