Как работают ключи для сортировки?

Это перевод How do sort keys work? Автор: Майкл Каплан.

Ключ сортировки - это, фактически, массив байт. Его назначение - быстрое сравнение строк: если вы сравниваете значения двух ключей от строк - это будет всё равно как если бы вы сравнивали две строки. Ключи сортировки абстрагируют все данные, не относящиеся к делу (например, если вы указывали флаг NORM_IGNORECASE или CompareOptions.IgnoreCase), так что двоичные ключи для строк "AAAA", "AaAa" и "aaaa" будут одинаковыми. В общем, ключи сортировки являются отличной основой для индекса строк, вроде того, который используется в базах данных.

Но как они устроены, чтобы это работало?

Ключи сортировки имеют одинаковую архитектуру в управляемом (создаются через класс SortKey) и неуправляемом (создаются через функцию LCMapString с флагом LCMAP_SORTKEY) окружении. Эта структура описана в теме LCMapString в Platform SDK:

[все Unicode веса сортировки] $01 [все диакретические веса] $01 [все регистровые веса] $01 [все особые веса] $00

Заметьте, что ключ сортировки терминируется нулём. Это справедливо для любого значения cchSrc. Заметьте также, что даже если некоторые сортировочные веса отсутствуют в ключе (из-за наличия флагов игнорирования чего-либо), то разделители $01 и нуль-терминатор всё равно присутствуют в ключе.

Причина для такой структуры в том, что основные веса (названные Unicode-весами выше) должны иметь приоритет над вторичными весами (называемые диакретическими выше), которые, в свою очередь, должны иметь приоритет над третичными весами (называемыми регистровыми) - и так далее. Таким образом, все из нижеследующих примером истинны при использовании инвариантной локали/культуры, как описано в предыдущем посте:

AAAA   <   AAAB      (первичные отличия)
AAAA   <   AÃAA      (вторичные отличия)
aaaa   <   AAAA      (третичные отличия)
AÃAA   <   AAAB      (первичные отличия, вторичные отличия игнорируются)
AAAA   <   aaaB      (первичные отличия, третичные отличия игнорируются)
aaaaab <   aaab      (первичные отличия, длина и третичные отличия игнорируются)
ＡＡＡ  <   aaà      (вторичные отличия, особая ширина и третичные отличия игнорируются)

И так далее. Чтобы это работало, нужно, чтобы все четыре категории хранились отдельно друг от друга, и каждая часть помещается в ключ сортировки целиком или же, если какая-то часть весов игнорируется, то вся секция будет пустой.

Вы можете взять ключ сортировки, такой вот структурированный массив байт, и использовать его как индекс для строки. Сравнение двух байтовых массивов будет всегда быстрее, чем сравнение исходных строк.

Конечно же, это предполагает, что ключи сортировки вычислены заранее, как это бывает с индексом. Если это не так, и вы оцениваете, что быстрее: сравнить строки сразу или сначала вычислить ключ сортировки и сравнить ключи, то прямое сравнение строк почти всегда будет быстрее. Причина в том, что использование ключа сортировки подразумевает анализ содержимого строки целиком (и это не считая самого сравнения), когда сравнение строк напрямую остановится как только обнаружит отличие - до того, как пройдётся вся строка.

Несколько лет назад я проводил презентацию, и меня осенило, что точка зрения на прямое сравнение строк против ключей сортировок аналогична точке зрения на "retail" версию collation vs. варианта "оптовой торговли". Всего несколько человек в аудитории оценили эту аналогию - и я снова вспомнил, что мне не следует озвучивать не проверенные гениальные мысли, посещающие меня во время презентации :-)

И последнее замечание - нет, не существует такой вещи как ключ сортировки последовательного (ordinal) типа. Потому что последовательные сравнения и так происходят в двоичной манере!

This post brought to you by "р" (U+0440, a.k.a. CYRILLIC SMALL LETTER ER)