Как работает индексация базы данных?
Учитывая, что индексирование так важно, поскольку размер вашего набора данных увеличивается, может ли кто-нибудь объяснить, как индексирование работает на уровне базы данных?
Информацию о запросах для индексирования поля смотрите в разделе Как индексировать столбец базы данных.
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 блоки.
Линейный поиск в поле id потребует в среднем N/2 = 500,000 доступ к блоку для поиска значения, учитывая, что поле id является ключевым. Но так как поле 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% от числа записей, что фактически делает индекс пустой тратой пространства.
Классический пример "Указатель в книгах"
Рассмотрим "Книгу" из 1000 страниц, разделенную на 100 разделов, каждый раздел с X страницами.
Просто, да?
Теперь, без индексной страницы, чтобы найти конкретный раздел, начинающийся с буквы "S", у вас нет другого выбора, кроме сканирования всей книги. то есть: 1000 страниц
Но с индексной страницей в начале вы здесь. И еще: чтобы прочитать какой-либо конкретный раздел, который имеет значение, вам просто нужно просматривать страницу индекса снова и снова, каждый раз. После нахождения соответствующего индекса вы можете эффективно перейти к разделу, пропустив другие разделы.
Но затем, в дополнение к 1000 страниц, вам потребуется еще ~10 страниц для отображения страницы индекса, то есть всего 1010 страниц.
Таким образом, индекс представляет собой отдельный раздел, в котором хранятся значения индексированного столбца + указатель на индексированную строку в отсортированном порядке для эффективного поиска.
В школах все просто, не так ли?:П
Индекс - это просто структура данных, которая ускоряет поиск определенного столбца в базе данных. Эта структура обычно представляет собой b-дерево или хеш-таблицу, но это может быть любая другая логическая структура.
Для получения дополнительной информации я рекомендую: Как работают индексы базы данных? И как помогают индексы?
Когда я впервые прочитал это, это было очень полезно для меня. Спасибо.
С тех пор я получил некоторое представление о недостатках создания индексов: если вы пишете в таблицу (UPDATE или же INSERT) с одним индексом у вас фактически есть две операции записи в файловой системе. Один для данных таблицы и другой для данных индекса (и их применение (и - если кластеризовано - обращение к данным таблицы)). Если таблица и индекс находятся на одном жестком диске, это стоит больше времени. Таким образом, таблица без индекса (кучи) позволит быстрее выполнять операции записи. (если бы у вас было два индекса, вы бы получили три операции записи и т. д.)
Однако определение двух разных местоположений на двух разных жестких дисках для данных индекса и данных таблицы может уменьшить / устранить проблему увеличения затрат времени. Это требует определения дополнительных групп файлов с соответствующими файлами на желаемых жестких дисках и определения местоположения таблицы / индекса по желанию.
Другая проблема с индексами заключается в их фрагментации с течением времени при вставке данных. REORGANIZE помогает, вы должны написать подпрограммы, чтобы сделать это.
В определенных сценариях куча более полезна, чем таблица с индексами,
Например:- Если у вас есть много конкурирующих записей, но только одна ночная чтение вне рабочих часов для отчетности.
Кроме того, различие между кластерными и некластеризованными индексами довольно важно.
Помог мне:- Что на самом деле означает Кластерный и Некластерный индекс?
Теперь предположим, что мы хотим запустить запрос, чтобы найти все детали любых сотрудников с именем "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 имеет индекс, созданный для него, базе данных придется решить, имеет ли смысл использовать индекс для поиска искомых значений - потому что есть некоторые сценарии, где на самом деле менее эффективно использовать индекс базы данных. и более эффективно просто сканировать всю таблицу.
Какова стоимость наличия индекса базы данных?
Это занимает место - и чем больше ваша таблица, тем больше ваш индекс. Еще одним ударом по производительности с индексами является тот факт, что всякий раз, когда вы добавляете, удаляете или обновляете строки в соответствующей таблице, одни и те же операции должны выполняться с вашим индексом. Помните, что индекс должен содержать те же самые данные с точностью до минуты, как и все, что находится в столбцах таблицы, которые покрывает индекс.
Как правило, индекс должен быть создан только для таблицы, если данные в индексированном столбце будут часто запрашиваться.
Смотрите также
Простое описание!!!!!!!!!!
Индекс - это не что иное, как структура данных, в которой хранятся значения для определенного столбца в таблице. Индекс создается по столбцу таблицы.
Например, у нас есть таблица базы данных "Пользователь" с тремя столбцами: "Имя", "Возраст" и "Адрес". Предположим, что таблица User имеет тысячи строк.
Теперь предположим, что мы хотим запустить запрос, чтобы найти все детали любых пользователей с именем "Джон". Если мы запустим следующий запрос.
SELECT * FROM User
WHERE Name = 'John'
Программному обеспечению базы данных в буквальном смысле пришлось бы просматривать каждую строку в таблице User, чтобы узнать, является ли имя для этой строки 'John'. Это займет много времени.
Здесь индекс помогает нам: "Индекс используется для ускорения поисковых запросов путем существенного сокращения количества записей / строк в таблице, которые необходимо изучить".
Как создать индекс
CREATE INDEX name_index
ON User (Name)
Индекс состоит из значений столбцов (например, Джон) из одной таблицы и того, что эти значения хранятся в структуре данных.
Так что теперь база данных будет использовать индекс для поиска сотрудников по имени Джон, потому что индекс, вероятно, будет отсортирован в алфавитном порядке по имени пользователя. И, поскольку оно отсортировано, это означает, что поиск имени выполняется намного быстрее, потому что все имена, начинающиеся с буквы "J", будут находиться рядом друг с другом в индексе!
Просто быстрое предложение. Поскольку индексация требует дополнительных операций записи и хранения, поэтому, если вашему приложению требуется больше операций вставки / обновления, вы можете использовать таблицы без индексов, но если для этого требуется больше операций извлечения данных, вам следует перейти к индексированным Таблица.
Просто подумайте об индексе базы данных как об индексе книги. Если у вас есть книга о собаках, и вы хотите найти информацию о, скажем, немецких овчарках, вы, конечно, можете пролистать все страницы книги и найти то, что вы ищете, но это, конечно, отнимает много времени и не очень быстро. Другой вариант заключается в том, что вы можете просто перейти к разделу "Указатель" книги и затем найти то, что вы ищете, используя Имя сущности, которую вы ищете (в данном случае, немецкие овчарки), а также взглянув на номер страницы, чтобы быстро найти то, что вы ищете. В базе данных номер страницы называется указателем, который направляет базу данных на адрес на диске, на котором находится объект. Используя ту же аналогию с немецкой овчаркой, мы можем получить что-то вроде этого ("Немецкая овчарка", 0x77129), где 0x77129 - это адрес на диске, где хранятся данные строки для немецкой овчарки.
Короче говоря, индекс - это структура данных, которая хранит значения для определенного столбца в таблице, чтобы ускорить поиск запросов.
Индекс SQL связан с ускорением поиска в базе данных SQL. Индекс позволяет программисту получать данные из базы данных очень быстро. Предположим, вы студент или читатель книги. Ваша книга содержит 50000 страниц. В первый день вы читаете какую-то тему "Азбука", на следующий день вы хотите прочитать какую-то другую тему "xyz". Вы никогда не пройдете вручную страницу за страницей. Что вы будете делать в этой ситуации, так это использовать индекс книги, чтобы посмотреть какую-то конкретную тему, а затем перейти непосредственно к своей теме. Индекс сэкономил вам много времени для поиска темы. Индекс SQL, аналогичный индексу SQL, позволяет очень быстро искать миллионы записей в базе данных.
Индекс базы данных - это структура данных, которая повышает скорость операций поиска данных в таблице базы данных за счет дополнительных операций записи и хранения для поддержки структуры данных индекса. Индексы используются для быстрого поиска данных без необходимости искать каждую строку в таблице базы данных при каждом обращении к таблице базы данных. Индексы могут быть созданы с использованием одного или нескольких столбцов таблицы базы данных, обеспечивая основу как для быстрого случайного поиска, так и для эффективного доступа к упорядоченным записям.