Как работает индексация базы данных? [закрыто]

, Почему это необходимо?

, Когда данные хранятся на дисковых устройствах хранения, они хранятся как блоки данных. К этим блокам получают доступ в их полноте, делая их атомарной операцией доступа к диску. Дисковые блоки структурированы почти таким же способом как связанные списки; оба содержат раздел для данных, указатель на местоположение следующего узла (или блок), и оба не должен быть сохранен непрерывно.

Вследствие того, что много записей могут только быть отсортированы на одном поле, мы можем заявить, что поиск на поле, что отсортированный isn’t требует Линейного Поиска, который требует N/2 доступы блока (в среднем), где N количество блоков, которые охватывает таблица. Если то поле является неполем ключа (т.е. doesn’t содержат уникальные записи), тогда, вся табличная область должна искаться в N доступы блока.

принимая во внимание, что с отсортированным полем, Двоичный поиск может использоваться, который имеет log2 N доступы блока. Также, так как данные отсортированы, учитывая неполе ключа, остальная часть таблицы doesn’t должна искаться дублирующиеся значения, когда-то более высокое значение найдено. Таким образом увеличение производительности является существенным.

, Что индексирует?

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

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

, Как это работает?

Во-первых, let’s обрисовывают в общих чертах схему таблицы базы данных-образца;

Field name       Data type      Size on disk
id (Primary key) Unsigned INT   4 bytes
firstName        Char(50)       50 bytes
lastName         Char(50)       50 bytes
emailAddress     Char(100)      100 bytes

Примечание : символ использовался вместо varchar для обеспечения точного размера на дисковом значении. Эта база данных-образец содержит пять миллионов строк и неиндексируема. Производительность нескольких запросов будет теперь проанализирована. Это запрос с помощью идентификатор (отсортированное поле ключа) и одно использование firstName (неключ неотсортированное поле).

Пример 1 - отсортированный по сравнению с неотсортированными полями

, Учитывая нашу базу данных-образец r = 5,000,000 записи фиксированного размера, дающего рекордную длину R = 204, байты и они хранятся в таблице с помощью механизма MyISAM, который использует размер блока по умолчанию B = 1,024 байты. Число записей в блоке таблицы было бы bfr = (B/R) = 1024/204 = 5 записи на дисковый блок. Общее количество блоков, требуемых содержать таблицу, N = (r/bfr) = 5000000/5 = 1,000,000 блоки.

А линейный поиск на идентификационном поле потребовал бы в среднем N/2 = 500,000 доступы блока находить значение, учитывая, что идентификационное поле является полем ключа. Но так как идентификационное поле также отсортировано, двоичный поиск может быть проведен, требуя в среднем log2 1000000 = 19.93 = 20 доступы блока. Немедленно мы видим, что это - решительное улучшение.

Теперь поле firstName ни не отсортировано, ни поле ключа, таким образом, двоичный поиск невозможен, и при этом значения не уникальны, и таким образом таблица потребует поиска до конца точного N = 1,000,000 доступы блока. Это - эта ситуация что, индексируя цели исправить.

, Учитывая, что индексная запись содержит только индексируемое поле и указатель на исходную запись, это выдерживает обосновать, что это будет меньше, чем мультиполевая запись, на которую это указывает. Таким образом, сам индекс требует меньшего количества дисковых блоков, чем исходная таблица, которая поэтому требует, чтобы меньше доступов блока выполнило итерации через. Схема для индекса на поле firstName обрисована в общих чертах ниже;

Field name       Data type      Size on disk
firstName        Char(50)       50 bytes
(record pointer) Special        4 bytes

Примечание : Указатели в MySQL равняются 2, 3, 4 или 5 байтов в длине в зависимости от размера таблицы.

Пример 2 - индексация

, Учитывая нашу базу данных-образец [1 114] записи с индексом записывают длину [1 115] байты и использование размера блока по умолчанию B = 1,024 байты. Число записей в блоке индекса было бы bfr = (B/R) = 1024/54 = 18 записи на дисковый блок. Общее количество блоков, требуемых содержать индекс, N = (r/bfr) = 5000000/18 = 277,778 блоки.

Теперь поиск с помощью поле firstName может использовать индекс для увеличения производительности. Это допускает двоичный поиск индекса в среднем с log2 277778 = 18.08 = 19 доступы блока. Для нахождения адреса фактической записи которая требует, дальнейшее блокирует доступ в чтение, принося общее количество к [1 120] доступы блока, большая разница по сравнению с 1 000 000 доступов блока, требуемых найти соответствие firstName в неиндексируемой таблице.

, Когда это должно использоваться?

, Учитывая, что создание индекса требует дополнительного дискового пространства (277 778 блоков, дополнительных от вышеупомянутого примера, увеличения на ~28%), и что слишком много индексов могут вызвать проблемы, являющиеся результатом пределов размера файловых систем, осторожная мысль должна использоваться для выбора корректных полей для индексации.

, Так как индексы только используются для ускорения поиска поля соответствия в записях, он выдерживает обосновать, что индексация полей, используемых только для вывода, была бы просто тратой дискового пространства и время обработки при выполнении вставки или удалила бы операцию, и таким образом должна избежаться. Также, учитывая природу двоичного поиска, кардинальности или уникальности данных важно. Индексация на поле с кардинальностью 2 разделила бы данные в половине, тогда как кардинальность 1 000 возвратит приблизительно 1 000 записей. С такой низкой кардинальностью эффективность уменьшается до линейного вида, и оптимизатор запросов будет избегать использования индекса, если кардинальность составит меньше чем 30% рекордного числа, эффективно делая индекс тратой пространства.