Physical ordering of records in an index

Question: I’ve been wondering about record storage in indexes and how SQL Server maintains the ordering. At what point do records get moved around on the index pages so that they’re stored in the correct order for a SELECT to retrieve them?

Answer: The simple answer is that records are not moved around to maintain ordering in an index page.

The question in email asked at length how a record would be inserted on a page (with room on the page for the record) if the key value of the record being inserted is in the middle of the range of keys on the page. The questioner assumed that some of the records on the page would have to be shuffled down to allow the new record to be inserted in the correct place.

Related: How record DELETEs can cause index fragmentation

This does not happen. The physical records can be stored anywhere on a page in relation to each other and the physical ordering does not have to match the logical (key-based) ordering. However, the records still must be accessible in key order.

SQL Server manages this by having an indirection mechanism on each page. There is a set of two-byte pointers at the end of the page called the slot array. Each entry in the slot array points to the offset of a record on the page. Although the records can be physically stored in any order, the slot array entries must be ordered such that the first slot array entry points to the record on the page with the lowest key value (assuming that the page is part of an ascending index, of course).

For example, if a page has three 400-byte records with key values and offsets as follows:

Then the slot array will also have three entries. The first will be 896, the second will be 96, and the last will be 496. Although the record with the lowest key value is stored last on the page, the slot array ensures that it is the first logical record on the page.

All accesses to records on the page are done using the slot array, so the records are always accessed in the correct logical order.

If a new record is inserted on the page with key value 5, it will be inserted at offset 1296 on the page and it will be the third logical record on the page. The slot array entry for the record with key value 7 will be moved by two bytes and the pointer for the new record inserted into the correct position in the slot array. The new slot array will have four entries – 896, 96, 1296, and 496.

The only times that records on a page are sorted into their correct logical and physical order is during an index rebuild, or when there is enough free space for a new record (or expanding) record on a page but the free space is not contiguous. In the latter case, a new copy of the page will be built in memory with the records ordered correctly and squished together to make all the free space contiguous.

Using the slot array mechanism allows SQL Server to avoid having to move records around repeatedly and make efficient use of the free space on index pages.