Что такое index в базе данных

Что такое индексы базы данных (для начинающих)?

Многие слышали о том, что индексы в базах данных это весьма полезная штука. Но, одно дело слышать, а другое представлять себе их устройство хотя бы на базовом уровне. Поэтому в рамках данной статьи для начинающих, я рассмотрю этот вопрос, применяя простые и понятные каждому выражения и аналогии из жизни.

Что такое индекс базы данных и зачем он нужен?

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

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

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

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

Теперь, представьте себе, что речь идет не об одной полочке, а об огромном помещении, где находятся тысячи книг.

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

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

Таким образом, чтобы найти одну или все нужные книги по названию, вам достаточно открыть этот каталог и быстро пролестнуть до нужной страницы, а затем пройтись по всем указанным стеллажам. При этом для упрощения, вы так же можете первые буквы названий так же индексировать. То есть добавляете наклейку на каждую первую страницу с указанной буквой (таким образом можете сразу перейти, например, к букве «Р», не пролистывая все названия до нее).

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

Так вот, в данном примере, если переносить это в базу данных:

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

Поиск книги — это sql-запросы получения данных. При этом важно отметить, что сами по себе они не меняются. То есть вам как нужно было найти «Термодинамику», так и осталось нужным найти «Термодинамику». Другое дело, как вы будете это осуществлять — прочесывая тысячи книг или открыв каталог.

Каталог — это и есть упрощенный вариант индекса в базе данных. То есть, индекс это набор дополнительных данных, записанных в удобном виде, который позволяет существенно быстрее осуществлять поиск, хоть и требующий дополнительных усилий для поддерживания его актуальности.

Имя книги (страничка) — это ключ в индексе. То уникальное значение, которое может ссылаться как на одну какую-то запись, так и на несколько. Стоит отметить, что даже если записей для каждого значения будет несколько, это все равно быстрее, чем полный перебор всех данных.

Если суммировать, то можно увидеть, что наличие индекса может быть весьма выгодным. Например, для одной домашней полочки с десятком книг — индекс в общем-то не сильно нужен, а вот когда речь заходит о более больших объемах, то индекс будет весьма полезным.

Так же можно заметить, что добавление индекса не требует того, чтобы сами sql-запросы были переписаны, так как последние являются лишь выражением на упрощенном языке для базы данных. Если продолжить аналогию, то это как попросить кого-то найти вам «Флора и фауна». При этом каким образом и сколько этот кто-то будет искать книгу, будет решать сам этот человек. В данном примере «найти книгу» — это sql-запрос, а этот «кто-то» это база данных.

Какие бывают индексы?

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

Дерево (древовидный индекс) — это специального вида структура, у которой есть корневая вершина и у каждого узла может быть несколько дочерних узлов. При этом каждый узел встречается только один раз и может иметь всего один родительский узел. Выглядит это так:

Как видите, очень похоже на перевернутое обычное зеленое дерево, у которого ветки растут не вверх, а вниз.

Максимальное количество дочерних узлов, как вероятно уже догадались по картинке, это то количество дочерних узлов, больше которого у одного узла не может быть.

Теперь поясню откуда берется логарифм. Дело в том, что дерево обычно заполняется по определенным правилам. К примеру, если у узла максимально может быть всего два дочерних узла (так называемое бинарное дерево), то обычно левый дочерний узел имеет значение меньше текущего, а правый большее значение. Поэтому если вам нужно найти, например, число 30 в дереве с рисунка чуть выше, то вам понадобится всего 4 сравнения (40 — 25 — 32 — 30). Именно из-за этой особенности поиска и берется логарифм (так как каждое сравнение сокращает количество проверяемых элементов в два раза). При этом обычно значение логарифма округляют в большую сторону.

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

Как видите, чтобы здесь найти запись с ключом «3» понадобится 4 сравнения (40 — 25 — 10 — 3), хотя всего записей 5.

Практически во всех базах данных, существует деление по уникальности:

Уникальный индекс — это такой индекс, у которого все значения встречаются только один раз. Проводя аналогию, когда каждая книга присутствует только в одном экземпляре и никогда названия книг не совпадают.

Неуникальный индекс — это такой индекс, у которого значения могут повторяться. Проводя аналогию, существуют книги с одними и теми же названиями, но разными авторами, или же просто встречаются копии.

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

Так же стоит знать, что индексы делятся по количеству входящих в них полей:

Обычные индексы — состоят из одного поля. Здесь, вероятно, все понятно. Обычный каталог страничек.

Составные индексы — строятся по нескольким полям, при этом расположение полей является важным.

Чуть подробнее про составные индексы. Рассмотрим аналогию с теми же книгами. До этого индекс строился только по названию. Теперь же представим, что книги с одинаковыми названиями часто встречаются. В такой ситуации, легко может получится, что страничка каталога будет состоять из координат сотен книг (десятки авторов и у каждого по десять копий). Бегать их всех проверять — так же немалое количество времени. Поэтому вместо того, чтобы страничка просто перечисляла все местонахождения книг, можно сделать так, чтобы странички с именами книг указывали на дополнительные каталоги, где аналогичным образом проиндексированы авторы.

Немного упрощая, поиск будет выглядит примерно так.

1. Вначале вы ищите в каталоге с именами необходимую страничку с названием.

2. Затем в этой страничке смотрите, где находится соответствующий каталог с авторами.

3. Берете этот каталог и уже в нем находите страничку, где указано месторасположение всех книг с этим автором и названием.

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

Существуют и другие моменты, но чаще всего достаточно знать хотя бы эти базовые знания.

Источник

Индексы

Что такое индексы

Создание индекса

Создадим индекс на колонку dept_id в таблице employees :

На длину имен индексов также действует ограничение в 30 символов.

При создании первичного или уникального ключа в таблице Oracle создает индексы на эти колонки автоматически.

Удаление индекса

Индексы удаляются по своим именам. Удалим индекс employee_dept_id_idx :

Составные индексы

Индексы могут создаваться на несколько колонок. Такие индексы называются составными.

Составные индексы можно добавлять тогда, когда в таблице ищут данные сразу по нескольким колонкам. Порядок колонок в составном индексе важен. Однозначного правила, которое бы работало всегда, нет, но чаще всего следует добавлять колонки в индекс в порядке:

То в таком случае можно попробовать добавить составной индекс, состоящий из колонок emp_name и job_code :

Порядок колонок в индексе не обязательно должен совпадать в порядке встречи колонок в условии запроса; Исходим мы здесь из того предположения, что:

До версии 9i порядок колонок в индексе был более важен, т.к. обязательным условием использования индекса было обращение в запросе к колонке, которая является первой в индексе. В нашем случае, если бы мы написали запрос следующим образом:

Index skip scan

Начиная с версии 9i в Oracle появилась возможность использовать составной индекс, даже если его лидирующая колонка не используется в запросе.

Index skip scan может использоваться тогда, когда количество уникальных значений лидирующей колонки индекса относительно невелико. Опять же, решение об использовании или неиспользовании принимает оптимизатор Oracle.

По-прежнему, лучше стараться создавать составные индексы таким образом, чтобы лидирующая колонка использовалась чаще всего, так как наличие возможности использования index scip scan вовсе не означает, что он будет использован всегда.

Зачем использовать составные индексы

Уникальные индексы

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

Когда нужно создавать индекс

Однозначно ответить на этот вопрос нельзя, т.к. наличие индекса не означает, что он будет использоваться. Решение о том, использовать индекс или нет, принимает оптимизатор Oracle.

В общем случае, можно придерживаться следующих рекомендаций:

Источник

«Добавим 2 млн статей и посмотрим, что будет»: как ускорить базу данных с помощью индексов

Разбираемся, как ускорить работу базы данных приложений и сайтов, что такое индексы и как они устроены. Пособие для начинающих backend-разработчиков.

PHP-разработчик digital-агентства «Атвинта», в свободное время пишу на Go/C#/C++. Нравится проектировать и продумывать highload-системы.

Базы данных — это совсем не сложно, даже новички быстро вливаются в тему и начинают работать практически без проблем. А что сложного? Есть таблицы, в них записываем строки — всё просто. Да, и всё работает, никто не жалуется. Пока не наступит момент… когда данных будет много.

Тут нам и приходят на помощь индексы. Во всех базах данных они работают примерно по одному и тому же принципу. В этой статье я буду использовать MariaDB.

Запрос на выборку без индексов

Рассмотрим на простом примере. Есть таблица articles со следующей структурой:

Добавим в таблицу несколько записей:

И сделаем следующий запрос:

Ничего удивительного: простой запрос и выполняется быстро. Но что будет, если данных «чуть-чуть» больше? Давайте добавим, например, 2 млн статей.

И повторим запрос на выборку:

Как видим, время выполнения запроса увеличилось. Хоть и две секунды, но это долго. И нагрузка на диск высокая.

Две секунды на выполнение запроса — не предел; когда данных ещё больше, всё будет ещё хуже. Оптимизировать этот запрос можно с помощью индексов.

Запрос на выборку с индексом

Создаем индекс по колонке views из таблицы articles.

И повторяем запрос:

Вот! Так намного лучше. Выборка проходит так же быстро, как и с тремя записями. В чём же подвох? Как это работает и почему? Что может пойти не так?

Как устроен запрос без индекса и с ним

Запрос к выборке БД без индекса

Что происходит, когда мы запрашиваем данные? А что вы делаете, когда ищете нужную вам строку в таблице? Да, база данных сканирует всю таблицу и выбирает те записи, которые попадают под условия.

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

Запрос к выборке БД с индексом

Я часто встречаю, что индекс путают с id или уникальным идентификатором, считают, что это одно и то же. Это не так! Индекс в базах данных — это другое.

Индекс, который мы создали, представляет из себя такую структуру данных, как B-дерево. Но, например, в InnoDB используется B+-дерево. Всё зависит от подсистемы хранения, а в целом принцип их работы похож. Это дерево строится по колонке views из таблицы articles.

Чтобы понять, как происходит выборка с индексом, нужно знать, как работает B-дерево.

Перед нами B-дерево индекса. В каждом узле хранятся элементы со значениями; в нашем случае это значения из поля views. Также элементы хранят ссылку на строку в таблице.

Поиск начинается с корневого узла. Наша задача — пройти по каждому элементу в узле и сравнить его значение с искомым:

Дерево из примера выше не является копией того, которое построила БД в моём случае. Это я изобразил, чтобы показать, как проходит поиск по дереву.

Рассмотрим алгоритм на примере поиска значения 2001.

То, что мы и искали. А так как искомая ячейка содержит ссылку на место, где лежат наши данные, то мы можем легко и быстро прочитать их.

Ещё один способ запроса с индексом

В данной структуре можно легко делать выборку по диапазонам, например views >= 1000. В случае таких запросов индекс также поможет.

Хоть поиск и значительно ускорился, есть и свои нюансы. Изменения в В-дереве — не самая быстрая операция.

Необходимо, чтобы все конечные узлы (листья) дерева находились на одном уровне, а количество элементов в узлах было одинаковым — тогда мы получим наивысшую скорость выборки.

Чтобы придерживаться этих условий, нужно постоянно проводить перебалансировку дерева. Это и замедляет работу.

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

Мы рассмотрели создание индекса по одной колонке (views), но в базах данных одной колонкой не ограничишься. Можно создавать составные индексы. Например, если есть поле views и дата created_at, и вы хотите делать подобные запросы: views = 1000 and created_at = «10.10.2019», то имеет смысл создать индекс по двум колонкам.

Источник

Индексы в MySQL

Индексы в MySQL (Mysql indexes) — отличный инструмент для оптимизации SQL запросов. Чтобы понять, как они работают, посмотрим на работу с данными без них.

1. Чтение данных с диска

На жестком диске нет такого понятия, как файл. Есть понятие блок. Один файл обычно занимает несколько блоков. Каждый блок знает, какой блок идет после него. Файл делится на куски и каждый кусок сохраняется в пустой блок.

При чтении файла, мы по очереди проходимся по всем блокам и собираем файл из кусков. Блоки одного файла могут быть раскиданы по диску (фрагментация). Тогда чтение файла замедлится, так как понадобится прыгать по разным участкам диска.

Когда мы ищем что-то внутри файла, нам понадобится пройтись по всем блокам, в которых он сохранен. Если файл очень большой, то и количество блоков будет значительным. Необходимость перепрыгивать с блока на блок, которые могут находиться в разных местах, сильно замедлит поиск данных.

2. Поиск данных в MySQL

Таблицы MySQL – это обычные файлы. Выполним запрос такого вида:

MySQL при этом открывает файл, где хранятся данные из таблицы users. А дальше — начинает перебирать весь файл, чтобы найти нужные записи.

Кроме этого, MySQL будет сравнивать данные в каждой строке таблицы со значением в запросе. Допустим работа ведется с таблицей, в которой есть 10 записей. Тогда MySQL прочитает все 10 записей, сравнит колонку age каждой из них со значением 29 и отберет только подходящие данные:

Итак, есть две проблемы при чтении данных:

3. Сортировка данных

Представим, что мы отсортировали наши 10 записей по убыванию. Тогда используя алгоритм бинарного поиска, мы могли бы максимум за 4 операции отобрать нужные нам значения:

Кроме меньшего количества операций сравнения, мы сэкономили бы на чтении ненужных записей.

Индекс – это и есть отсортированный набор значений. В MySQL индексы всегда строятся для какой-то конкретной колонки. Например, мы могли бы построить индекс для колонки age из примера.

4. Выбор индексов в MySQL

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

Рассмотрим запрос из примера:

Нам необходимо создать индекс на колонку age:

После этой операции MySQL начнет использовать индекс age для выполнения подобных запросов. Индекс будет использоваться и для выборок по диапазонам значений этой колонки:

Сортировка

Для запросов такого вида:

действует такое же правило – создаем индекс на колонку, по которой происходит сортировка:

Внутренности хранения индексов

Представим, что наша таблица выглядит так:

После создания индекса на колонку age, MySQL сохранит все ее значения в отсортированном виде:

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

Уникальные индексы

MySQL поддерживает уникальные индексы. Это удобно для колонок, значения в которых должны быть уникальными по всей таблице. Такие индексы улучшают эффективность выборки для уникальных значений. Например:

На колонку email необходимо создать уникальный индекс:

Тогда при поиске данных, MySQL остановится после обнаружения первого соответствия. В случае обычного индекса будет обязательно проведена еще одна проверка (следующего значения в индексе).

5. Составные индексы

MySQL может использовать только один индекс для запроса (кроме случаев, когда MySQL способен объединить результаты выборок по нескольким индексам). Поэтому, для запросов, в которых используется несколько колонок, необходимо использовать составные индексы.

Рассмотрим такой запрос:

Нам следует создать составной индекс на обе колонки:

Устройство составного индекса

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

значения составного индекса будут такими:

Это означает, что очередность колонок в индексе будет играть большую роль. Обычно колонки, которые используются в условиях WHERE, следует ставить в начало индекса. Колонки из ORDER BY — в конец.

Поиск по диапазону

Представим, что наш запрос будет использовать не сравнение, а поиск по диапазону:

Тогда MySQL не сможет использовать полный индекс, т.к. значения gender будут отличаться для разных значений колонки age. В этом случае база данных попытается использовать часть индекса (только age), чтобы выполнить этот запрос:

Сортировка

Составные индексы также можно использовать, если выполняется сортировка:

В этом случае нам нужно будет создать индекс в другом порядке, т.к. сортировка (ORDER) происходит после фильтрации (WHERE):

Такой порядок колонок в индексе позволит выполнить фильтрацию по первой части индекса, а затем отсортировать результат по второй.

Колонок в индексе может быть больше, если требуется:

В этом случае следует создать такой индекс:

6. Использование EXPLAIN для анализа индексов

Инструкция EXPLAIN покажет данные об использовании индексов для конкретного запроса. Например:

Колонка key показывает используемый индекс. Колонка possible_keys показывает все индексы, которые могут быть использованы для этого запроса. Колонка rows показывает число записей, которые пришлось прочитать базе данных для выполнения этого запроса (в таблице всего 336 записей).

Как видим, в примере не используется ни один индекс. После создания индекса:

Прочитана всего одна запись, так как был использован индекс.

Проверка длины составных индексов

Explain также поможет определить правильность использования составного индекса. Проверим запрос из примера (с индексом на колонки age и gender):

Значение key_len показывает используемую длину индекса. В нашем случае 24 байта – длина всего индекса (5 байт age + 19 байт gender).

Если мы изменим точное сравнение на поиск по диапазону, увидим что MySQL использует только часть индекса:

Это сигнал о том, что созданный индекс не подходит для этого запроса. Если же мы создадим правильный индекс:

В этом случае MySQL использует весь индекс gender_age, т.к. порядок колонок в нем позволяет сделать эту выборку.

7. Селективность индексов

Вернемся к запросу:

Для такого запроса необходимо создать составной индекс. Но как правильно выбрать последовательность колонок в индексе? Варианта два:

Подойдут оба. Но работать они будут с разной эффективностью.

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

68 rows in set (0.00 sec)

Эта информация говорит нам вот о чем:

Если колонка age будет идти первой в индексе, тогда MySQL после первой части индекса сократит количество записей до 200. Останется сделать выборку по ним. Если же колонка gender будет идти первой, то количество записей будет сокращено до 6000 после первой части индекса. Т.е. на порядок больше, чем в случае age.

Это значит, что индекс age_gender будет работать лучше, чем gender_age.

Селективность колонки определяется количеством записей в таблице с одинаковыми значениями. Когда записей с одинаковым значением мало – селективность высокая. Такие колонки необходимо использовать первыми в составных индексах.

8. Первичные ключи

Первичный ключ (Primary Key) — это особый тип индекса, который является идентификатором записей в таблице. Он обязательно уникальный и указывается при создании таблиц:

При использовании таблиц InnoDB всегда определяйте первичные ключи. Если первичного ключа нет, MySQL все равно создаст виртуальный скрытый ключ.

Кластерные индексы

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

Кластерные индексы сохраняют данные записей целиком, а не ссылки на них. При работе с таким индексом не требуется дополнительной операции чтения данных.

Первичные ключи таблиц InnoDB являются кластерными. Поэтому выборки по ним происходят очень эффективно.

Overhead

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

Создавайте только необходимые индексы, чтобы не расходовать зря ресурсы сервера. Контролируйте размеры индексов для Ваших таблиц:

Когда создавать индексы?

Самое важное

Выделяйте достаточно времени на анализ и организацию индексов в MySQL (и других базах данных). На это может уйти намного больше времени, чем на проектирование структуры базы данных. Удобно будет организовать тестовую среду с копией реальных данных и проверять там разные структуры индексов.

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

Как исправить ошибку доступа к базе 1045 Access denied for user

Основные понятия о шардинге и репликации

Настройка Master-Master репликации на MySQL за 6 шагов

Примеры ad-hoc запросов и технологии для их исполнения

Анализ медленных PHP скриптов с помощью XHprof

Типы и способы применения репликации на примере MySQL

Анализ медленных запросов (профилирование) в MySQL с помощью Percona Toolkit

Как создать и использовать составной индекс в Mysql

Настройка Master-Slave репликации на MySQL за 6 простых шагов

Синтаксис и оптимизация Mysql LIMIT

Правильная настройка Mysql под нагрузки и не только. Обновлено.

И как правильно работать с длительными соединениями в MySQL

Запрос для определения версии Mysql: SELECT version()

Check-unused-keys для определения неиспользуемых индексов в базе данных

Как работают индексы в Clickhose и как их использовать.

Анализ медленных запросов с помощью EXPLAIN

3 примера установки индексов в JOIN запросах

Что значит и как это починить

Описание, рекомендации и значение параметра query_cache_size

Быстрый подсчет уникальных значений за разные периоды времени

Использование партиций для ускорения сложных удалений

Правила выбора типов данных для максимальной производительности в Mysql

Включение и использование логов ошибок, запросов и медленных запросов, бинарного лога для проверки работы MySQL

Источник