I think you should give us little more information about your system.
What does database engine you are using (e.g. - MySQL, PostgreSQL, MonogoDB...)? And is that database some of your solutions, or some already well-known app (like Wordpress...) ?
I had a chance to work with MySQL databases, and I can say that 110 MB is nothing. I had database which size is few GB, and it was working very well.
If this is your database solution and you're using something like MySQL I would first pay attention to indexing.
In my personal experience indexing can massive improve loading and query execution time. For first look for ID fields and make sure they have Primary Keys if possible. For even more optimization, you can look for most used fields under WHERE clauses and make sure they have (index) key.
Go thought docs and read more about it, but it can really improve times.
After that you can research about query caching. It can also improve time so it's worth trying.
In case of MySQL, here you are a few links:
Optimization and Indexes
Query caching docs
If this is some known app, say what, maybe there is some known fix.
As I said, 110 MB is not big database, database usually grow very very large and works correctly. Also you have powerful server that performance should not be a problem.
Maybe with more details I or someone else can you give more details, but this is my 5-cents.