Таким образом, большинство экспертов по базам данных говорят, что это неэффективно, создавая индекс для столбца с очень небольшим количеством уникальных значений по отношению к размеру таблицы.
В зависимости от того, как базы данных работают внутри (я знаю, что большинство баз данных хранят индексы с использованием B-дерева), почему B-Tree с несколькими уникальными значениями делает поиск неэффективным?
Во-первых, вам нужно понять, как работает индекс в столбце. Простыми словами это не что иное, как
упорядоченный список всех возможных значений в данном столбце с указателем назад к фактической записи в базе данных.
Поскольку он упорядочен, вместо него можно использовать двоичный поиск, а не линейный поиск, что повышает производительность над большим набором данных.
Представьте себе, что ваш индекс как телефонная книга, заказанная столбцом, скажем last name; но в пределах набора записей с аналогичным last name для записей нет общего шаблона или значимого порядка: они упорядочены исключительно случайным образом. И скажем, что нам нужно искать эту запись:
Ike Smith 4783 Random Ave. Сиэтл, WA 98117
Поскольку телефонная книга упорядочена по last name, нам нужно только перейти к S, затем m, затем i и т.д., пока не найдем Smith. И (надеюсь) в разделе Smith есть только несколько записей, поэтому мы находим тот, который мы хотим довольно быстро.
Теперь представьте, что у вас есть телефонная книга, заказанная city вместо last name. И в пределах записей, которые соответствуют данному city, нет конкретного порядка. И поэтому мы снова пытаемся найти наш поиск. Однако, как только мы найдем Seattle (используя чрезвычайно сложный бинарный поиск), нам осталось около 620 778 записей, которые мы должны проверять последовательно, поскольку они упорядочены полностью случайными. Мы застряли, проверяя каждую запись для записи, которую хотим.
Это то, что происходит, когда вы используете очень общий столбец в качестве базы вашего индекса: двоичный поиск возвращает очень большой набор возможных записей, с которыми база данных не может делать какие-либо предположения за пределами начальных индексированных значений столбца, поэтому он должен проверять последовательно в результирующем наборе для соответствующей записи.
Если телефонная книга была вместо этого упорядочена с помощью zip code (менее распространенная переменная), вы можете найти только поиск 18 623 записей, находящихся на 98117.
Кроме того, настоящая телефонная книга обычно напоминает составной индекс: вместо простого упорядочения одним столбцом (т.е. last name) значения в результирующем наборе затем упорядочиваются другим столбцом (скажем, first name) и затем другой (middle name?), поэтому поиск может выполняться сублинейно на каждом шаге, пока не найдете нужную запись. Это в основном индекс в индексе, где даже если первый столбец не является таким общим, комбинация со вторым обеспечивает достаточно определенные критерии, чтобы поиск только небольшого набора записей выполнялся линейно.
В целом цель индекса состоит в том, чтобы обеспечить более быстрый, чем линейный, поиск, избегая необходимости сканировать значительную часть данных в таблице (см. http://en.wikipedia.org/wiki/Database_index). Если многие потенциальные индексированные значения идентичны, база данных должна сканировать значительную часть таблицы даже после успешного поиска индекса.
Таким образом, индекс, который имеет мало уникальных значений, обеспечит очень мало производительности, независимо от его реализации.
Если у вас очень мало уникальных значений, хэш (если вы используете хэш-таблицу) будет одинаковым для многих записей и не будет ускоряться. С помощью b дерева многие записи в диапазоне будут очень маленькими. В основном, вы используете не уникальные значения, вам нужно либо вернуть больше записей в качестве результатов, либо использовать больше критериев для поиска базы данных
Поскольку первичный ключ гарантированно имеет все уникальные значения, он часто индексируется
Хорошим примером является рассмотрение наихудшего случая, когда все значения одинаковы: в b-дереве или хэш-таблице вы не получаете преимущества от производительности, индексируя данные
В b-дереве индекс хранится отдельно (по крайней мере на диске) из данных. Поиск в b-дереве требует O(log n) для поиска, а другой O(1) для поиска самой таблицы.
При поиске без индекса вы обнаружите большое время поиска через сканирование таблицы, а именно O(n). Однако, когда сопоставление результатов хранится по всей таблице, поиск по индексу превышает (с точки зрения ресурсов) поиск, выполняя сканирование таблицы.
Когда у вас есть много значений, которые могут соответствовать запросу, вы создаете поиск O(log n) по индексу и поиск самих данных таблицы. Затем вы почти достигаете сканирования таблицы (поскольку последовательный поиск по большей части таблицы близок к сканированию), поэтому небольшое уменьшение сканирования таблицы по индексу меньше, чем отходы, которые ищут сам индекс.
Подробнее: Задержка поиска и поиска на дереве (на жестких дисках), где голова должна быть перепозиционирована, происходит один раз для каждого матча (с наивным подходом к поиску индекса), в то время как сканирование таблицы просто происходит один раз. Даже если данные кластеризуются в индексе, должны выполняться вычисления и сканирование, а оптимизатор запросов выбирает сканирование таблицы.
Извините за плохой организации этого поста, я работаю от недостатка сна