Мы все помним объяснение из учебника: «Что такое индексы в базе данных и как они облегчают задачу поиска правильных строк».
Я уверен, что большинство из вас имеют в виду что-то подобное: 
И сразу становится очевидно, насколько меньше данных нужно перебрать, чтобы найти две-три нужные строки.
Великолепно.
Только.
Ясно.
И лично мне всегда казалось, что улучшать эту схему некуда.
Пока я не познакомился с кластерными индексами.
Оказалось, что с «обычными» индексами все не так радужно.
Итак, что такое кластеризованный индекс, чем он лучше некластеризованного и как с этим справляется MySQL?
Некластеризованные индексы
Чтобы избежать путаницы, мы пока будем рассматривать простой индекс по одному полю.Упрощенно, некластеризованный индекс можно рассматривать как отдельную таблицу, каждая строка которой ссылается на одну или несколько строк таблицы с данными.
Строки в индексной таблице упорядочены и сгруппированы по значениям ключевых полей.
Представим себе простой запрос:
Без индексации вообще каждая строка будет прочитана и проверена, а строки, не удовлетворяющие условию, просто не попадут в результат. Но они будут прочитаны.SELECT * FROM `t1` WHERE `fld1` = 12;
При использовании «обычного», некластеризованного индекса задача поиска значительно ускоряется.
Во-первых , индексная таблица весит намного меньше, чем таблица данных, а значит, ее просто можно прочитать быстрее.
Во-вторых СУБД чаще всего пытаются кэшировать индексы в оперативной памяти, которая сама по себе намного быстрее, чем жесткий диск*.
Третий , в индексах нет повторяющихся строк.
Это означает, что как только мы нашли первое значение, мы можем прекратить поиск — оно же и последнее.
Четвертый , данные в индексе сортируются.
И в-третьих и в-четвертых, вместе они позволяют использовать алгоритм бинарного поиска (он же метод халвинга), эффективность которого во много раз превышает простой поиск.
* Если позволяют ресурсы, таблицу данных можно (и нужно) также кэшировать в оперативной памяти.
Однако по понятным причинам индексам и их месту в оперативной памяти принято уделять больше внимания.
Индексирование — великая сила.
Но если представить все указатели индексной таблицы на строки таблицы данных ОДНОВРЕМЕННО, то получится довольно сложная «паутина»: 
И эта паутина со множеством пересекающихся стрелок подводит нас к проблеме (она просто наглядно ее демонстрирует), которую создает некластеризованный индекс.
Фрагментация
Оптимизатор MySQL может принять решение вообще не использовать индексы для поиска небольших таблиц (до пары десятков записей — в зависимости от конкретной структуры данных и индекса).Почему? Потому что поиск методом перебора считывает данные последовательно.
А указатель в индексе относится к разным разделам данных.
А переход по ссылкам из индекса в конечном итоге может стоить дороже, чем полный поиск.
Итак, что мы имеем на данном этапе эволюции индексации? Представьте себе большую таблицу, фрагментированную с точки зрения индексации.
Поскольку данные поступали хаотично и неотсортировано, именно так они и хранились.
Теперь представьте для него индексную таблицу.
И наша старая добрая просьба: SELECT * FROM `t1` WHERE `fld1` = 12;
Что происходит? Значение находится в индексе (это быстро и просто), а строки, на которые ссылается этот индекс, считываются из таблицы данных.
Естественно, когда таблица сильно фрагментирована, становятся заметными накладные расходы на чтение из разных ее частей.
И вот тут нам пригодится.
Кластеризованные индексы
Кластеризованные индексы отличаются от некластеризованных индексов так же, как оглавление книги отличается от индекса.Алфавитный индекс (некластеризованный индекс) для точного слова (значения) дает точные номера страниц (строк в базе данных).
В оглавлении указывается диапазон страниц, соответствующий конкретной главе, в которых искомое слово уже встречается.
При этом каждая глава, если она достаточно большая, может содержать собственное оглавление.
Кластеризованный индекс — это древовидная структура данных, в которой значения индекса хранятся вместе с соответствующими им данными.
Таким образом организованы как индексы, так и данные.
При добавлении новой строки в таблицу она добавляется не в конец файла*, не в конец плоского списка, а в нужную ей ветвь древовидной структуры, соответствующую ей по сортировке.
* В разных движках и при разных настройках это может быть вообще не конец и вообще не конец файла.
Слово файл здесь означает «определенную единицу измерения данных, соответствующую одной таблице», а «конец файла» используется как символ последовательной, линейной записи.
Одним из самых мощных и производительных движков для MySQL является InnoDB. Причин этому много, и одна из них — кластерные индексы.
Самый простой способ понять, как структурированы кластерные индексы, — представить их в динамике: как они растут по мере добавления данных и как таблица начинает разветвляться.
Этап первый: плоский список
Данные в InnoDB хранятся на страницах по 16 КБ.Размер одной страницы — это максимальный размер узла нашей древовидной структуры, определяющий, в какой точке начнется ветвление.
Если вся таблица умещается на одной странице, то она сохраняется в виде плоского списка, отсортированного по ключевым полям, без отдельной индексной таблицы.
В будущем все наши данные будут представлены в точно таких же маленьких табличках, а цепочки индексных страниц соединят их в дерево.
Второй этап: дерево
Когда данные больше не умещаются на одной странице, список превращается в дерево.Страница с данными разделена на две, и в том узле (на странице), где раньше находились данные, теперь находится индекс, охватывающий обе новые страницы.
Конкретный узел в таком дереве должен включать индексы всех дочерних узлов или конечные данные, если узел является последним.
Узлы могут ссылаться друг на друга только в одном направлении: от родительского к дочернему.
По мере добавления все большего количества данных дерево будет становиться более сложным и глубоким.
И чем он крупнее и разветвленнее, тем больший выигрыш будет от такой схемы хранения данных.
Серые страницы идентичны странице первого этапа — это просто отсортированные данные, листья (конечные узлы) нашего дерева.
Синие страницы являются промежуточными узлами дерева, содержащими только индекс и никаких данных.
Стрелки отмечены пути поиска конкретных значений ключей.
Запомним наш запрос (зеленая стрелка): SELECT * FROM `t1` WHERE `fld1` = 12;
При обращении к таблице запрос попадает на первую страницу и получает индекс, который сразу же отправляет его на конечную страницу с данными, где находятся строки, соответствующие критериям поиска.
Страница уже прочитана на этапе поиска, все данные собраны, база данных может вернуть ответ. Однако индекс, указывающий на другую страницу, не обязательно ведет непосредственно на страницу данных.
Индекс может указывать на страницу с промежуточным индексом.
Возможно, при больших размерах таблиц базе данных придется проводить больше итераций поиска, но каждая такая итерация включает в себя минимальный объем данных, а значит, в целом поиск все равно происходит быстрее.
Здесь есть простое правило, актуальное для любого типа индекса: чем разнообразнее данные, тем эффективнее использовать индекс для поиска конкретных значений.
Поскольку данные являются частью индекса, отсортированными и целенаправленно фрагментированными, очевидно, что для каждой таблицы можно использовать только один ключ кластера.
Из этой довольно сложной логики хранения индексов и данных есть еще одно важное следствие: операции записи, а особенно изменения существующих данных ключевых полей — крайне ресурсоемкий процесс.
Попробуйте использовать поля, которые редко меняются для кластерных индексов.
Что касается сложных (составных) ключей кластера, то к ним применяется абсолютно та же схема, только данные сортируются по двум полям.
Сам индекс мало чем отличается от некластеризованного составного ключа.
Ключи кластера в InnoDB
Здесь все просто.Каждая таблица InnoDB имеет ключ кластера.
Каждый.
Без исключений.
Гораздо интереснее, какие поля для этого выбраны.
- Если в таблице указан ПЕРВИЧНЫЙ КЛЮЧ, то это он.
- В противном случае, если таблица имеет УНИКАЛЬНЫЕ (уникальные) индексы, это первый индекс.
- В противном случае InnoDB самостоятельно создаст скрытое поле с суррогатным ID размером 6 байт.
И не забывайте, что InnoDB хранит полный набор значений полей ключа кластера во вторичных ключах как ссылку на последнюю строку таблицы.
Чем больше первичный ключ, тем больше вторичные ключи.
Теги: #Кластерный индекс #MySQL #InnoDB #кластерные индексы #MySQL
-
Аутизм
19 Oct, 24 -
Получение Постоянного Дохода В Интернете
19 Oct, 24 -
Бизнес, Поехали...
19 Oct, 24 -
Opera Открыла Сайт Для Разработчиков
19 Oct, 24
