Индексирование

Индексирование

Материал из ПИЭ.Wiki

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

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

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

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

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

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

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

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

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

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

Главными целями создания индексов в БД являются:

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

На этапе создания физической модели данных ХД нужно принять последовательность серьёзных ответов о том, что и как индексировать; наряду с этим принципиально важно четко сформулировать правила индексирования. Для каждого ИТ-проекта с ХД нужно создать и оформить в письменном виде правила индексирования как часть неспециализированных правил обеспечения производительности. сопровождение и Поддержка индексов в ходе эксплуатации ХД есть по большей части задачей администратора БД.

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

Разработка таких правил существенно повысит уровень качества эксплуатации ХД с позиций обеспечения ее производительности.

Дабы решать эти задачи, проектировщик обязан знать, как трудится индекс, какие конкретно типы индексов поддерживает СУБД, и осознавать суть способов индексирования.

Индекс со структурой B-Tree

Индекс на базе сбалансированной иерархической структуры (либо индекс B-Tree, balanced tree structured object) напоминает дерево, в случае если наблюдать на него снизу вверх. При работе СУБД с данной структурой сперва считывается самый верхний блок — корневой узел (root), после этого блок на следующем уровне — блок-ветвь (branch), и без того потом, до тех пор, пока не будет извлечен блок-лист (leaf) с индексируемыми колонками (колонкой) строчка. Обратим внимание, что значения индексируемых колонок сохраняется в индексе (рис.

1.1).

Такая структура разрешает минимизировать число операций ввода-вывода. Для получения индексируемых колонок строчка в большинстве случаев требуется одно посещение блока-страницы, т.е. физической страницы файловой структуры БД, отведенной под индекс.

Рис. 1.1. Концептуальная организация B-Tree индекса

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

  1. в то время, когда строка имеет длину более одной физической страницы файловой структуры БД — так называемая расщепленная строка ;

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

Индекс B-Tree характеризуется числом уровней в индексе – высотой (height). Чем меньше уровней, тем выше производительность.

Индекс B-Tree — это физический объект реляционной БД, организованный по принципу сбалансированной иерархической структуры и владеющий комплектом особенностей. Сформулируем кое-какие свойства индексов со структурой B-Tree.

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

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

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

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

Индексы смогут быть выстроены для нескольких колонок таблицы — так называемый составной индекс. СУБД применяет составные индексы для исполнения тех запросов, в которых задана лидирующая часть составного ключа. К примеру, составной индекс для обработки запроса SELECT * FROM EMPLOYEE WHERE Job=’Инженер’; использоваться не будет.

СУБД в большинстве случаев сама принимает ответ, применять индекс либо нет.

Значения колонок NULL не индексируются. В случае если для таких колонок строится индекс, то СУБД будет отказываться использовать его в некоторых операциях, к примеру, ORDER BY .

В СУБД семейства MS SQL Server все индексы организованы на базе сбалансированной иерархической структуры. Кроме того, что индексы владеют особенностями уникальности ( UNIQUE ) и неуникальности, индексы в СУБД семейства MS SQL Server смогут быть кластеризованными ( CLUSTERED ) либо некластеризованными ( NONCLUSTERED ), являющимися индексами по умолчанию.

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

Некластеризованный индекс – это индекс, в котором задается логическое упорядочение для таблицы. Логический порядок строчков в некластеризованном индексе не воздействует на их физический порядок. Для каждой таблицы возможно создать до 999 некластеризованных индексов, независимо от того, как они создаются: неявно, посредством ограничений PRIMARY KEY и UNIQUE. либо очевидно, посредством команды CREATE INDEX .

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

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

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

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

В зависимости от типов данных любая структура кластеризованного индекса складывается из одной либо более единиц распределения, каковые используются для управления и хранения данными секциями. Для каждой секции кластеризованный индекс содержит как минимум одну единицу распределения IN_ROW_DATA. Для хранения столбцов громадных объектов ( LOB ) кластеризованному индексу требуется одна единица распределения LOB_DATA для каждой секции. Помимо этого, для хранения строчков переменной длины, каковые превышают ограничение на размер строчка, равное 8 060 байтам, для каждой секции требуется одна единица распределения ROW_OVERFLOW_DATA .

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

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

Указатели строчков на строчках некластеризованных индексов являются или указателем на строчок, или ключом кластеризованного индекса для строчка, как обрисовано ниже.

В случае если таблица есть кучей (другими словами не содержит кластеризованный индекс ), то указатель строчка есть указателем на строчок. Указатель строится на базе идентификатора файла ( ID ), номера строки и номера страницы на странице. Целый указатель полностью именуется идентификатором строчка ( RID ).

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

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

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

В зависимости от типов данных в некластеризованном индексе любая его структура будет содержать одну либо более единиц распределения, в которых сохраняются эти для определенной секции. Любой некластеризованный индекс будет иметь как минимум одну единицу распределения IN_ROW_DATA на секцию, в которой сохраняются страницы сбалансированного дерева индекса. Некластеризованный индекс будет кроме этого содержать одну единицу распределения LOB_DATA на секцию, в случае если в индексе имеется столбцы типа громадного объекта (LOB). Помимо этого, некластеризованный индекс

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

Только другие типы и индексные таблицы индексов на базе B-Tree

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

В некоторых СУБД, в частности в СУБД Oracle, только индексные таблицы поддерживаются. Только индексная таблица есть индексом типа B-Tree БД, что в один момент выполняет роль таблицы. Все сведенья таковой таблицы сохраняются в индексе.

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

Только индексная таблица в СУБД Oracle создается посредством команды SQL CREATE TABLE.

Команда CREATE TABLE не отличается ничем от вторых команд создания таблиц — до тех пор, пока не встретится предложение ORGANIZATION INDEX. которое показывает СУБД на создание только индексной таблицы. Для размещения индекса на диске указывается табличное пространство.

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

В СУБД семейства MS SQL Server нет предопределенной возможности создавать только индексные таблицы. Но в ряде практических случаев в СУБД этого семейства возможно создавать структуры, подобные только индексным таблицам. Для этого возможно использован некластеризованный индекс с включенными колонками (опция INCLUDE команды CREATE INDEX ).

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

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

Любой бит так именуемого битового (bitmap) индекса относится к идентификатору строчка ROWID (что в Oracle создается и хранится для каждой строки и употребляется во внутренней организации индексов ) в табличном объекте. В случае если некая строка содержит данное главное значение, то в индексе для этого значения сохраняется единица.

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

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

В СУБД семейства MS SQL Server возможность создания битовых индексов средствами диалекта SQL отсутствует.

В индексе с обращением ключа (reverse-key index) используется обращение байтов индексируемой колонки числового типа. Данный прием разрешает приобретать равномерное распределение значений колонок среди блоков-листков индекса со структурой B-Tree, что прекрасно подходит для индексирования колонок с последовательной нумерацией либо нумерацией с заданным шагом.

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

В СУБД семейства MS SQL Server возможность создания индексов с обращением значения ключа средствами диалекта SQL отсутствует.

В случае если в предложении WHERE используется функция по индексированной колонке, то в большинстве случаев СУБД не применяют данный индекс при организации доступа к строчкам таблицы. Но при создании индекса на базе значения функции (function-based index), которая есть той же функцией, что и в предложении WHERE. СУБД как семейства Oracle, так и семейства MS SQL Server применяет таковой индекс для считывания строчков, удовлетворяющих критерию отбора.

В СУБД семейства MS SQL Server вычисляемые колонки смогут иметь свойство PERSISTED. Это указывает, что компонент Database Engine хранит вычисленные значения в таблице и обновляет их при обновлении любых колонок, от которых зависит вычисляемый столбец. Компонент Database Engine применяет эти материализованные значения, в то время, когда формирует индекс по колонке и в то время, когда запрос обращается к индексу.

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

  1. вычисляемые столбцы, основанные на выражениях языка Transact-SQL, функциях CLR и способах пользовательских типов данных CLR, отмеченных пользователем как детерминированные;
  2. вычисляемые столбцы, основанные на выражениях, каковые выяснены компонентом Database Engine как детерминированные, но не являются правильными.

При наличии в БД для того чтобы индекса СУБД будет его применять при обработке запроса обрисованного в данном примере.

В СУБД семейства MS SQL Server возможно создавать и применять фильтрованные индексы, для таких индексов в команде CREATE INDEX предусмотрена возможность применения предложения WHERE

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

Предикат фильтра применяет несложную логику сравнения и не имеет возможности ссылаться на вычисляемый столбец, столбец определяемого пользователем типа, столбец пространственного типа данных либо столбец типа hierarchyID. Сравнения посредством литералов NULL с операторами сравнения недопустимы. Вместо этого употребляются операторы IS NULL и IS NOT NULL .

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

О некоторых параметрах проектирования индексов

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

Кардинальностью колонки (cardinality) таблицы именуется число дискретных разных значений колонки, каковые видятся в строчках таблицы. К примеру, в случае если в таблице Служащий (EMPLOYEE) мы заводим колонку для указания пола – Пол (SEX), то кардинальность данной колонки имеется 2, так в природе у людей существует лишь два пола — мужской и женский. Для колонки первичного ключа кардинальность будет равна числу строчков в таблице.

Обстоятельство, по которой кардинальность колонки серьёзна для проектирования индексов, пребывает в том, что кардинальность индексируемой колонки определяет число неповторимых входов, каковые должны сберигаться в индексе, т.е. число записей в индексе. Так, для индексируемой колонки Пол (SEX) будут существовать два неповторимых входа, каковые будут повторяться неоднократно в индексе.

При предположении равновероятного распределения пола сотрудников на 100000 строчков в таблице Служащий (EMPLOYEE) любой вход индекса будет повторяться 50000 раз. СУБД вряд ли будут принимать ответ об применении для того чтобы индекса при построении замысла запроса.

Выяснить кардинальность потенциальной колонки индексирования в существующей таблице БД достаточно легко.

SELECT COUNT (DISTINCT колонка) FROM таблица;

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

Хорошими кандидатами для индексирования в большинстве случаев являются:

  • колонки первичного ключа. По определению, колонки первичного ключа должны иметь неповторимый индекс ;

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

  • каждые колонки, каковые содержат неповторимые значения;
  • колонки, запросы либо соединения, каковые применяют от 5 до 10% строчков таблицы;
  • колонки, каковые довольно часто входят как доводы в функции агрегирования;
  • колонки, каковые довольно часто употребляются для проверки правильности ввода данных в программах ввода-редактирования.
  • Факторы, воздействующие на низкую эффективность индексов:

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

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

    асимметрия значений ключей (Skewness of keys). В случае если распределение значений ключа имеет большую асимметрию, то кардинальность индекса может оказаться высокой и СУБД из-за низкого фактора селективности будет довольно часто применять данный индекс. Но итог применения индекса будет неудовлетворительным по причине того, что большая часть строчков таблицы имеет одно да и то же значение ключа, что приведет к нивелированию цены применения индекса по сравнению со сканирование всей таблицы.

    Нехорошими кандидатами для индексирования в большинстве случаев являются:

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

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

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

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

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

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

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

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

    Рис. 1.2. Черта колонок для индексов

    Источник: wiki.mvtom.ru

    Урок #63. Что такое индексирование

    Важное на сайте:

    Самые интересные результаты статей, подобранные именно по Вашим интересам: