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

Зачем это нужно?

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

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

В то время как с отсортированным полем можно использовать двоичный поиск, который имеет доступ к блоку log2 N . Кроме того, поскольку данные сортируются по неключевому полю, rest таблицы не нужно искать для повторяющихся значений, как только будет найдено более высокое значение. Таким образом, повышение производительности является существенным.

Что такое индексация?

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

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

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

Во-первых, давайте набросаем пример схемы таблицы базы данных;

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

Примечание: char был использован вместо 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 блоков.

Линейный поиск по полю id потребует в среднем N/2 = 500,000 блочных обращений для поиска значения, учитывая, что поле id является ключевым полем. Но поскольку поле id также сортируется, двоичный поиск может быть проведен, требуя в среднем 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 - индексация

Приведем наш пример базы данных из r = 5,000,000 записи с индексной длиной записи R = 54 байта и использованием стандартного размера блока B = 1,024 байта. Коэффициент блокировки индекса будет составлять bfr = (B/R) = 1024/54 = 18 записи на дисковый блок. Общее количество блоков, необходимых для хранения индекса, составляет N = (r/bfr) = 5000000/18 = 277,778 блоков.

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

Когда его следует использовать?

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

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

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

С тех пор я получил некоторое представление о недостатках создания индексов: если вы пишете в таблицу (UPDATE или INSERT) с одним индексом, у вас фактически есть две операции записи в файловой системе. Один - для табличных данных, а другой-для индексных данных (и их повторное использование (а если они кластеризованы-повторное использование табличных данных)). Если таблица и индекс расположены на одном жестком диске, это требует больше времени. Таким образом, таблица без индекса (куча) , позволит быстрее выполнять операции записи. (если бы у вас было два индекса, вы бы закончили с тремя операциями записи и так далее)

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

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

В некоторых сценариях куча полезнее таблицы с индексами,

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

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

Помог мне: - что на самом деле означает кластеризованный и некластеризованный индекс?

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

Классический пример "Index in Books"

Рассмотрим "Book" из 1000 страниц, разделенных на 100 разделов, каждый из которых содержит X страниц.

Просто, да?

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

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

Но тогда, в дополнение к 1000 страницам, вам понадобится еще ~10 страниц для отображения индексной страницы, так что всего 1010 страниц.

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

В школах все просто, не так ли? :P

Теперь предположим, что мы хотим запустить запрос, чтобы найти все данные о любых сотрудниках, которые называются "Abc"?

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

Что же будет без индекса?

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

Как индекс базы данных может повысить производительность

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

Как работает индекс B-деревьев?

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

Как работает индекс таблицы hash?

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

Например, запрос, который мы обсуждали ранее, может извлечь выгоду из индекса hash, созданного в столбце Employee_Name. Индекс hash будет работать так, что значение столбца будет ключом к таблице hash, а фактическое значение, сопоставленное этому ключу, будет просто указателем на данные строки в таблице. Поскольку таблица hash в основном является ассоциативным массивом, типичная запись будет выглядеть примерно так: "Abc => 0x28939", где 0x28939-ссылка на строку таблицы, где Abc хранится в памяти. Поиск значения типа “Abc” в индексе таблицы hash и получение обратно ссылки на строку в памяти, очевидно, намного быстрее, чем сканирование таблицы для поиска всех строк со значением “Abc” в столбце Employee_Name.

Недостатки индекса hash

Hash таблицы не являются отсортированными структурами данных, и есть много типов запросов, с которыми индексы hash даже не могут помочь. Например, предположим, что вы хотите узнать всех сотрудников, которым меньше 40 лет. Как вы могли бы сделать это с индексом таблицы hash? Ну, это невозможно, потому что таблица hash хороша только для поиска пар ключевых значений – что означает запросы, которые проверяют равенство

Что именно находится внутри индекса базы данных? Итак, теперь вы знаете, что индекс базы данных создается для столбца в таблице и что индекс хранит значения в этом конкретном столбце. Но важно понимать, что индекс базы данных не хранит значения в других столбцах той же таблицы. Например, если мы создадим индекс для столбца Employee_Name, это означает, что значения столбцов Employee_Age и Employee_Address также не хранятся в индексе. Если бы мы просто сохранили все остальные столбцы в индексе, то это было бы так же, как создать еще одну копию всей таблицы – что заняло бы слишком много места и было бы очень неэффективно.

Как база данных может знать, когда использовать индекс? Когда выполняется запрос типа "SELECT * FROM Employee WHERE Employee_Name =' Abc’", база данных проверяет, есть ли индекс в запрашиваемых столбцах. Предполагая, что столбец Employee_Name действительно имеет индекс, созданный на нем, база данных должна будет решить, действительно ли имеет смысл использовать индекс для поиска искомых значений – потому что есть некоторые сценарии, где на самом деле менее эффективно использовать индекс базы данных, а более эффективно просто сканировать всю таблицу.

Какова стоимость наличия индекса базы данных?

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

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

Смотреть также

1. Какие колонки, как правило, делают хорошие коэффициенты?
2. Как работают индексы баз данных

Простое Описание!!!!!!!!!!

Индекс - это не что иное, как структура данных, которая хранит значения для определенного столбца в таблице. Индекс создается по столбцу таблицы.

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

Теперь предположим, что мы хотим выполнить запрос, чтобы найти все сведения о любых пользователях с именем "Джон". Если мы выполним следующий запрос.

SELECT * FROM User 
WHERE Name = 'John'

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

CREATE INDEX name_index
ON User (Name)

Индекс состоит из значений столбцов(например, John) из одной таблицы, и эти значения хранятся в структуре данных.
Таким образом, теперь база данных будет использовать индекс для поиска сотрудников по имени Джон, потому что индекс, по-видимому, будет отсортирован в алфавитном порядке по имени пользователя. И, поскольку он отсортирован, это означает, что поиск имени намного быстрее, потому что все имена, начинающиеся с “J”, будут находиться рядом друг с другом в индексе!

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

Просто подумайте об индексе базы данных как об индексе книги. Если у вас есть книга о собаках, и вы хотите найти информацию, скажем, о немецких овчарках, вы, конечно, можете пролистать все страницы книги и найти то, что вы ищете, но это, конечно, занимает много времени и не очень быстро. Другой вариант заключается в том, что вы можете просто перейти в раздел индекса книги, а затем найти то, что вы ищете, используя имя объекта, который вы ищете ( в данном случае немецкие овчарки), а также посмотреть на номер страницы, чтобы быстро найти то, что вы ищете. В базе данных номер страницы называется указателем, который направляет базу данных на адрес на диске, где находится объект. Используя ту же аналогию с немецкой овчаркой, мы могли бы иметь что-то вроде этого (“немецкая овчарка”, 0x77129), где 0x77129-это адрес на диске, где хранятся данные строки для немецкой овчарки.

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