php performance

I'm running php4 on apache on linux. I'm having performance problems with php getting data from the mysql database. With one user at a given instant, performance is fine, even with the massive size of the data table. But when do very rudimentary load testing (basically, opening a few browser and performing the same requests), the performance is awful. I suppose the issue is with mysql, but I can't be sure. What are some solutions to performance issues such as these? I've already done mysql indexing, which is how I got the current level of performance. But again, performance is unsatisfactory with just a few simultaneous requests. Thanks in advance.