Understanding about SQL index on DateTime Column

Question

I have about 1 million records. When searching through the date range, it is surprisingly slow. Then I do the google search and someone suggested to do the index on the "DateTime" column. I am not convinced because I always thought index is for O(1) search - which means equality search; and since my query is a date range search, how can it be possible to improve the performance?

But, out of curiosity, I tried anyway and to my surprise, it does improve the performance significantly.

Here is my table

tblOrder
--------
OrderId (Primary Key)
CurrencyId
ProductId
...
...
...
OrderDate DATETIME

I am using linqtosql and the code is:

return (from rec in tblOrders.AsNoTracking()
        where (rec.CurrencyId == CurrencyId) && (rec.OrderDate >= startDate) && (rec.OrderDate < endDate)
        select rec).ToList();

I created a composite index on both CurrencyId and OrderDate. The result is a huge improvement. My question is, how is it possible? Why do indexes work on range search (not equal but >= or <=).

Can someone explain to me how does SQL index work in regards to date range search?

Thank you...

Answer 1

B-tree indexes don't work by comparing only for equality. They're designed (the algorithm is designed) to use ranges.

Figure 1.3 shows an index fragment to illustrate a search for the key “57”. The tree traversal starts at the root node on the left-hand side. Each entry is processed in ascending order until a value is greater than or equal to (>=) the search term (57). In the figure it is the entry 83. The database follows the reference to the corresponding branch node and repeats the procedure until the tree traversal reaches a leaf node.

References

• The Search Tree (B-Tree) Makes the Index Fast See especially section 1.3, B-Tree traversal
• SQL Server index structure and concepts