Что называется индексом в базе данных
Индекс (базы данных)
Индекс (англ. index ) — объект базы данных, создаваемый с целью повышения производительности поиска данных. Таблицы в базе данных могут иметь большое количество строк, которые хранятся в произвольном порядке, и их поиск по заданному критерию путем последовательного просмотра таблицы строка за строкой может занимать много времени. Индекс формируется из значений одного или нескольких столбцов таблицы и указателей на соответствующие строки таблицы и, таким образом, позволяет искать строки, удовлетворяющие критерию поиска. Ускорение работы с использованием индексов достигается в первую очередь за счёт того, что индекс имеет структуру, оптимизированную под поиск — например, сбалансированного дерева.
Некоторые СУБД расширяют возможности индексов введением возможности создания индексов по столбцам представлений [1] или индексов по выражениям. [2] Например, индекс может быть создан по выражению upper(last_name) и соответственно будет хранить ссылки, ключом к которым будет значение поля last_name в верхнем регистре. Кроме того, индексы могут быть объявлены как уникальные и как не уникальные. Уникальный индекс реализует ограничение целостности на таблице, исключая возможность вставки повторяющихся значений.
Содержание
Архитектура
Индексы могут быть реализованы различными структурами. Наиболее частоупотребимы B*-деревья, B+-деревья, B-деревья и хеши.
Последовательность столбцов в составном индексе
Последовательность, в которой столбцы представлены в составном индексе, достаточно важна. Дело в том, что получить набор данных по запросу, затрагивающему только первый из проиндексированных столбцов, можно. Однако в большинстве СУБД невозможно или неэффективно получение данных только по второму и далее проиндексированным столбцам (без ограничений на первый столбец).
Например, представим себе телефонный справочник, отсортированный вначале по городу, затем по фамилии, и затем по имени. Если вы знаете город, вы можете легко найти все телефоны этого города. Однако в таком справочнике будет весьма трудоёмко найти все телефоны, записанные на определённую фамилию — для этого необходимо посмотреть в секцию каждого города и поискать там нужную фамилию. Некоторые СУБД выполняют эту работу, остальные же просто не используют такой индекс.
Производительность
Для оптимальной производительности запросов индексы обычно создаются на тех столбцах таблицы, которые часто используются в запросах. Для одной таблицы может быть создано несколько индексов. Однако увеличение числа индексов замедляет операции добавления, обновления, удаления строк таблицы, поскольку при этом приходится обновлять сами индексы. Кроме того, индексы занимают дополнительный объем памяти, поэтому перед созданием индекса следует убедиться, что планируемый выигрыш в производительности запросов превысит дополнительную затрату ресурсов компьютера на сопровождение индекса.
Ограничения
Индексы полезны для многих приложений, однако на их использование накладываются ограничения. Возьмём такой запрос SQL:
Для выполнения такого запроса без индекса СУБД должна проверить поле last_name в каждой строке таблицы (этот механизм известен как «полный перебор» или «полный скан таблицы», в плане может отображаться словом NATURAL). При использовании индекса СУБД просто проходит по B-дереву, пока не найдёт запись «Франкенштейн». Такой проход требует гораздо меньше ресурсов, чем полный перебор таблицы.
Теперь возьмём такой запрос:
Этот запрос должен нам найти всех клиентов, у которых е-мейл заканчивается на @yahoo.com, однако даже если по столбцу email_address есть индекс, СУБД всё равно будет использовать полный перебор таблицы. Это связано с тем, что индексы строятся в предположении, что слова/символы идут слева направо. Использование символа подстановки в начале условия поиска исключает для СУБД возможность использования поиска по B-дереву. Эта проблема может быть решена созданием дополнительного индекса по выражению reverse(email_address) и формированием запроса вида:
В данном случае символ подстановки окажется в самой правой позиции (moc.oohay@%), что не исключает использование индекса по reverse(email_address).
Редкий индекс
Редкий индекс (англ. sparse index ) в базах данных — это файл с последовательностью пар ключей и указателей. [4] Каждый ключ в редком индексе, в отличие от плотного индекса, ассоциируется с определённым указателем на блок в сортированном файле данных. Идея использования индексов пришла от того, что современные базы данных слишком массивны и не помещаются в основную память. Мы обычно делим данные на блоки и размещаем данные в памяти поблочно. Однако поиск записи в БД может занять много времени. С другой стороны, файл индексов или блок индексов намного меньше блока данных и может поместиться в буфере основной памяти что увеличивает скорость поиска записи. Поскольку ключи отсортированы, можно воспользоваться бинарным поиском. В кластерных индексах с дублированными ключами редкий индекс указывает на наименьший ключ в каждом блоке.
5. Понятие индексов
5. Понятие индексов
Создание ключей в базовых отношениях автоматически связано с созданием индексов.
Дадим определение понятия индекса.
Индекс – это системная структура данных, в которой размещается обязательно упорядоченный перечень значений какого-либо ключа со ссылками на те кортежи отношения, в которых эти значения встречаются.
Индексы в системах управления базами данных бывают двух видов:
1) простые.
Простой индекс берется для подсхемы схемы базового отношения из одного атрибута;
2) составные.
Соответственно составной индекс – это индекс для подсхемы, состоящей из нескольких атрибутов.
Но, кроме деления на простые и составные индексы, в системах управления базами данных существует деление индексов на уникальные и неуникальные. Итак:
1) уникальные индексы – это индексы, ссылающиеся не более чем на один атрибут.
Уникальные индексы, как правило, соответствуют первичному ключу отношения;
2) неуникальные индексы – это индексы, могущие соответствовать нескольким атрибутам одновременно.
Неуникальные ключи, в свою очередь, чаще всего соответствуют внешним ключам отношения.
Рассмотрим пример, иллюстрирующий деление индексов на уникальные и неуникальные, т. е. рассмотрим следующие отношения, заданные таблицами:
Здесь соответственно Primary key – первичный ключ отношения, Foreign key – внешний ключ. Понятно, что в этих отношениях, индекс атрибута Primary key – уникальный, так как он соответствует первичному ключу, т. е. одному атрибуту, а индекс атрибута Foreign key – неуникальный, ведь он соответствует ключам внешним. И его значение «20» соответствует одновременно первой и третьей строкам таблицы-отношения.
Но иногда индексы могут создаваться без отношения к ключам. Это делается в системах управления базами данных для поддержки производительности операций сортировки и поиска.
Например, дихотомический поиск значения индекса в кортежах будет реализован в системах управления базами данных за двадцать итераций. Откуда получены эти сведения? Они были получены путем несложных вычислений, т. е. следующим образом:
10 6 = (10 3 ) 2 = 2 20 ;
Создаются индексы в системах управления базами данных при помощи уже известного нам оператора Create, но только с добавлением ключевого слова index. Выглядит такой оператор следующим образом:
Create index имя индекса
On имя базового отношения (имя атрибута. );
Здесь мы видим знакомый нам металингвистический символ «. », обозначающий возможность повтора аргумента через запятую, т. е. в этом операторе может быть создан индекс, соответствующий нескольким атрибутам.
Если требуется объявить уникальный индекс, перед словом index добавляют ключевое слово unique, и тогда весь оператор создания в базовом отношении индекса принимает следующий вид:
Create unique index имя индекса
On имя базового отношения (имя атрибута);
Тогда в самом общем виде, если вспомнить правило обозначения необязательных элементов (металингвистический символ []), оператор создания индекса в базовом отношении будет выглядеть следующим образом:
Create [unique] index имя индекса
On имя базового отношения (имя атрибута. );
Если требуется удалить из базового отношения уже имеющийся индекс, используют оператор Drop, также уже известный нам:
Drop index <имя базового отношения. Имя индекса>. ;
Почему здесь используется уточненное имя индекса «имя базового отношения. Имя индекса»? В операторе удаления индекса всегда используется его уточненное имя, потому что имя индекса должно быть уникальным в пределах одного отношения, но не больше.
Данный текст является ознакомительным фрагментом.
Продолжение на ЛитРес
Читайте также
4.1.3 Освобождение индексов
4.1.3 Освобождение индексов В том случае, когда ядро освобождает индекс (алгоритм iput, Рисунок 4.4), оно уменьшает значение счетчика ссылок для него. Если это значение становится равным 0, ядро переписывает индекс на диск в том случае, когда копия индекса в памяти отличается от
Сравнение индексов
Сравнение индексов Изучая поисковые индексы «Яндекс» и Google с помощью операторов inurl: и site, мы можем найти разницу в количестве проиндексированных страниц по сайту в целом и по каждому кластеру в частности. Это самая простая и эффективная проверка сайта на ошибки,
Применение индексов
Применение индексов Теперь, когда ясно, что можно требовать от индексов, настало время разобраться с тем, какую роль они играют в базе данных. Индексы используются в трех основных случаях:* Ускорение выполнения запросов. Индексы создаются для полей, которые используются
Ускорение выполнения запросов с помощью индексов
Ускорение выполнения запросов с помощью индексов Выше описано, что применение индексов может значительно ускорить выполнение запросов. Это действительно так для большинства случаев, но есть и определенные оговорки. Сначала ответим на вопрос, часто возникающий у тех,
Обеспечение ссылочной целостности с помощью индексов
Оптимизация производительности индексов
Статистика страниц индексов
Имена индексов ограничений
Имена индексов ограничений Использование явных планов в Yaffil в триггерах и процедурах существенно упрощается благодаря возможности именования индексов, автоматически создаваемых сервером для ограничений первичных, внешних ключей и ограничений уникальности. В версиях
Определение индексов и первичного ключа
2.4.4. Создание таблиц и индексов в Falcon
2.4.4. Создание таблиц и индексов в Falcon Falcon поддерживает все стандартные типы данных столбцов, обеспечиваемые MySQL.Чтобы создать таблицу, которая использует Falcon, примените опцию ENGINE = Falcon в инструкции CREATE TABLE:CREATE TABLE names (id INT, fname VARCHAR (20),lname VARCHAR (20)) ENGINE=FalconИндексы могут быть
4.6.1. Создание пространственных индексов
4.6.1. Создание пространственных индексов MySQL может создавать пространственные индексы, использующие синтаксис, подобный аналогичному для создания регулярных индексов, но расширенный с ключевым словом SPATIAL. В настоящее время пространственные столбцы, которые
2.2.4 Поддержка фрагментации таблиц и индексов
2.2.4 Поддержка фрагментации таблиц и индексов INFORMIX-OnLine DS поддерживает горизонтальную локальную фрагментацию таблиц. Это такой способ хранения таблицы, когда совокупность ее строк разбивается на несколько групп согласно некоторому правилу, и эти группы хранятся на
Импорт существующих индексов
Импорт существующих индексов Не импортируйте «первичные индексы» таблиц при миграции из другой СУБД. Есть две важные причины отказаться от таких индексов.* Многие существующие системы используют иерархические структуры индексов для реализации ссылочной целостности.
Просмотр индексов
Просмотр индексов Для просмотра всех индексов, определенных в текущей базе данных, используйте в isql команду SHOW INDEX:* чтобы просмотреть все индексы, определенные для конкретной таблицы, используйте команду:SHOW INDEX имя-таблицы;* для просмотра информации конкретного индекса
Действия по обслуживанию индексов
Действия по обслуживанию индексов Индексы являются двоичными структурами, которые могут стать разбалансированными после многих изменений базы данных, особенно если вы пренебрегаете общим обслуживанием базы данных. Индексы могут быть сделаны сбалансированными[55]
15) Индексирование в базах данных
Что такое индексирование?
INDEXING — это метод структуры данных, который позволяет вам быстро извлекать записи из файла базы данных. Индекс — это небольшая таблица, имеющая всего два столбца. Первый столбец содержит копию первичного или потенциального ключа таблицы. Его второй столбец содержит набор указателей для хранения адреса дискового блока, где хранится это конкретное значение ключа.
Из этого руководства по индексированию СУБД вы узнаете:
Типы индексации
Индексация базы данных определяется на основе ее атрибутов индексации. Два основных типа методов индексации:
Первичная индексация
Первичный индекс — это упорядоченный файл с фиксированной длиной и двумя полями. Первое поле — это тот же первичный ключ, а второе поле указывает на этот конкретный блок данных. В первичном индексе всегда существует отношение один к одному между записями в таблице индекса.
Первичная индексация также делится на два типа.
Плотный индекс
В плотном индексе запись создается для каждого поискового ключа, оцененного в базе данных. Это помогает быстрее выполнять поиск, но требует больше места для хранения записей индекса. В этом индексировании записи метода содержат значение ключа поиска и указывают на реальную запись на диске.
Разреженный индекс
Это индексная запись, которая отображается только для некоторых значений в файле. Разреженный индекс поможет вам решить проблемы плотного индексирования. В этом методе методики индексирования диапазон столбцов индекса хранит один и тот же адрес блока данных, и когда данные должны быть извлечены, адрес блока будет выбран.
Однако разреженный индекс хранит записи индекса только для некоторых значений ключа поиска. Ему требуется меньше места, меньше затрат на обслуживание для вставки и удаления, но он медленнее по сравнению с плотным индексом для поиска записей.
Пример разреженного индекса
Вторичный индекс
Вторичный индекс может быть создан с помощью поля, которое имеет уникальное значение для каждой записи, и это должен быть ключ-кандидат. Он также известен как некластеризованный индекс.
Этот двухуровневый метод индексации базы данных используется для уменьшения размера отображения первого уровня. Для первого уровня из-за этого выбирается большой диапазон чисел; размер отображения всегда остается небольшим.
Пример вторичной индексации
В базе данных банковского счета данные хранятся последовательно с помощью acc_no; Вы можете найти все счета в конкретном отделении банка ABC.
Здесь вы можете иметь вторичный индекс для каждого поискового ключа. Индексная запись — это точка записи в корзину, которая содержит указатели на все записи с определенным значением ключа поиска.
Индекс кластеризации
В кластеризованном индексе сами записи хранятся в индексе, а не в указателях. Иногда индекс создается для столбцов не первичного ключа, которые могут быть не уникальными для каждой записи. В такой ситуации вы можете сгруппировать два или более столбцов, чтобы получить уникальные значения и создать индекс, который называется кластеризованным индексом. Это также поможет вам быстрее идентифицировать запись.
Пример:
Давайте предположим, что компания набрала много сотрудников в различных отделах. В этом случае кластерная индексация должна быть создана для всех сотрудников, принадлежащих к одному отделу.
Он рассматривается в одном кластере, а индексные точки указывают на кластер в целом. Здесь Department _no — неуникальный ключ.
Что такое многоуровневый индекс?
Многоуровневое индексирование создается, когда первичный индекс не помещается в памяти. В этом методе индексации вы можете сократить число обращений к диску, чтобы сократить любую запись и сохранить ее на диске в виде последовательного файла, а также создать разреженную базу для этого файла.
B-Tree Index
Индекс B-дерева — это широко используемые структуры данных для индексации. Это метод многоуровневого индексного формата, который сбалансирован бинарными деревьями поиска. Все конечные узлы дерева B обозначают фактические указатели данных.
Более того, все конечные узлы связаны между собой списком ссылок, что позволяет дереву B поддерживать как произвольный, так и последовательный доступ.
Преимущества индексации
Важные плюсы / преимущества индексирования:
Недостатки индексации
Важными недостатками / минусами индексации являются:
Что такое индексы базы данных (для начинающих)?
Многие слышали о том, что индексы в базах данных это весьма полезная штука. Но, одно дело слышать, а другое представлять себе их устройство хотя бы на базовом уровне. Поэтому в рамках данной статьи для начинающих, я рассмотрю этот вопрос, применяя простые и понятные каждому выражения и аналогии из жизни.
Что такое индекс базы данных и зачем он нужен?
Чтобы понять зачем нужны индексы в базе данных и что он собой представляет, сейчас рассмотрим простой пример.
Представьте себе, что у вас есть полочка для книг. При этом изначально эта полочка с книгами пуста. Книги вам то приносят, то уносят, то делают в них какие-то корректировки (к примеру, мемуары или может быть черновики) и тому подобное.
Так как полочка маленькая, то вы как-то не особо задумывались о какой-либо системе классификации, а просто вставляете книги в любые пустые места.
Каждый раз когда-то вам или кому-то необходимо найти определенную книгу, возникает необходимость просматривать все книги с самого начала полочки до первой попавшейся (если нужна только одна книга) или полностью все (если нужно собрать все копии). В принципе, для одной полочки это весьма необременительно.
Теперь, представьте себе, что речь идет не об одной полочке, а об огромном помещении, где находятся тысячи книг.
Тут-то вы и начинаете задумываться о том, что неплохо бы ввести какую-то систему классификации, например, по названию книги. Конечно, полностью сортировать все эти тысячи книг в алфавитном порядке вы не собираетесь, плюс с этим возникло бы куча других вопросов (как добавить книгу в уже заполненную полку и прочие).
Поэтому вы поступаете проще, вы берете каталог, где возможно добавлять листочки. При этом каждую страницу выделяете только под одно название книги, а сами страницы располагаете в каталоге в порядке возрастания названий. Содержание этих страниц весьма просто — вы записываете в каком стеллаже, на какой полке и какой по счету является книга. Если книг несколько, то строчек в этой странице становится несколько.
Таким образом, чтобы найти одну или все нужные книги по названию, вам достаточно открыть этот каталог и быстро пролестнуть до нужной страницы, а затем пройтись по всем указанным стеллажам. При этом для упрощения, вы так же можете первые буквы названий так же индексировать. То есть добавляете наклейку на каждую первую страницу с указанной буквой (таким образом можете сразу перейти, например, к букве «Р», не пролистывая все названия до нее).
Конечно, для поддержки такой системы требуется дополнительное время, но все же оно существенно меньше, чем попытка найти вслепую книгу из тысячи (пара минут против нескольких часов и более).
Так вот, в данном примере, если переносить это в базу данных:
Помещение — это таблица в базе данных. Если чуть проще, то любое скопище однотипных данных (тех же книг), по сути, представляет собой таблицу.
Поиск книги — это sql-запросы получения данных. При этом важно отметить, что сами по себе они не меняются. То есть вам как нужно было найти «Термодинамику», так и осталось нужным найти «Термодинамику». Другое дело, как вы будете это осуществлять — прочесывая тысячи книг или открыв каталог.
Каталог — это и есть упрощенный вариант индекса в базе данных. То есть, индекс это набор дополнительных данных, записанных в удобном виде, который позволяет существенно быстрее осуществлять поиск, хоть и требующий дополнительных усилий для поддерживания его актуальности.
Имя книги (страничка) — это ключ в индексе. То уникальное значение, которое может ссылаться как на одну какую-то запись, так и на несколько. Стоит отметить, что даже если записей для каждого значения будет несколько, это все равно быстрее, чем полный перебор всех данных.
Если суммировать, то можно увидеть, что наличие индекса может быть весьма выгодным. Например, для одной домашней полочки с десятком книг — индекс в общем-то не сильно нужен, а вот когда речь заходит о более больших объемах, то индекс будет весьма полезным.
Так же можно заметить, что добавление индекса не требует того, чтобы сами sql-запросы были переписаны, так как последние являются лишь выражением на упрощенном языке для базы данных. Если продолжить аналогию, то это как попросить кого-то найти вам «Флора и фауна». При этом каким образом и сколько этот кто-то будет искать книгу, будет решать сам этот человек. В данном примере «найти книгу» — это sql-запрос, а этот «кто-то» это база данных.
Какие бывают индексы?
Вообще, в зависимости от типов баз данных, индексы могут быть очень разными и реализоваться за счет специфических математических механизмов. Но, наиболее частым является древовидный индекс, так как поддерживать такой индекс относительно просто и максимальная скорость поиска в нем составляет логарифм по числу максимального количества дочерних узлом от общего количества записей (плюс минус некоторые технические моменты).
Дерево (древовидный индекс) — это специального вида структура, у которой есть корневая вершина и у каждого узла может быть несколько дочерних узлов. При этом каждый узел встречается только один раз и может иметь всего один родительский узел. Выглядит это так:
Как видите, очень похоже на перевернутое обычное зеленое дерево, у которого ветки растут не вверх, а вниз.
Максимальное количество дочерних узлов, как вероятно уже догадались по картинке, это то количество дочерних узлов, больше которого у одного узла не может быть.
Теперь поясню откуда берется логарифм. Дело в том, что дерево обычно заполняется по определенным правилам. К примеру, если у узла максимально может быть всего два дочерних узла (так называемое бинарное дерево), то обычно левый дочерний узел имеет значение меньше текущего, а правый большее значение. Поэтому если вам нужно найти, например, число 30 в дереве с рисунка чуть выше, то вам понадобится всего 4 сравнения (40 — 25 — 32 — 30). Именно из-за этой особенности поиска и берется логарифм (так как каждое сравнение сокращает количество проверяемых элементов в два раза). При этом обычно значение логарифма округляют в большую сторону.
Так же отмечу, что такая скорость достигается за счет того, что дерево строится специальным образом, чтобы не возникало таких ситуаций, как на картинке ниже, где максимальная скорость поиска будет сравнима с простым перебором всех записей.
Как видите, чтобы здесь найти запись с ключом «3» понадобится 4 сравнения (40 — 25 — 10 — 3), хотя всего записей 5.
Практически во всех базах данных, существует деление по уникальности:
Уникальный индекс — это такой индекс, у которого все значения встречаются только один раз. Проводя аналогию, когда каждая книга присутствует только в одном экземпляре и никогда названия книг не совпадают.
Неуникальный индекс — это такой индекс, у которого значения могут повторяться. Проводя аналогию, существуют книги с одними и теми же названиями, но разными авторами, или же просто встречаются копии.
Важно отметить, что если для таблицы создается уникальный индекс, то это означает, что при попытке добавить запись со значением, которое уже встречалось, или же изменить значение какой-то записи на существующее, то база данных не позволит сделать такое действие и будет ругаться (выдавать ошибки). В случае же с неуникальным индексом таких проблем нет.
Так же стоит знать, что индексы делятся по количеству входящих в них полей:
Обычные индексы — состоят из одного поля. Здесь, вероятно, все понятно. Обычный каталог страничек.
Составные индексы — строятся по нескольким полям, при этом расположение полей является важным.
Чуть подробнее про составные индексы. Рассмотрим аналогию с теми же книгами. До этого индекс строился только по названию. Теперь же представим, что книги с одинаковыми названиями часто встречаются. В такой ситуации, легко может получится, что страничка каталога будет состоять из координат сотен книг (десятки авторов и у каждого по десять копий). Бегать их всех проверять — так же немалое количество времени. Поэтому вместо того, чтобы страничка просто перечисляла все местонахождения книг, можно сделать так, чтобы странички с именами книг указывали на дополнительные каталоги, где аналогичным образом проиндексированы авторы.
Немного упрощая, поиск будет выглядит примерно так.
1. Вначале вы ищите в каталоге с именами необходимую страничку с названием.
2. Затем в этой страничке смотрите, где находится соответствующий каталог с авторами.
3. Берете этот каталог и уже в нем находите страничку, где указано месторасположение всех книг с этим автором и названием.
При этом важно понимать, что для каждого названия будет создаваться собственный каталог авторов. То есть в обратном порядке, к сожалению, поиск не осуществить. Если же требуется поиск вначале по автору, а уже затем по названиям книг, то необходимо создавать отдельный составной каталог (составной индекс).
Существуют и другие моменты, но чаще всего достаточно знать хотя бы эти базовые знания.