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

https://stackoverflow.com/questions/1108

08-06-2019
|

Вопрос

Учитывая, что индексирование очень важно по мере увеличения размера вашего набора данных, может ли кто-нибудь объяснить, как индексирование работает на уровне, независимом от базы данных?

Информацию о запросах на индексацию поля см. Как индексировать столбец базы данных.

Решение

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

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

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

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

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

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

Обратной стороной индексирования является то, что эти индексы требуют дополнительного места на диске, поскольку индексы хранятся вместе в таблице с использованием механизма 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

Примечание:Вместо varchar использовался char, чтобы обеспечить точный размер значения на диске.Этот пример базы данных содержит пять миллионов строк и неиндексирован.Теперь будет проанализирована производительность нескольких запросов.Это запрос с использованием идентификатор (отсортированное ключевое поле) и одно с использованием имя (неключевое несортированное поле).

Пример 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 заблокировать доступ.Мы сразу же видим, что это радикальное улучшение.

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

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

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 блоки.

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

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

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

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

Другие советы

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

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

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

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

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

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

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

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

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

Классический пример «Указатель в книгах»

Рассмотрим «Книгу» из 1000 страниц, разделенную на 100 разделов, в каждом разделе X страниц.

Просто, да?

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

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

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

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

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

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

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

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

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

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

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

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

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

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

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

Например, запрос, который мы обсуждали ранее, мог бы выиграть от хэш-индекса, созданного в столбце «Имя_сотрудника».Хэш-индекс будет работать следующим образом: значение столбца будет ключом в хеш-таблице, а фактическое значение, сопоставленное с этим ключом, будет просто указателем на данные строки в таблице.Поскольку хеш-таблица по сути представляет собой ассоциативный массив, типичная запись будет выглядеть примерно так: «Abc => 0x28939», где 0x28939 — это ссылка на строку таблицы, в которой Abc хранится в памяти.Поиск значения типа «Abc» в индексе хеш-таблицы и получение ссылки на строку в памяти, очевидно, намного быстрее, чем сканирование таблицы в поисках всех строк со значением «Abc» в столбце «Имя сотрудника».

Недостатки хеш-индекса

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

Что именно находится внутри индекса базы данных?Итак, теперь вы знаете, что индекс базы данных создается для столбца таблицы и что индекс хранит значения в этом конкретном столбце.Но важно понимать, что индекс базы данных не хранит значения в других столбцах той же таблицы.Например, если мы создаем индекс для столбца «Имя сотрудника», это означает, что значения столбцов «Сотрудник_Возраст» и «Адрес сотрудника» также не сохраняются в индексе.Если бы мы просто сохранили все остальные столбцы в индексе, это было бы похоже на создание еще одной копии всей таблицы — что заняло бы слишком много места и было бы очень неэффективно.

Как база данных узнает, когда использовать индекс?Когда выполняется запрос типа «SELECT * FROM Employer WHERE Employee_Name = ‘Abc’», база данных проверит, существует ли индекс в запрашиваемом столбце (столбцах).Предполагая, что для столбца «Имя_сотрудника» действительно создан индекс, базе данных придется решить, действительно ли имеет смысл использовать индекс для поиска искомых значений, поскольку в некоторых сценариях использование индекса базы данных фактически менее эффективно. и более эффективно просто сканировать всю таблицу.

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

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

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

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

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

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

Например, у нас есть таблица базы данных под названием «Пользователь» с тремя столбцами: «Имя», «Возраст» и «Адрес».Предположим, что таблица User содержит тысячи строк.

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

SELECT * FROM User 
WHERE Name = 'John'

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

CREATE INDEX name_index
ON User (Name)

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow