>> How do vendors actually implement auto-clustering? I assume
>they move
>> rows around during quiet periods or have lots of empty space in each
>> value bucket.
>
>
>As far as I know, Oracle does it by having a B-Tree organized heap (a
>feature introduced around v8 IIRC), basically making the primary key
>index and the heap the same physical structure. Any non-index columns
>are stored in the index along with the index columns. Implementing it
>is slightly weird because searching the index and selecting the rows
>from the heap are not separate operations.
Almost the same for MSSQL. The clustered index is always forced unique.
If you create a non-unique clustered index, SQLServer will internally
pad it with random (or is it sequential? Can't remember right now) data
to make each key unique. The clustered index contains all the data
fields - both the index key and the other columns from the database.
It does support non-clustered indexes as well on the same table. Any
"secondary index" will then contain the index key and the primary key
value. This means a lookup in a non-clustered index means a two-step
index lookup: First look in the non-clustered index for the clustered
key. Then look in the clustered index for the rest of the data.
Naturally a non-clustered index needs better selectivity before it's
actually used than a clustered index does.
IIRC, SQL Server always creates clustered indexes by default for primary
keys.
//Magnus