Сравнение метода полного индекса с индексно-последовательной организацией

1. В методе полного индекса не предусмотрена обработка переполнения; вместо этого всякий раз при включении новой записи в основной файл выполняется переупорядочивание индекса.

2. При отсутствии переполнения поиск всех записей в обоих методах имеют одинаковую производительность.

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

4. Вследствие физически последовательного размещения записей операции типа ПОЛУЧИТЬ СЛЕДУЮЩУЮ и ПОЛУЧИТЬ ПРЕДЫДУЩУЮ выполняются гораздо эффективнее в методе неплотного индекса.

5. Добавление, а так же изменение значений первичных ключей в основном файле в обоих методах трудоемко, поскольку, как правило, влечет обновление индекса.

6. В чем суть инвертирования.

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

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

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

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

 

 

Схема организации В-дерева

Частично инвертированный файл инвертируется по выборочному количеству неключевых атрибутов.

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

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

7. Что такое В-дерево.

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

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

Такие деревья называют сбалансированными (путь от корня до любого листа одинаков) Таким образом, термин В-дерево происходит от английского balance (баланс). Пример организации В-дерева представлен на рис.30.

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

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

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

8. Опишите механизмы использования битовых шкал.

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

Пример 1. Пусть основной файл содержит следующие записи:

 

01	S01	Иванов	Томск
02	S02	Петров	Томск
03	S03	Сидоров	Кемерово
04	S04	Кузнецов	Барнаул
05	S05	Петров	Омск

 

Значения элементов данных в полях записей отображают значения:

Поле1 – внутрисистемных номеров записей,

Поле2 – атрибута - первичного ключа,

Поле3 – атрибута – Фамилия_поставщика,

Поле4 – атрибута - Город, где живет поставщик.

Сформируем битовые строки, соответствующие следующим свойствам:

 

Свойство	Статья (битовая строка)
Фамилия_поставщика = “Петров”	0 1 0 0 1
Город = ”Томск”	1 1 0 0 0

 

Такая организация индекса имеет два важных достоинства:

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

2. Битовое представление индекса позволяет с высокой эффективностью выполнять операции выборки (селекции) записей по сложным логическим критериям, содержащим логические связки AND, OR и NOT, с помощью поразрядных логических операций над битовыми строками.

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

Пример 2. По этой схеме сформируем битовые строки для записей файла из Примера 1, соответствующие следующим свойствам:

Свойство 1. Фамилия_поставщика = “Петров”

Свойство 2. Город = “Томск”

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

 

Номер статьи	Значение уникального идентификатора	Битовая строка
01	S01	0 1
02	S02	1 1
03	S03	0 0
04	S04	0 0
05	S05	1 0

 

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

формирование битовой шкалы по второй схеме является в некотором роде транспонированием битовой шкалы, составленной по первой схеме.

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

 

 

Рис.31. Схема механизма инвертирования

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

Данный обзор показывает, что современные СУБД предоставляют достаточно широкий набор различных методов доступа, которые чаще всего являются теми или иными видами индексирования — способа отображения ключа индексирования в адрес хранимой записи (включая и хэширование). Наиболее часто используемыми  являются индексные структуры на основе B-дерева (B–tree); на основе хэш-функции или хеширование (hashing); на базе битовых шкал или индексов (bitmap). Индекс может служить различным целям: для ускорения доступа к записям одной таблицы и для ускорения операций соединения, тогда он называется индексом соединения. Если в качестве ключа индексирования используется некоторая функция атрибутов таблицы, такой индекс называют «основанным на функции» (function-based).

9. В чем суть бесфайловой организации внешней памяти. Опишите общую структуру страницы.

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

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

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

Замечание 2. Следует отметить, что некоторые механизмы, описываемые ниже, используются и при файловом управлении.

Структура и типы страниц

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

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

⇐ Предыдущая123456Следующая ⇒

Поделиться: