"Computers are really fast at sequential scans, less so at random-access stuff." This is true if you're simple talking about raw IO throughput, but in terms of

"Computers are really fast at sequential scans, less so at random-access stuff." This is true if you're simple talking about raw IO throughput, but in terms of algorithmic searching the truth is almost exactly the opposite. For example, to find a record in a 100 million record table with a unique key using sequential search would require on average a scan of 50 million records. To access the same record when that key is indexed requires accessing/testing a maximum 23 or 24 entries in the index (2^23 is roughly 10M) and then direct access of the exact record needed in the table. Indexes are used because they speed things up exponentially, even though it may be true that random access IO is much slower than sequential IO. People, I suspect, also have much higher throughput when scanning sequentially compared to random access of items. But imagine trying to find the single person in a copy of the Manhattan white pages (is there still such a thing?) with the name 'Horace Greeley'. Would you prefer to scan sequentially from the beginning (no use of an index) or make use of the fact that white page phone books are indexed by lastname, firstname? Of course, because sequential scanning is so much faster than random access it will always be faster on tiny tables. It will depend on the system and record size, but I'm guessing indexing will take over as faster method as table size grows beyond 5k records or so, give or take an order of magnitude. Not sure of exact numbers but you get the idea. As number of records goes up from there the speed advantage of indexing over scanning grows at exponential rate.