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

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

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

4.08.2008 10:07:12
8 ОТВЕТОВ
РЕШЕНИЕ

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

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

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

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

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

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

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

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

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

Имя поля Тип данных Размер на диске
id (первичный ключ) INT без знака 4 байта
firstName Char (50) 50 байтов
lastName Char (50) 50 байтов
emailАдрес Char (100) 100 байт

Примечание : вместо varchar использовался символ char для точного определения размера диска. Этот образец базы данных содержит пять миллионов строк и не индексируется. Производительность нескольких запросов теперь будет проанализирована. Это запрос с использованием идентификатора (поле отсортированного ключа) и запрос с использованием 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обращений к блоку для поиска значения, учитывая, что поле идентификатора является ключевым. Но поскольку поле id также отсортировано, можно выполнить бинарный поиск, требующий среднего числа log2 1000000 = 19.93 = 20обращений к блоку. Мгновенно мы видим, что это радикальное улучшение.

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

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

Имя поля Тип данных Размер на диске
firstName Char (50) 50 байтов
(указатель записи) Специальные 4 байта

Примечание . Указатели в 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% от числа записей, что фактически делает индекс пустой тратой пространства.

3509
24.04.2019 13:13:42
бинарный поиск может быть сделан, когда данные уникальны, я прав? хотя вы упомянули, что минимальное количество элементов является важным, алгоритм не будет простым двоичным поиском, как это приближение (~ log2 n) повлияет на время процесса?
shampoo 3.02.2013 10:20:27
@AbhishekShivkumar: Отличный вопрос! Я думаю, что в индексной таблице будет столько строк, сколько в таблице данных. И так как это поле будет иметь только 2 значения (логическое с true / false) и скажем, что вы хотите запись со значением true, то вы можете только вдвое сократить результирующий набор при первом проходе, во втором проходе все ваши записи имеют значение true, поэтому нет никаких оснований для дифференциации, теперь вы должны искать в таблице данных линейно - следовательно, он сказал, что при определении индексированного столбца следует учитывать количество элементов. В этом случае не стоит индексировать такой столбец. Надеюсь, я прав :)
Saurabh Patil 8.07.2013 04:20:24
не должно быть числа обращений к блоку в среднем случае (N+1)/2. Если мы суммируем количество обращений к блокам для всех возможных случаев и делим его на количество случаев, то мы получаем то, N*(N+1)/(2*n)что получается (N+1)/2.
ajay 30.01.2014 12:11:02
Я думаю, что в этом ответе есть несколько опечаток, например, в предложении: «далеко от 277 778 блочных обращений, необходимых для неиндексированной таблицы». Разве автор не имеет в виду 1 000 000 блочных доступов? 277 778 - количество блоков, необходимых для самого индекса. Кажется, есть еще пара неточностей :(
jcm 24.08.2014 04:02:07
@jcm Он объяснил это в разделе «Что такое раздел индексации» - «Индексирование - это способ сортировки количества записей по нескольким полям. Создание индекса по полю в таблице создает другую структуру данных, которая содержит значение поля и указатель к записи, к которой он относится. Затем эта структура индекса сортируется, что позволяет выполнять бинарный поиск ».
grinch 12.11.2014 20:32:58

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

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

Просто, да?

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

Эта аналогия известна как «полное сканирование таблицы» в мире баз данных.

введите описание изображения здесь

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

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

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

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

273
15.02.2020 09:40:05
действительно хорошая аналогия! забавно, я не установил связь между книжным индексом и индексом БД
Yolo Voe 11.07.2018 22:22:38
Это заставляет меня задуматься Libraryили не Grocery Store могли бы вы представить, что у вас нет индекса в продуктовом магазине? Where's The Beef?!? Oh its next to the Restrooms, a mop, and makeup
JayRizzo 4.09.2018 07:00:57
«Но с индексной страницей в начале, вы там». Что значит "ты там"?
Frisbetarian 13.09.2018 10:48:15
Индексы обычно идут в конце книги, а оглавление - в начале. Но это делает аналогию еще лучше, поскольку порядок столбцов не должен иметь значения.
undrline 9.07.2019 03:19:03
Ваше объяснение так легко принять. Другие люди, как правило, используют сложные термины для объяснения вещей. Я хотел бы дать больше, чем один голос.
emeraldhieu 12.07.2019 06:59:39

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

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

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

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

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

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

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

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

237
23.05.2017 11:47:36
Я думаю, что эти проблемы индексации могут быть решены путем поддержки двух разных баз данных, таких как Master и Slave. Где Мастер может быть использован для вставки или обновления записей. Без индексации. И раб может быть использован для чтения с правильным индексированием правильно ???
bharatesh 23.05.2014 09:51:06
нет, неправильно извините Необходимо обновлять не только содержимое таблиц, но также структуру и содержимое индекса (b-дерево, узлы). ваша концепция хозяина и раба здесь не имеет смысла. что может быть осуществимо, хотя это репликация или зеркалирование во вторую базу данных, в которой выполняется аналитика для отвода этой рабочей нагрузки от первой базы данных. эта вторая база данных будет содержать копии данных и индексы на этих данных.
Der U 29.05.2014 16:11:58
Я ...! Попробуйте прочитать мой комментарий и понять его правильно. Я также сказал то же самое, я говорил о главном и подчиненном (что угодно) как о «воспроизведении или зеркальном отображении второй базы данных, в которой выполняется аналитика для отвода этой рабочей нагрузки от первой базы данных. Эта вторая база данных будет содержать копии данных и индексов на эти данные "
bharatesh 2.06.2014 11:04:10
вторая база данных - для которой выполняется зеркалирование или репликация, ведомая - будет испытывать все манипуляции с данными, как и первая. при каждой dml-операции индексы в этой второй базе данных будут испытывать «эти проблемы с индексацией». Я не вижу выгоды в том, что когда бы ни были нужны индексы и они построены для быстрого анализа, их нужно постоянно обновлять.
Der U 3.06.2014 13:23:50

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

227
21.03.2019 12:56:55
+1 раз за миллион за этот ответ, так как я нашел этот список, пытаясь найти простое объяснение того, что такое индексация по сути.
Josh Burson 22.06.2015 23:06:13
Отметим, что «просто структура данных» не означает «дополнительный к данным». Иногда это так (например, «некластеризованный индекс»), иногда это определяет расположение данных (например, «кластеризованный индекс»).
Pablo H 28.08.2019 13:24:17

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

SELECT * FROM Employee 
WHERE Employee_Name = 'Abc'

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. Какие столбцы обычно дают хорошие показатели?
  2. Как работают индексы базы данных
152
23.05.2017 11:47:36
«индекс базы данных не хранит значения в других столбцах» - неверно.
mustaccio 13.08.2016 18:56:47
@mustaccio: Индекс хранит ссылку на строку только с индексированными столбцами (насколько я знаю). Я могу быть не прав. У вас есть ссылка, в которой говорится, что индекс хранит значения других столбцов?
Somnath Muluk 13.08.2016 19:11:40
@ To Downvoters: Можете ли вы просто объяснить, что не так, чтобы я мог улучшить?
Somnath Muluk 13.08.2016 19:12:18
Посмотрите, например, индексы кластеризации SQL Server или предложение DB2 CREATE INDEX ... INCLUDE. На мой взгляд, в вашем ответе слишком много обобщений.
mustaccio 13.08.2016 19:13:11
@mustaccio: поэтому по умолчанию create indexне включает другие столбцы и почему это следует. If we did just store all the other columns in the index, then it would be just like creating another copy of the entire table, which would take up way too much space and would be very inefficient., Это более обобщенная версия индексов. CREATE INDEX ... INCLUDEэто более новая версия, учитывая другие столбцы. Пост, который я объяснил, рассматривает более обобщенную версию. Как работают индексы, будет одна книга, если мы рассмотрим все базы данных? Не так ли? Как вы думаете, ответ заслуживает отрицательного ответа?
Somnath Muluk 13.08.2016 19:21:40

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

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

Пример: У нас есть таблица базы данных под названием Userс тремя столбцами - Name, Ageи Address. Предположим, что Userтаблица имеет тысячи строк.

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

SELECT * FROM User 
WHERE Name = 'John'

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

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

Как создать индекс:

CREATE INDEX name_index
ON User (Name)

Он indexсостоит из значений столбцов (например, John) из одной таблицы , и эти значения хранятся в структуре данных .

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

94
6.10.2019 06:30:48
Индекс не подразумевает порядок сортировки по столбцу
oligofren 15.02.2019 13:26:36
Спасибо. Это помогло моему пониманию. Таким образом, в основном индекс представляет собой копию данных столбца, которые были отсортированы. Обычно данные столбца находятся в том порядке, в котором они были вставлены.
Neil 1.05.2019 10:30:30

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

32
14.01.2015 06:44:51
Это комментарий, а не ответ.
RonJohn 24.07.2018 21:37:50
Это более наглядно и, следовательно, более полезно, так как это общее замечание. Какой ответ должен быть добавлен в качестве комментария?
pfabri 23.03.2019 19:16:36
вероятно, комментарий к OP
guyarad 24.09.2019 16:47:56

Просто подумайте об индексе базы данных как об индексе книги.

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

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

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

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

32
10.07.2019 07:42:29