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

Ответ 1

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

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

В связи с тем, что несколько записей могут быть отсортированы только по одному полю, мы можем констатировать, что для поиска по невыбранному полю требуется линейный поиск, который требует 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 для точного определения размера диска. Этот образец базы данных содержит пять миллионов строк и не индексируется. Производительность нескольких запросов теперь будет проанализирована. Это запрос с использованием идентификатора (поле отсортированного ключа) и запрос с использованием 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 обращений к 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% от числа записей, что фактически делает индекс пустой тратой пространства.

Ответ 2

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

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

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

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

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

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

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

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

Ответ 3

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

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

Просто, да?

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

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

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

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

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

Ответ 4

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

Ответ 5

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

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

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

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

См. также

• Какие столбцы обычно содержат хорошие индексы?
• Как работают индексы базы данных

Ответ 6

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

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

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

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

SELECT * FROM User 
WHERE Name = 'John'

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

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

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

CREATE INDEX name_index
ON User (Name)

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

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

Ответ 7

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

Ответ 8

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

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

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

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

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

Ответ 9

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

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

Когда строка вставлена, соответствующая строка записывается в индекс, а когда строка удаляется, ее строка индекса выводится.

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

Точное поведение зависит от реализации механизма хранения.

Некоторые механизмы хранения реализуют "первичные индексы", как правило, на PRIMARY KEY. Наиболее часто используемым механизмом хранения этого типа является MySQL InnoDB - в этом случае данные базовой таблицы хранятся в структуре B-Tree, а вторичные индексы сохраняют PRIMARY KEY для каждой строки. Oracle "Индексные упорядоченные таблицы" также реализованы таким образом.

Большим преимуществом этой структуры является поиск в PRIMARY KEY очень быстро, так как только одна структура должна быть посещена, чтобы вытягивать строки, а не два для традиционного хранилища "куча + вторичный индекс".

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

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

Ответ 10

Вы можете просмотреть индексы как книгу желтых страниц. Он может быстро показать вам, где найти нужные данные, а не идти от двери до двери, чтобы спросить, правда ли это. Простой поиск в Google может дать больше, чем несколько хороших результатов, однако один из них, который я нашел, помог мне больше всего: Топ-10 вопросов и ответов о индексах SQL Server