>My understanding of SQL server is that there is no notion of _natural_ order as their is with xbase tables. SQL optimizes as it sees fit.

This is not true. As Dan said, you can sort the records in a SQL Server table by creating a clustered index. Creating a clustered index physically sorts the reocrds in your table to adhere to the index. Non-clustered indexes are just pointers to the records.

Clustered indexes do not have to be created on the primary key. In fact, in a lot of cases, it is a performance killer to do that. For example, if you perform a lot of queries on customer name then you should think about having a clustered index on this field. The reason being in the way SQL Server stores and retrieves data. Records (rows) are stored on pages and the key to performance is to retrieve as few pages as possible. If the clustered index is on the primary key, then all records will be appended to the end of the table (last row of the last page). If you want to query something, then pages with recently added rows (records) adhering to your search criteria will have to be retrieved. If you have a clustered index on the criteria then SQL Server only has to return a few pages and search performance is fantastic.

However, new record addition performance could be total crap. Whenever you add a new record, the record must be inserted into the table. This could mean moving rows around, creating new pages, etc. This is one of factors you need to concern yourself with when creating indexes.