Индексы в базах данных: 14 вопросов об индексах в SQL Server, которые вы стеснялись задать / Хабр

Индексы в PostgreSQL

Виталий Сушков

Full Stack Developer в DataArt

В статье я расскажу о предназначении и основах принципов работы объектов баз данных — индексов. На примере СУБД PostgreSQL коротко рассмотрим несколько разных типов индексов и классов задач, для которых они применимы. В конце материала поделюсь ссылками на статьи с более глубоким описанием внутреннего устройства индексов в PostgreSQL.

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

Предназначение индексов

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

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

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

В качестве примера рассмотрим задачу поиска в списке чисел. Используя перебор элементов списка, в худшем случае, нам придется просмотреть список целиком. Алгоритмическая сложность такого метода — O(n). Но если мы будем хранить наши числа особым образом — отсортированными по возрастанию или по убыванию — сможем использовать алгоритм бинарного поиска.

2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180

Допустим, необходимо определить, содержит ли этот отсортированный список число 158. Для этого:

  • Смотрим на число в середине списка — 114. Наш список отсортирован по возрастанию, и мы ищем число 158 > 114. Значит, левую половину списка до числа 114 мы можем отбросить: в ней гарантированно не может быть искомого элемента.
    • 2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180
  • Теперь делаем то же самое для правой половины списка. В середине у нее число 134, значит, мы снова можем отбросить элементы левее.
    • 2 4 5 10 23 34 38 58 112 114 115 110 123 134 138 158 180
  • Делаем то же самое для элементов правее 134. В середине у них число 158 — искомый элемент. Поиск закончен.

В итоге метод бинарного поиска дал нам результат всего за три шага. При полном переборе с начала списка нам потребовалось бы 16 шагов. Бинарный поиск имеет алгоритмическую сложность O(log(n)). Используя формулы алгоритмической сложности O(n) и O(log(n)), мы можем оценить, как будет меняться приблизительное количество операций при поиске разными способами с ростом объема данных:

Результат впечатляет. Храня данные в отсортированном виде, мы не только снизили скорость поиска по ним, но и колоссально сократили скорость замедления поиска при росте объема данных.

Использование индексов в базе данных дает аналогичный результат. Принцип работы одного из важнейших индексов в базе данных (индекс на основе B-дерева) основан именно на рассмотренном нами выше принципе — возможности хранить данные в отсортированном виде.

Индексы в PostgreSQL

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

Рассмотрим запрос:

SELECT * FROM table_name WHERE P(column_name) = 1

Здесь выражение P(column_name) = 1 означает, что значение в колонке column_name удовлетворяет некоторому условию (предикату) P.

В отсутствии индекса для колонки column_name, PostgreSQL для выполнения этого запроса был бы вынужден просмотреть таблицу table_name целиком, вычисляя для каждой строки значение предиката P и, если значение истинно, добавлял бы строку к результатам запроса.

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

Предикат P может вычисляться от значения нескольких колонок. В этом случае для ускорения запроса используется индекс, построенный не для одной колонки, а для нескольких. Такие индексы называют составными.

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

CREATE INDEX index_name
ON table_name (column_name_1, column_name_2,....)

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

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

CREATE UNIQUE INDEX index_name
ON table_name (column_name_1, column_name_2,. ...)

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

SELECT * FROM table_name
WHERE lower(text_field) = 'some_string_in_lower_case'

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

CREATE INDEX index_name ON table_name(lower(text_field))

И такой индекс уже может успешно применяться для ускорения нашего запроса.

В зависимости от типа индексируемых данных, для индексирования применяются разные подходы. По умолчанию при создании индекса используется индекс на основе B-дерева. Но PostgreSQL поддерживает разные типы индексов для очень широкого круга задач, и при необходимости мы можем указать другой тип индекса, отличный от B-tree. Для этого перед списком индексируемых полей необходимо указать директиву USING <тип_индекса>. Например, для использования индекса типа GiST:

CREATE INDEX index_name ON table_name USING GIST (column_name)

B-tree

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

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

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

  • Найти пользователя по его email:
  • Найти товары одной из двух категорий:
    • SELECT * FROM goods WHERE category_id = 10 OR category_id = 20
  • Найти количество пользователей, зарегистрировавшихся в конкретный месяц:
    • SELECT COUNT(id) FROM users WHERE reg_date >= 01.01.2021 AND reg_date <= 31.01.2021

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

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

Однако хранить индекс  просто  в виде отсортированного массива мы не можем, т. к. данные могут модифицироваться: значения могут меняться, записи — удаляться или добавляться. Чтобы эффективно поддерживать хранение индексируемых данных в отсортированном виде, индекс хранят в виде сбалансированного сильно ветвящегося дерева, называемого B-деревом (B-tree).

Корневой узел B-дерева содержит в упорядоченном виде несколько значений из общего набора, допустим, t элементов. Тогда все остальные элементы можно распределить по t+1 дочерним поддеревьям по следующему правилу:

  • Первое поддерево будет содержать элементы, которые меньше, чем 1-й элемент корневого узла (на рисунке выше первое поддерево содержит числа, меньшие 30).
  • Второе поддерево будет содержать элементы, которые находятся между 1-м и 2-м элементами корневого узла (на рисунке выше второе поддерево содержит числа между 30 и 70).
  • И т. д. — последнее поддерево будет содержать элементы, большие элемента корневого узла с номером t (на рисунке выше третье поддерево содержит элементы, большие 70).

Каждое поддерево, в свою очередь, тоже является B-деревом, имеет корневой элемент и строится далее рекурсивно по такому же принципу.

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

  • Корневой узел содержит числа 30 и 70, значит, искомый элемент следует искать во втором поддереве, т.к. 67 > 30 и 67 < 70.
  • Корневой узел второго поддерева содержит элементы 40 и 50. Т. к. 67 > 50, искомый элемент следует искать в третьем потомке этого узла.
  • На третьем шаге мы получили узел, не имеющий потомков, среди элементов которого находим искомое число 67.

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

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

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

SELECT * FROM table_name WHERE text_field LIKE 'start_substring%'

Если индекс построен по нескольким колонкам, он может ускорять запросы, в которых фигурируют одна или несколько первых колонок. Поэтому важен порядок, в котором мы указываем колонки при создании индекса. Допустим, у нас есть индекс по колонкам col_1 и col_2. Тогда он может использоваться в том числе для ускорения запроса вида:

SELECT * FROM table_name WHERE col_1 = 123

И нам не нужно создавать отдельный индекс для колонки col_1. Будет использоваться составной индекс (col_1, col_2).

Однако для запроса только по колонке col_2 такой составной индекс уже использовать не получится.

Подробнее, как индекс на основе B-дерева реализован в PostgreSQL, см. статью.

GiST и SP-GiST

GiST — сокращение от «generalized search tree». Это сбалансированное дерево поиска, точно так же, как и рассмотренный ранее b-tree. Но b-tree применимо только к тем типам данных, для которых имеет смысл операция сравнения и есть возможность упорядочивания. Но PostgreSQL позволяет хранить и такие данные, для которых операция упорядочивания не имеет смысла, например, геоданные и геометрические объекты.

Тут на помощь приходит индексный метод GiST. Он позволяет распределить данные любого типа по сбалансированному дереву и использовать это дерево для поиска по самым разным условиям. Если при построении B-дерева мы сортируем все множество объектов и делим его на части по принципу больше-меньше, при построении GiST индексов можно реализовать любой принцип разбиения любого множества объектов.

Например, в GiST-индекс можно уложить R-дерево для пространственных данных с поддержкой операторов взаимного расположения (находится слева, справа; содержит и т. д.). Такой индекс доступен в PostgreSQL и может быть полезен при разработке геоинформационных систем, в которых возникают запросы вида «получить множество объектов на карте, находящихся от заданной точки на расстоянии не более 1 км».

SP-GiST похож GiST, но он позволяет создавать несбалансированные деревья. Такие деревья могут быть полезны при разбиении множества на непересекающиеся объекты. Буквы SP означают space partitioning. К такому типу индексов можно отнести kd-деревья, реализация которых присутствует в PostgreSQL. Его, как и R-дерево, можно использовать для ускорения запросов геометрического поиска. Свойство непересечения упрощает принятие решений при вставке и поиске. С другой стороны, получающиеся деревья, как правило, слабо ветвисты, что усложняет их эффективное хранение во внешней памяти.

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

Подробнее об алгоритмах, лежащих в основе R- и kd-деревьев см. раз и два, а об их реализации и использовании в PostgreSQL см. в этой и этой статье.

Заключение

Индексы — важнейший инструмент баз данных, ускоряющий поиск. Он не бесплатен, создавать много индексов без лишней необходимости не стоит — индексы занимают дополнительную память, и при любом обновлении проиндексированных данных СУБД должна выполнять дополнительную работу по поддержанию индекса в актуальном состоянии.

PostgreSQL поддерживает разные типы индексов для разных задач:

  • B-дерево покрывает широчайший класс задач, т. к. применимо к любым данным, которые можно отсортировать.
  • GiST и SP-GiST могут быть полезны при работе с геометрическими объектами и для создания совершенно новых типов индексов для новых типов данных.
  • За рамками этой статьи оказался ещё один важный тип индексов — GIN. GIN индексы полезны для организации полнотекстового поиска и для индексации таких типов данных, как массивы или jsonb. Подробнее см. в статье. Современные версии PostgreSQL имеют вариацию такого индекса под названием RUM (см. статью).

Ссылки на полезные материалы

  1. Создание индекса в PostgreSQL
  2. Алгоритмы работы с B-деревом
  3. Релизация B-дерева в PostgreSQL
  4. R-дерево
  5. Kd-дерево
  6. Индекс типа GiST в PostgreSQL
  7. Индекс типа SP-GiST в PostgreSQL
  8. Индекс типа GIN в PostgreSQL
  9. Индекс типа RUM в PostgreSQL

 

что это и зачем нужны — Блог Lineate

ко всем статьям

< ко всем статьям

<

Автор: Татьяна Сергиенко, Software Engineer

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

Что такое индексы?

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

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

Для чего используются индексы?

Индексы помогают:

  • быстро находить строки, соответствующие выражению WHERE
  • извлекать строки из других таблиц при выполнении объединений
  • находить величины MAX() или MIN() для заданного индексированного столбца
  • производить сортировку или группирование в таблице, если эти операции делаются на крайнем левом префиксе используемого ключа (например, ORDER BY key_part_1, key_part_2).

Индекс – это специальная структура данных, обычно это B-Tree дерево, которое позволяет повышать скорость извлечения данных за счет дополнительных операций записи и хранения. Здесь стоит отметить, что индексы хранятся отдельно от данных.

Схематично B-Tree можно изобразить так: дерево состоит из корня (верхняя вершинка), дальше у нас идут ветви, ветви заканчиваются листьями, на листьях находится нужная информация.

Мощность Индекса

Мощность индекса относится к уникальности значений, хранящихся в указанном столбце индекса.

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

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

Действия с индексами MySQL

Создание индекса

Есть два варианта, которые можно использовать в зависимости от ситуации:

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

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

Просмотр индексов

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

Удаление индекса

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

ДРУГИЕ СТАТЬИ

>

ко всем статьям

Wednesday, August 18

Индексы MySQL: что это и зачем нужны — Блог Lineate

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

Wednesday, August 18

Типы индексов MySQL — Блог Lineate

Кластеризованные — специальные индексы, Primary Key и Unique Index (Key и Index – это синонимы в данном случае). Некластеризованные, или вторичные, индексы — все остальные индексы, которые не попадают под Primary и Unique

Давайте работать вместе

Присоединяйтесь к нашей команде!

Смотреть вакансии

Пример использования индексов базы данных

Загрузить в формате PDF

Введение

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

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

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

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

Драйвер базы данных может использовать индексы для быстрого поиска записей. Например, индекс в поле EMP_ID значительно сокращает время, затрачиваемое водителем на поиск определенного значения идентификатора сотрудника. Рассмотрим следующее предложение Where:

ГДЕ emp_id = 'E10001'

Без индекса драйвер должен выполнить поиск по всей таблице базы данных, чтобы найти записи с идентификатором сотрудника E10001. Однако, используя индекс поля EMP_ID, драйвер может быстро найти эти записи.

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

Наверх

Повышение производительности выбора записей

Чтобы индексы повышали производительность выбора, выражение индекса должно точно соответствовать условию выбора. Например, если вы создали индекс с выражением last_name, следующий оператор Select использует этот индекс:

SELECT * FROM emp WHERE last_name = 'Smith'

Это заявление SELECT, однако, не использует индекс:

SELECT * из EMP , где Верхний (последний_нам) = .

Второй оператор не использует индекс, поскольку предложение Where содержит UPPER(LAST_NAME), что не соответствует индексному выражению LAST_NAME. Если вы планируете использовать функцию UPPER во всех своих операторах Select и ваша база данных поддерживает индексы для выражений, вам следует определить индекс, используя выражение UPPER(LAST_NAME).

Наверх

Индексирование нескольких полей

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

WHERE last_name = 'Smith' и first_name = 'Thomas'

. Это создает составной индекс.

Составные индексы также можно использовать для предложений Where, содержащих только первое из двух связанных полей. Индекс LAST_NAME, FIRST_NAME также улучшает производительность следующего предложения Where (даже если значение имени не указано):

last_name = 'Smith'

Рассмотрим следующее предложение Where:

WHERE 9 last_name = «Кузнец» и middle_name = 'Эдвард' и

first_name = 'Томас'

Если ваши поля индекса включают все условия предложения Where в указанном порядке, драйвер может использовать весь индекс. Однако если ваш индекс состоит из двух непоследовательных полей, скажем, LAST_NAME и FIRST_NAME, драйвер может использовать только поле LAST_NAME индекса.

Драйвер использует только один индекс при обработке предложений Where. Если у вас есть сложные предложения Where, которые включают ряд условий для разных полей и имеют индексы более чем для одного поля, драйвер выбирает индекс для использования. Драйвер пытается использовать индексы для условий, использующих знак равенства в качестве оператора отношения, а не условий, использующих другие операторы (например, больше). Предположим, у вас есть индекс для поля EMP_ID, а также для поля LAST_NAME и следующего предложения Where: 9.0003

ГДЕ emp_id >= 'E10001' И last_name = 'Smith'

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

В большинстве случаев драйвер не использует индекс, если предложение Where содержит оператор сравнения ИЛИ. Например, драйвер не использует индекс для следующего предложения Where:

WHERE emp_id >= 'E10001' OR last_name = 'Smith'

0
Наверх

Выбор индексов для создания

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

  • Вставка, обновление и удаление записей
  • Получить записи

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

Если вы чаще всего извлекаете записи, вам необходимо дополнительно определить критерии для извлечения записей и создать индексы для повышения производительности этих извлечений. Предположим, у вас есть таблица базы данных сотрудников, и вы будете извлекать записи на основе имени сотрудника, отдела или даты приема на работу. Вы должны создать три индекса: один для поля DEPT, один для поля HIRE_DATE и один для поля LAST_NAME. Или, возможно, для поиска на основе поля имени вам понадобится индекс, объединяющий поля LAST_NAME и FIRST_NAME (подробности см. в разделе «Индексирование нескольких полей»).

Вот несколько правил, которые помогут вам решить, какие индексы создавать:

Наверх

Повышение производительности соединения

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

Предположим, у вас есть следующий оператор Select:

SELECT * FROM отдел, emp WHERE dept.dept_id = emp.dept

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

Чтобы повысить производительность соединения, вам нужен индекс для поля соединения второй таблицы в предложении From. Если в предложении From есть третья таблица, драйвер также использует индекс для поля в третьей таблице, который соединяет ее с любой предыдущей таблицей. Например:

SELECT * Из DEPT, EMP, ADDR

, где DEPT. DEPT_ID = EMP.DEPT и EMP.LOC = ADDR.LOC

и EMP. у вас должен быть индекс для поля EMP.DEPT и поля ADDR.LOC.

Наверх

Индексирование в базах данных | Набор 1

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

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

  • Первый столбец — это Ключ поиска , который содержит копию первичного ключа или ключа-кандидата таблицы. Эти значения хранятся в отсортированном порядке, чтобы можно было быстро получить доступ к соответствующим данным.
    Примечание. Данные могут храниться или не храниться в отсортированном порядке.
  • Второй столбец — это Ссылка на данные или Указатель , который содержит набор указателей, содержащих адрес блока диска, где можно найти это конкретное значение ключа.

Индексация имеет различные атрибуты:  

  • Типы доступа : относится к типу доступа, такому как поиск по значению, доступ к диапазону и т. д.
  • Время доступа : относится к необходимому времени чтобы найти конкретный элемент данных или набор элементов.
  • Время вставки : Время, необходимое для поиска подходящего места и вставки новых данных.
  • Время удаления : Время, необходимое для поиска элемента и его удаления, а также для обновления структуры индекса.
  • Space Overhead : Это относится к дополнительному пространству, необходимому для индекса.

В целом существует два типа механизма организации файлов, за которыми следуют методы индексации для хранения данных:  

1. Последовательная организация файлов или упорядоченный индексный файл: В этом случае индексы основаны на отсортированном порядок значений. Как правило, это быстрый и более традиционный тип механизма хранения. Эти упорядоченные или последовательные организации файлов могут хранить данные в плотном или разреженном формате: 

(i) Плотный индекс:  

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

(ii) Разреженный индекс:  

  • Запись индекса появляется только для нескольких элементов в файле данных. Каждый элемент указывает на блок, как показано.
  • Чтобы найти запись, мы находим запись индекса с наибольшим значением ключа поиска, меньшим или равным искомому значению ключа поиска.
  • Мы начинаем с той записи, на которую указывает индексная запись, и действуем по указателям в файле (то есть последовательно), пока не найдем нужную запись.

2. Организация хеш-файла: Индексы основаны на значениях, равномерно распределенных по ряду сегментов. Сегменты, которым присваивается значение, определяются функцией, называемой хеш-функцией.

В основном существует три метода индексации:  

  • Кластерное индексирование
  • Некластерное или вторичное индексирование
  • Многоуровневое индексирование

1. Кластерное индексирование  
Когда в одном файле хранится более двух записей, эти типы хранения называются кластерным индексированием. Используя кластерное индексирование, мы можем снизить стоимость поиска, поскольку несколько записей, связанных с одним и тем же объектом, хранятся в одном месте, а также часто происходит объединение более двух таблиц (записей).
Индекс кластеризации определен для упорядоченного файла данных. Файл данных упорядочен по неключевому полю. В некоторых случаях индекс создается по столбцам, не являющимся первичными ключами, которые могут не быть уникальными для каждой записи. В таких случаях, чтобы быстрее идентифицировать записи, мы сгруппируем два или более столбца вместе, чтобы получить уникальные значения и создать из них индекс. Этот метод известен как индекс кластеризации. По сути, записи со схожими характеристиками группируются вместе, и для этих групп создаются индексы.
Например, студенты, обучающиеся в каждом семестре, группируются вместе. то есть 1 студентов семестра, 2 и студентов семестра, 3 и студентов семестра и т. д. сгруппированы.

Кластерный индекс, отсортированный по имени (ключу поиска) 

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

2. Некластеризованное или вторичное индексирование  
Некластеризованный индекс просто сообщает нам, где находятся данные, т. е. дает нам список виртуальных указателей или ссылок на место, где данные фактически хранятся. Данные физически не хранятся в порядке индекса. Вместо этого данные присутствуют в листовых узлах. Например. страница содержания книги. Каждая запись дает нам номер страницы или местоположение сохраненной информации. Фактические данные здесь (информация на каждой странице книги) не организованы, но у нас есть упорядоченная ссылка (страница содержания) на то, где фактически лежат точки данных. У нас может быть только плотное упорядочение в некластеризованном индексе, поскольку разреженное упорядочение невозможно, потому что данные физически не организованы соответствующим образом.
Это требует больше времени по сравнению с кластеризованным индексом, потому что выполняется некоторый объем дополнительной работы для извлечения данных путем дальнейшего следования указателю. В случае кластеризованного индекса данные находятся непосредственно перед индексом.

3. Многоуровневое индексирование  

С ростом размера базы растут и индексы.