2 edited tags
| link
    Post Migrated Here from stackoverflow.com
1
source | link

B-tree node split strategy in SQL Server for monotonically increasing value

Consider a B-tree index on a value that will always increase monotonically, e.g. a column of type IDENTITY. With a conventional B-tree implementation, whenever a node is full, it will be split 50%/50% and we end up with a B-tree in which (almost) all nodes will be only 50% full.

I know that Oracle discovers when a value is ever-increasing and in these cases Oracle performs a 90%/10% split instead. That way, (almost) all nodes will be 90% full and a far better page utilization is obtained for these, quite common, cases.

I have not been able to find documentation for a similar feature in SQL Server. However, I have performed two experiments in which I inserted N random integers, and N consecutive integers in an index, respectively. The former case used far more pages the latter.

Does SQL Server provide a similar functionality? If so: can you point me to some documentation on this feature?

UPDATE: It seems, by the experiments provided below, that leaf nodes are kept un-splitted and internal nodes are split 50%/50%. That makes B-trees on increasing keys more compact than on random keys. However, the 90%/10%-approach by Oracle is even better, and I still look for some official documentation that can verify the behavior seen in experiments.