How is combined index implemented in SQL Server

Question

I understand how single indexed column works in SQL Server and how it is implemented using balanced trees. There are plenty of interesting videos on YouTube on this topic. However I don't understand how it works if the index is based on multiple columns. For example:

CREATE NONCLUSTERED INDEX idxItemsCatState
ON Items (Category,OfferState)
INCLUDE ([Id],[Ranking])

And how it can speedup query like

SELECT ID, Ranking FROM Items where Category = 1 AND OfferState < 3

It is still implemented as B-Tree? How it can evaluate the combination of values? What are the restrictions for such feature?

Answer 1

To store rows in a b-tree and perform a seek, all that is needed is an ordering in which the rows should be sorted. Just like you can sort on (Category), you can also sort on the tuple (Category, OfferState). In the latter case, rows are first sorted by Category and then any ties are broken by sorting by OfferState.

The resulting index will use the same b-tree structure, but the value for each entry in the b-tree will be a (Category, OfferState) tuple.

And how it can speedup query like...

For your query, SQL Server can perform a seek in the following way:

• Seek to the first row that matches Category = 1. This can be done using the same b-tree seek you are familiar with, with SQL Server only needing to use the Category portion of each (Category, OfferState) tuple.
• Begin reading rows, and continue until a row with OfferState >= 3 is found

In this way, SQL Server will be able to seek directly to the beginning of the range of rows that are needed, read those rows, and stop at the end of the range of rows. Note that you can see how this seek works by looking at the Seek Predicate property of the Index Seek operator in your query plan.

More generally, a multi-column index across columns (a, b, c, d, ...) can support a seek on any leading subset of columns, such as (a) or (a, b, c), when you are matching for equality (using =).

If you are looking for a range (e.g., b < 3), SQL Server can no longer seek on any columns that fall later in the index. In such a case, it would have to perform a separate seek within each distinct value of b, which is not supported (except in a more specific case you probably don't need to worry about: across partitions of a partitioned table).

Answer 2

Traditional indexes are implemented as B-trees, whether single or multi column key.

And how it can speedup query like

SELECT ID, Ranking FROM Items where Category = 1 AND OfferState < 3

The order of composite index keys is significant for query optimization. Specify column(s) used in equality predicates first (in order of selectivity), followed by column(s) used with inequality predicates. This will facilitate touching only those rows that match the equal condition, and then access rows within the specified range. So for this query, the column order in the index should be Category and OfferState rather than vice-versa.

Answer 3

Logically, the individual columns are put into a tuple (Category, OfferState). Those tuples are the index keys and the b-tree algorithm works unmodified.

B-trees do not need any kind of "condition". They work on any value domain that has a total order defined. The only operations that is ever being done in a data structure sense is to compare two keys. SQL Server in addition uses two more operations: serialization to bytes and deserialization from bytes.

• Tomas Kubes: I understand of comparison of one key. But what if the comparison of one key of tuple is true and second key is false? Is the B-tree going left or right? Or does need to be scanned entire subtree?
• usr: @qub1n the tuples are compared as a whole. The first non-equal value determines the outcome. (a, 3) is smaller than (a, 4). The b-tree itself does not care about how tuples are compared.