An index is almost always useful, even for a primary key.
The one place that no index is needed to take advantage of a primary record key is in a relative file where all data is accessed by an address relative to the beginning of the file. So, if you have fixed length records and record numbers running from 0, 1, 1, ... and up), all one needs to do to calculate the relative address is to multiple the record number by the length.
If there any variable length records, or if the records are not written sequentially to the file in block format, then an index is mandatory. The primary index is tree'd and the ranges of keys of records kept in each data block are stored in the index. Thus, finding records is accomplished by bopping through the tree. Indexes, especially primary indexes are used by many sql implementations to obtain SELECT COUNT.
