Does having an index on a VARCHAR column with a lot of very similar starting values have bad performance

We seem to be having quite unusual bad performance on queries that use an index. for example the table looks like

• PK BIGINT

• ID VARCHAR(50)

• Col1

• Col2

• etc

So we need to insert a row in the database and later look it up on the ID. But the ID a third party has and we have the PK. We need to get the PK back. But a very large range of those IDs have very similar starting values. for example

• "//45-423484834893457"

• "//45-573459834589345"

• "//45-345345345345345

I am not sure how SQL Server is traversing the BTree, if it hashing the values or doing string comparisons starting at the left most position.

Could having a very large range of very similar values (at least first 4 characters are identical) lead to a poorly performing index when querying for those values?

UPDATE:

Sorry the look up query is

SELECT PK_Column FROM table WHERE ID = @ID

Marks request:

```
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 0 ms.

SQL Server Execution Times:
CPU time = 0 ms, elapsed time = 0 ms.
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 22 ms.
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 30 ms.

(1 row(s) affected)
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 0 ms.

(1 row(s) affected)
SQL Server parse and compile time:
CPU time = 0 ms, elapsed time = 0 ms.

It depends on the queries are you using. MS SQL Server use BTree indexes which are always balanced, but if you use query like this:

select * from table where field like 'some%'

and most of your records correspons to this condition, MS SQL Server can decide that it will be cheaper to use table scan instead of index scan or index lookup.

Addition: Anyway you can use computed columns to reverse your field value and create the index on it.

StackExchange Database Administrators Q#22072, answer score: 2