Индексирование данных. Индексированные файлы

Определим индексирование как способ доступа к данным в реляци-онной таблице с помощью специальной структуры – индекса.

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

Рис. 4.3. Пример индекса

Индекс обычно хранится в отдельном файле или отдельной области па-мяти. Пустые значения атрибутов (NULL) не индексируются.

Индексирование используется для ускорения доступа к записям по значению ключа и не влияет на размещение данных этой таблицы. Ускорение поиска данных через индекс обеспечивается за счёт:

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

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

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

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

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

Различают индексы по одному полю и по нескольким (составные). Составной индекс включает два или более столбца одной таблицы (рис. 4.4). Последовательность вхождения столбцов в индекс определяется при его создании. Из примера на рис. 4.4 видно, что данные в индексе отсортированы по первому столбцу (ID), внутри группы с одинаковыми значениями ID – отсортированы по второму столбцу (EDATE), а внутри группы с одинаковыми значениями ID и EDATE – по третьему столбцу (CODE).

Источник

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

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

PHP-разработчик digital-агентства «Атвинта», в свободное время пишу на Go/C#/C++. Нравится проектировать и продумывать highload-системы.

Базы данных — это совсем не сложно, даже новички быстро вливаются в тему и начинают работать практически без проблем. А что сложного? Есть таблицы, в них записываем строки — всё просто. Да, и всё работает, никто не жалуется. Пока не наступит момент… когда данных будет много.

Тут нам и приходят на помощь индексы. Во всех базах данных они работают примерно по одному и тому же принципу. В этой статье я буду использовать MariaDB.

Запрос на выборку без индексов

Рассмотрим на простом примере. Есть таблица articles со следующей структурой:

Добавим в таблицу несколько записей:

И сделаем следующий запрос:

Ничего удивительного: простой запрос и выполняется быстро. Но что будет, если данных «чуть-чуть» больше? Давайте добавим, например, 2 млн статей.

И повторим запрос на выборку:

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

Две секунды на выполнение запроса — не предел; когда данных ещё больше, всё будет ещё хуже. Оптимизировать этот запрос можно с помощью индексов.

Запрос на выборку с индексом

Создаем индекс по колонке views из таблицы articles.

И повторяем запрос:

Вот! Так намного лучше. Выборка проходит так же быстро, как и с тремя записями. В чём же подвох? Как это работает и почему? Что может пойти не так?

Как устроен запрос без индекса и с ним

Запрос к выборке БД без индекса

Что происходит, когда мы запрашиваем данные? А что вы делаете, когда ищете нужную вам строку в таблице? Да, база данных сканирует всю таблицу и выбирает те записи, которые попадают под условия.

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

Запрос к выборке БД с индексом

Я часто встречаю, что индекс путают с id или уникальным идентификатором, считают, что это одно и то же. Это не так! Индекс в базах данных — это другое.

Индекс, который мы создали, представляет из себя такую структуру данных, как B-дерево. Но, например, в InnoDB используется B+-дерево. Всё зависит от подсистемы хранения, а в целом принцип их работы похож. Это дерево строится по колонке views из таблицы articles.

Чтобы понять, как происходит выборка с индексом, нужно знать, как работает B-дерево.

Перед нами B-дерево индекса. В каждом узле хранятся элементы со значениями; в нашем случае это значения из поля views. Также элементы хранят ссылку на строку в таблице.

Поиск начинается с корневого узла. Наша задача — пройти по каждому элементу в узле и сравнить его значение с искомым:

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

Рассмотрим алгоритм на примере поиска значения 2001.

То, что мы и искали. А так как искомая ячейка содержит ссылку на место, где лежат наши данные, то мы можем легко и быстро прочитать их.

Ещё один способ запроса с индексом

В данной структуре можно легко делать выборку по диапазонам, например views >= 1000. В случае таких запросов индекс также поможет.

Хоть поиск и значительно ускорился, есть и свои нюансы. Изменения в В-дереве — не самая быстрая операция.

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

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

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

Мы рассмотрели создание индекса по одной колонке (views), но в базах данных одной колонкой не ограничишься. Можно создавать составные индексы. Например, если есть поле views и дата created_at, и вы хотите делать подобные запросы: views = 1000 and created_at = «10.10.2019», то имеет смысл создать индекс по двум колонкам.

Источник

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

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

Хотя индексы, строго говоря, не являются обязательным компонентом СУБД, они могут существенным образом повысить ее производительность. Как и в случае с предметным указателем книги, читатель может найти определение интересующего его понятия, просмотрев всю книгу, но это потребует слишком много времени. А предметный указатель, ключевые слова в котором расположены в алфавитном порядке, позволяют сразу же перейти на нужную страницу.

Структура индекса связана с определенным ключом поиска и содержит записи, состоящие из ключевого значения и адреса логической записи в файле, содержащей это ключевое значение. Файл, содержащий логические записи, называется файлом данных, а файл, содержащий индексные записи, — индексным файлом. Значения в индексном файле упорядочены по полю индексирования, которое обычно строится на базе одного атрибута.

Типы индексов

Для ускорения доступа к данным применяется несколько типов индексов.

Основные из них перечислены ниже.

Файл может иметь не больше одного первичного индекса или одного индекса кластеризации, но дополнительно к ним может иметь несколько вторичных индексов. Индекс может быть разреженным (sparse) или плотным (dense). Разреженный индекс содержит индексные записи только для некоторых значений ключа поиска в данном файле, а плотный индекс имеет индексные записи для всех значений ключа поиска в данном файле. Ключ поиска для индекса может состоять из нескольких полей.

Индексно-последовательные файлы

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

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

Вторичные индексы

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

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

Многоуровневые индексы

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

Усовершенствованные сбалансированные древовидные индексы

Поскольку время доступа в древовидной структуре зависит от глубины, а не от ширины, обычно принято использовать более «разветвленные» и менее глубокие деревья.

Усовершенствованные сбалансированные древовидные индексы определяются по следующим правилам.

Источник

Создание и использование индекса для увеличения производительности

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

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

В этой статье

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

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

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

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

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

Примечание: Первичный ключ таблицы индексируется автоматически.

Индексировать поля с типом данных «Объект OLE», «Вычисляемый» или «Вложение» невозможно. Индексировать другие поля следует в тех случаях, когда выполняются все указанные ниже условия.

Тип данных поля: «Короткий текст» («Текст» в Access 2010), «Длинный текст» («Поле МЕМО» в Access 2010), «Число», «Дата/время», «Автонум», «Валюта», «Да/Нет» или «Гиперссылка».

Предполагается поиск значений в поле.

Предполагается сортировка значений в поле.

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

Составные индексы

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

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

В составной индекс можно включить до 10 полей.

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

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

Параметр свойства «Индексированное поле»

Не создавать индекс для этого поля (или удалить существующий индекс)

Да (допускаются совпадения)

Создать индекс для этого поля

Да (совпадения не допускаются)

Создать уникальный индекс для этого поля

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

Создание индекса для одного поля

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

Щелкните пункт Имя поля для поля, которое следует индексировать.

В разделе Свойства поля откройте вкладку Общие.

В свойстве Индексированное выберите значение Да (допускаются совпадения), если следует разрешить повторяющиеся значения, или значение Да (совпадения не допускаются), чтобы создать уникальный индекс.

Чтобы сохранить изменения, щелкните элемент Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.

Создание составного индекса

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

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

На вкладке Конструктор в группе Показать или скрыть щелкните пункт Индексы.

Появится окно «Индексы». Измените размеры этого окна, чтобы отображались пустые строки и свойства индекса.

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

В столбце Имя поля щелкните стрелку, затем щелкните первое поле, которое следует использовать в индексе.

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

Чтобы изменить порядок сортировки значений полей, в столбце Порядок сортировки окна «Индексы» щелкните пункт По возрастанию или По убыванию. По умолчанию выполняется сортировка по возрастанию.

В разделе Свойства индекса окна Индексы укажите свойства индекса для строки в столбце Имя индекса, содержащем имя индекса. Задайте свойства в соответствии с таблицей ниже.

Если Да, то индекс является первичным ключом.

Если Да, то каждое индексируемое значение должно быть уникальным.

Пропуск пустых полей

Если Да, то записи с пустыми значениями в индексируемых полях будут исключены из индекса.

Чтобы сохранить изменения, нажмите кнопку Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.

Закройте окно «Индексы».

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

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

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

На вкладке Конструктор в группе Показать или скрыть щелкните пункт Индексы.

Появится окно «Индексы». Измените размеры этого окна, чтобы отображались пустые строки и свойства индекса.

В окне «Индексы» выделите строки, содержащие индекс, который следует удалить, и нажмите клавишу DELETE.

Чтобы сохранить изменения, нажмите кнопку Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.

Закройте окно Индексы

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

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

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

На вкладке Конструктор в группе Показать или скрыть щелкните пункт Индексы.

Появится окно «Индексы». Измените размеры этого окна, чтобы отображались пустые строки и свойства индекса.

Просмотрите или измените индексы и свойства индексов в соответствии со своими задачами.

Чтобы сохранить изменения, нажмите кнопку Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.

Закройте окно Индексы

Автоматическое создание индексов

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

Для автоматического создания индекса также можно использовать параметр Автоиндекс при импорте и создании в диалоговом окне Параметры Access. Access автоматически проиндексирует все поля, имена которых начинаются с указанных в поле Автоиндекс при импорте и создании знаков или заканчиваются ими, например ID, ключ, код или число. Чтобы просмотреть или изменить текущие параметры, сделайте следующее:

Выберите Файл > Параметры.

Щелкните Конструкторы объектов, а затем в разделе Конструктор таблиц добавьте, измените или удалите значения в поле Автоиндекс при импорте и создании. Для разделения значений используйте точку с запятой ( ;).

Примечание: Если имя поля начинается со значения, указанного в списке, или заканчивается им, поле будет автоматически проиндексировано.

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

Источник