If I have a very large table with an IDENTITY column (bigint) and this table is subject to deletes, will the fragmentation of the address space (the available IDs) result in slower SELECTS?
Clarification:
By address space fragmentation I mean the gaps left in the values in the ID column, not the fragmentation on the disk that occurs when deleting rows from the table.
Obviously, this can’t be known for certain without running tests. However, I will speculate that it would not run any faster or slower if it is contiguous or fragmented.
Assuming that your column is indexed—SQL Server stores indexes in a b-tree. The nodes of this tree are designed to be of optimal size for the system’s paging system. A search within the node is going to identify the correct child-node pages regardless of the fragmentation of the indexes. Since the time it takes to load the pages is going to swamp the time it takes to search within the nodes, I don't think fragmentation will have any effect on the lookup times.
If the column is not indexed, on the other hand, then SQL Server has to do a full table scan anyway, so the distribution of values is not going to affect the time at all.
The one place that it could have an effect is on query plan optimization. SQL Server stores histograms of column contents so that it may choose a query plan that will give adequate performance. It seems possible to me that fragmentation could cause it to choose a plan that is not as good as another plan that it might have considered. This would be the case if the column statistics are not up-to-date. If the statistics are up-to-date, then the fragmentation would be detected, and the optimizer could take that information into consideration.