Принимая во внимание, что более высокая кардинальность означает менее эффективное хранение, но более высокую производительность чтения, потому что ему нужно перемещаться по меньшему количеству ветвей, чтобы получить любые данные, которые он ищет, чтобы сузить строки для запроса.
Более высокая кардинальность означает лучшую производительность чтения, потому что по определению требуется прочитать меньше записей.
Чтобы обработать такой запрос:
SELECT *
FROM mytable
WHERE indexed_col = @myvalue
, двигатель должен выполнить следующие шаги:
Найдите первую запись, удовлетворяющую условию.
Это делается путем обхода B-Tree
, начиная с корневой записи.
По страницам поиск осуществляется по B-Tree
ссылкам; внутри страницы поиск выполняется с использованием бинарного поиска (если ваши ключи не сжаты, в этом случае это линейный поиск).
Этот алгоритм одинаково эффективен как для столбцов с высокой, так и с низкой кардинальностью. Поиск первых 3
(в отличие от любых 3
) в этих списках:
1 2 3 4 5 6 7 8 9 10
3 3 3 3 3 3 3 3 4 4
требует тех же O(log(n))
шагов.
Обход индекса до тех пор, пока значение ключа не изменится. Это, конечно, требует линейного времени: чем больше у вас записей, тем больше вам нужно пройти.
Если вам нужна только первая запись:
SELECT *
FROM mytable
WHERE indexed_col = @myvalue
LIMIT 1
, мощность столбца не влияет на производительность чтения.
Как кардинальность влияет на производительность записи?
Каждый ключ индекса имеет скрытое дополнительное значение: указатель записи. В этом весь смысл наличия индекса: вам нужно знать, на какую запись он указывает.
Поскольку указатель записи по определению уникален, каждый ключ индекса также уникален. Записи индекса, имеющие одно и то же значение ключа, сортируются по указателю записи.
Это делается для удобства обслуживания индекса: если вы удаляете запись со значением индексированного столбца, общим для миллионов других записей, соответствующая запись индекса также должна быть удалена. Но при этом не просматривается весь миллион записей индекса: вместо этого в качестве дополнительного условия поиска используется указатель записи.
Каждый ключ индекса на самом деле уникален (даже если вы не определяете индекс как уникальный) и, следовательно, имеет максимально возможную мощность.
Итак, ответ на ваши вопросы: нет, мощность столбца не влияет на производительность записи индекса.
person
Quassnoi
schedule
08.04.2010