random reads

[chintan sanghvi]

I have a single myisam table with 5Million user entries. My applications is using 20 threads to continuously "read" (read is more frequent then update) from the table. Each row on an avg has 400bytes.
I see something interesting with Myisam when i do my load testing. When i try to read user information of contiguous block of users, my read performance as benchmarked inside my application is <1mili second on an avg.
However, when i try to read user information of "random" users, my performance is severely impacted and i see the avg read time in 800 milliseconds.

My understanding is, because of the randomness, mysql must be repeatedly going back and forth to the disc for fetching data for this "random" user. And every so often it would need to flush its indexes from the cache.

1) How can i improve the performance? Use InnoDB? How will it be different?
2) Please rationalize this difference in performance!

Increasing the number of application threads connected to the mysql does not help much.