An elevator picks people up and moves them to different floors based on where they have requested. If an elevator picked up exactly one person on the ground floor of a building, dropped them off, and went down to get another person it wouldn’t be very efficient. Modern elevators pick up people and move them between floors in an optimal pattern. Disk access is pretty much the same idea if you think of the disk head as an elevator and the disk as a building. It takes time to move an elevator just as it takes time to move a disk head. Modern operating systems can change the order of disk accesses into a more optimal pattern.
There are many different algorithms for scheduling I/O. I’m going to cover the ones I know from linux and how they can help you make the best use of your servers disks.
CFQ (Completely Fair Queue)
CFQ maintains an i/o queue per process. Processes can post multiple reads but the CFQ scheduler will process exactly one read per process in a round robin fashion. This makes it very fair for large systems that have a lot of processing doing i/o and have multiple storage devices.
Anticipatory Scheduler (as)
This scheduler tries to read the mind of your processes. Along with scheduling i/o it watches access patterns. When it detects a process sending sequential reads to a file it will hold off on sending other requests so the next read request your process sends will return quicker. It does this without trying to be too unfair to other processes. This is great for webservers and workstations which tend to read files from top to bottom. It’s not so good for databases which tend to seek randomly in files and really on want the blocks they asked for. This is why it’s usually a good idea to turn off read-ahead.
Deadline Scheduler
The deadline scheduler is similar to anticipatory except that it tends to be better under heavy load. When multiple requests are coming in the deadline scheduler will place an expire time on each read then try to execute then in an optimal order without exceeding that time limit. If the time limit it hit for a request the deadline scheduler will force that request to be next in the queue so it can be serviced. This is good for heavy file servers but has been somewhat out dated by the anticipatory scheduler.
Noop
As it’s name implies this scheduler isn’t really a scheduler at all. It simple keeps a FIFO queue of i/o requests executing them in the same order they arrived. At first glance it seems kind of pointless but like everything else it has it’s place. Modern raid controllers can schedule their i/o more acurately than the operating systems running them because the operating system has no idea what the head is on the disk. Only the raid controller knows that. Using the noop scheduler with a raid controller can result in a nice performance boost because the raid controller will get more information with which to choose the optimal order to satisfy requests.
Basically my recomendation is.
* Desktop or webserver use anticipatory
* MySQL on ide or a raid controller not smart enough do it’s own scheduling use deadline
* MySQL on a good raid controller use noop.
This recomendation isn’t based on any hard data. I’ve never benchmarked mysql with different schedulers. If you have, please let me know 
If I get a chance to I will run some numbers.
[Update: 2006-2-1 redhat.com has a i/o scheduling article. ]
) is showing that you actually made progress on it. This alone can have more positive impact than the progress you actually made. If there is someone out there from the mysql web/docs team that has been slaving to improve the manual search please shout out.