Term_Relationship way too big – Server Crash

Heya there,

In the past six Weeks i got many Server-Crashes from a Out of Memory Error and also DB Crashes.

I spoke to my Hoster and he told me, that some of the Tables in WordPress are way to big. For exemple, on my largest Blog ive about 16.000 Posts and the Term_Relationship measures about 130.000 Entries. Ive been told, that the query for that command takes way to long and the Server runs out of Memory.

I hope someone got a solution. Ive been told, that Indizes might help for that Problem, but ive no idea how to use em.

PS: Iam on a Virtual Server Managed with 4GB Ram. Also ive already used Clean-Up Tools for the DB like WP-optimize.