Сколько индексов может содержать индексный файл

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

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

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

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

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

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

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

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

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

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

Вторичный индекс — это индекс, который определен на поле файла данных, отличном от поля, по которому выполняется упорядочение.

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

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

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

• первичная область хранения;
• отдельный индекс или несколько индексов;
• область переполнения.

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

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

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

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

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

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

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

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

Дерево — это структура данных, используемая во многих СУБД для хранения данных или индексов. Дерево состоит из иерархии узлов (node), в которой каждый узел, за исключением корня (root), имеет родительский (parent) узел, а также один, несколько или ни одного дочернего (child) узла. Корень не имеет родительского узла. Узел, который не имеет дочерних узлов, называется листом (leaf).

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

Сбалансированное дерево, В-дерево, В-Тгее — это дерево, у которого глубина дерева одинакова для всех листов.

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

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

Бинарное дерево, binary tree — это дерево порядка 2, в котором каждый узел имеет не больше двух дочерних узлов.

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

• Если корень не является лист-узлом, то он должен иметь, по крайней мере, два дочерних узла.
• В дереве порядка n каждый узел (за исключением корня и листов) должен иметь от n/2 до n указателей и дочерних узлов. Если число n/2 не является целым, то оно округляется до ближайшего большего целого.
• В дереве порядка n количество значений ключа в листе должно находиться в пределах от (n-1)/2 до (n-1). Если число (n-1)/2 не является целым, то оно округляется до ближайшего большего целого.
• Количество значений ключа в нелистовом узле на единицу меньше количества указателей.
• Дерево всегда должно быть сбалансированным, т.е. все пути от корня к каждому листу должны иметь одинаковую глубину.
• Листы дерева связаны в порядке возрастания значений ключа.

Знаете ли Вы, что в 1974 — 1980 годах профессор Стефан Маринов из г. Грац, Австрия, проделал серию экспериментов, в которых показал, что Земля движется по отношению к некоторой космической системе отсчета со скоростью 360±30 км/с, которая явно имеет какой-то абсолютный статус. Естественно, ему не давали нигде выступать и он вынужден был начать выпуск своего научного журнала «Deutsche Physik», где объяснял открытое им явление. Подробнее читайте в FAQ по эфирной физике.

Сколько индексов может содержать индексный файл

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

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

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

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

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

• Кроме того, индексный файл экземпляров можно создать или обновить при помощи команды Файл (File) > Управление сессией (Manage Session) > Обновить индекс (Update Index) .

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

• Чтобы упростить процесс загрузки экземпляров в сессию для добавления их в индексный файл экземпляров, можно использовать команду Инструменты (Tools) > Проверка (Verify) в меню Таблица семейства (Family Table) . При сохранении базовой модели после проверки имена всех успешно регенерированных экземпляров будут добавлены в индексный файл экземпляров для этой папки.

• Файл .idx — это текстовый файл, который можно редактировать за пределами Creo Parametric в любом текстовом редакторе. Тем не менее, если этот файл отредактирован за пределами Creo Parametric , то Creo Parametric не распознает его. Например, при выборе команды Файл (File) > Открыть (Open) для открытия модели, содержащей измененный файл .idx , имена экземпляров этого файла не появятся в диалоговом окне Открыть файл (File Open) .

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

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

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

В этой статье

• Что такое индекс?
• Выбор полей для индексирования
• Создание индекса
• Удаление индекса
• Просмотр и редактирование индексов
• Автоматическое создание индексов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. В области навигации щелкните правой кнопкой мыши имя таблицы, в которой необходимо создать индекс, и выберите в контекстном меню пункт Конструктор.
2. Щелкните пункт Имя поля для поля, которое следует индексировать.
3. В разделе Свойства поля откройте вкладку Общие.
4. В свойстве Индексированное выберите значение Да (допускаются совпадения), если следует разрешить повторяющиеся значения, или значение Да (совпадения не допускаются), чтобы создать уникальный индекс.
5. Чтобы сохранить изменения, щелкните элемент Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.

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

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

1. В области навигации щелкните правой кнопкой мыши имя таблицы, в которой необходимо создать индекс, и выберите в контекстном меню пункт Конструктор.
2. На вкладке Конструктор в группе Показать или скрыть щелкните пункт Индексы. Появится окно «Индексы». Измените размеры этого окна, чтобы отображались пустые строки и свойства индекса.
3. В первой пустой строке столбца Индекс введите имя индекса. Для индекса можно использовать либо имя одного из индексируемых полей, либо другое подходящее имя.
4. В столбце Имя поля щелкните стрелку, затем щелкните первое поле, которое следует использовать в индексе.
5. Следующую строку столбца Индекс оставьте пустой, затем в столбце Имя поля укажите второе индексируемое поле. Повторите этот шаг для всех полей, которые необходимо включить в индекс.
6. Чтобы изменить порядок сортировки значений полей, в столбце Порядок сортировки окна «Индексы» щелкните пункт По возрастанию или По убыванию. По умолчанию выполняется сортировка по возрастанию.
7. В разделе Свойства индекса окна Индексы укажите свойства индекса для строки в столбце Имя индекса, содержащем имя индекса. Задайте свойства в соответствии с таблицей ниже.
   

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

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

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

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

1. В области навигации щелкните правой кнопкой мыши имя таблицы, для которой необходимо удалить индекс, и выберите в контекстном меню пункт Конструктор.
2. На вкладке Конструктор в группе Показать или скрыть щелкните пункт Индексы. Появится окно «Индексы». Измените размеры этого окна, чтобы отображались пустые строки и свойства индекса.
3. В окне «Индексы» выделите строки, содержащие индекс, который следует удалить, и нажмите клавишу DELETE.
4. Чтобы сохранить изменения, нажмите кнопку Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.
5. Закройте окно Индексы

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

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

1. В области навигации щелкните правой кнопкой мыши имя таблицы, индекс которой вы хотите изменить, и выберите в контекстном меню пункт Конструктор.
2. На вкладке Конструктор в группе Показать или скрыть щелкните пункт Индексы. Появится окно «Индексы». Измените размеры этого окна, чтобы отображались пустые строки и свойства индекса.
3. Просмотрите или измените индексы и свойства индексов в соответствии со своими задачами.
4. Чтобы сохранить изменения, нажмите кнопку Сохранить на панели быстрого доступа или нажмите клавиши CTRL+S.
5. Закройте окно Индексы

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

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

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

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

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

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

Индексные файлы

Индексные файлы Несмотря на высокую эффективность хэш-адресации, в файловых структурах далеко не всегда удается найти соответствующую функцию, поэтому при организации доступа по первичному ключу широко используются индексные файлы. В некоторых коммерческих системах индексными файлами называются также и файлы, организованные в виде инвертированных списков, которые используются для доступа по вторичному ключу. Мы будем придерживаться классической интерпретации индексных файлов и надеемся, что если вы столкнетесь с иной интерпретацией, то сумеете разобраться в сути, несмотря на некоторую путаницу в терминологии. Наверное, это отчасти связано с тем, что область баз данных является достаточно молодой областью знаний, и несмотря на то, что здесь уже выработалась определенная терминология, многие поставщики коммерческих СУБД предпочитают свой упрощенный сленг при описании собственных продуктов. Иногда это связано с тем, что в целях рекламы они не хотят ссылаться на старые, хорошо известные модели и методы организации информации в системе, а изобретают новые названия при описании своих моделей, тем самым пытаясь разрекламировать эффективность своих продуктов. Хорошее знание принципов организации данных поможет вам объективно оценивать решения, предлагаемые поставщиками современных СУБД, и не попадаться на рекламные крючки. Индексные файлы можно представить как файлы, состоящие из двух частей. Это не обязательно физическое совмещение этих двух частей в одном файле, в большинстве случаев индексная область образует отдельный индексный файл, а основная область образует файл, для которого создается индекс. Но нам удобнее рассматривать эти две части совместно, так как именно взаимодействие этих частей и определяет использование механизма индексации для ускорения доступа к записям. Мы предполагаем, что сначала идет индексная область, которая занимает некоторое целое число блоков, а затем идет основная область, в которой последовательно расположены все записи файла. В зависимости от организации индексной и основной областей различают 2 типа файлов: с плотным индексом и с неплотным индексом. Эти файлы имеют еще дополнительные названия, которые напрямую связаны c методами доступа к произвольной записи, которые поддерживаются данными файловыми структурами. Файлы с плотным индексом называются также индексно-прямыми файлами, а файлы с неплотным индексом называются также индексно-последовательными файлами. Смысл этих названий нам будет ясен после того, как мы более подробно рассмотрим механизмы организации данных файлов. Файлы с плотным индексом, или индексно-прямые файлы Рассмотрим файлы с плотным индексом. В этих файлах основная область содержит последовательность записей одинаковой длины, расположенных в произвольном порядке, а структура индексной записи в них имеет следующий вид:

Рекомендуемые материалы

1.2 (8 вариант)
Информатика
ИДДО итоговый тест 86% (50 вопросов)
Информатика
1.3.2 (вариант 8)
Информатика
Аттестационный тест по курсу «Информатика» 88,33%
Информатика
Лабораторная работа №8
Программирование
299 90 руб.
8 лекций в ворде
Информатика

Здесь значение ключа — это значение первичного ключа, а номер записи — это порядковый номер записи в основной области, которая имеет данное значение первичного ключа. Так как индексные файлы строятся для первичных ключей, однозначно определяющих запись, то в них не может быть двух записей, имеющих одинаковые значения первичного ключа. В индексных файлах с плотным индексом для каждой записи в основной области существует одна запись из индексной области. Все записи в индексной области упорядочены по значению ключа, поэтому можно применить более эффективные способы поиска в упорядоченном пространстве. Длина доступа к произвольной записи оценивается не в абсолютных значениях, а в количестве обращений к устройству внешней памяти, которым обычно является диск. Именно обращение к диску является наиболее длительной операцией по сравнению со всеми обработками в оперативной памяти. Наиболее эффективным алгоритмом поиска на упорядоченном массиве является логарифмический, или бинарный, поиск. Очень хорошо изложил этот алгоритм барон Мюнхгаузен, когда он объяснял, как поймать льва в пустыне. При этом все пространство поиска разбивается пополам, и так как оно строго упорядочено, то определяется сначала, не является ли элемент искомым, а если нет, то в какой половине его надо искать. Следующим шагом мы определенную половину также делим пополам и производим аналогичные сравнения, и т. д., пока не обнаружим искомый элемент. Максимальное количество шагов поиска определяется двоичным логарифмом от общего числа элементов в искомом пространстве поиска: T_n = log₂N, где N — число элементов. Однако в нашем случае является существенным только число обращений к диску при поиске записи по заданному значению первичного ключа. Поиск происходит в индексной области, где применяется двоичный алгоритм поиска индексной записи, а потом путем прямой адресации мы обращаемся к основной области уже по конкретному номеру записи. Для того чтобы оценить максимальное время доступа, нам надо определить количество обращений к диску для поиска произвольной записи. На диске записи файлов хранятся в блоках. Размер блока определяется физическими особенностями дискового контроллера и операционной системой. В одном блоке могут размещаться несколько записей. Поэтому нам надо определить количество индексных блоков, которое потребуется для размещения всех требуемых индексных записей, а потому максимальное число обращений к диску будет равно двоичному логарифму от заданного числа блоков плюс единица. Зачем нужна единица? После поиска номера записи в индексной области мы должны еще обратиться к основной области файла. Поэтому формула для вычисления максимального времени доступа в количестве обращений к диску выглядит следующим образом: T_n = log₂N_{бл. инд.} + 1. Давайте рассмотрим конкретный пример и сравним время доступа при последовательном просмотре и при организации плотного индекса. Допустим, что мы имеем следующие исходные данные: Длина записи файла (LZ) — 128 байт. Длина первичного ключа (LK) — 12 байт. Количество записей в файле (KZ) — 100000. Размер блока (LB) — 1024 байт. Рассчитаем размер индексной записи. Для представления целого числа в пределах 100000 нам потребуется 3 байта, можем считать, что у нас допустима только четная адресация, поэтому нам надо отвести 4 байта для хранения номера записи, тогда длина индексной записи будет равна сумме размера ключа и ссылки на номер записи, то есть: LI = LK + 4 = I4 + 4 = 16 байт. Определим количество индексных блоков, которое требуется для обеспечения ссылок на заданное количество записей. Для этого сначала определим, сколько индексных записей может храниться в одном блоке: KIZB = LB/LI = 1024/16 = 64 индексных записи в одном блоке. Теперь определим необходимое количество индексных блоков: KIB = KZ/KZIB = 100000/64 = 1563 блока. Мы округлили в большую сторону, потому что пространство выделяется целыми блоками, и последний блок у нас будет заполнен не полностью. А теперь мы уже можем вычислить максимальное количество обращений к диску при поиске произвольной записи: T_поиска = log₂KIB + 1 = log₂1563 + 1 = 11 + 1 = 12 обращений к диску. Логарифм мы тоже округляем, так как считаем количество обращений, а оно должно быть целым числом. Следовательно, для поиска произвольной записи по первичному ключу при организации плотного индекса потребуется не более 12 обращений к диску. А теперь оценим, какой выигрыш мы получаем, ведь организация индекса связана с дополнительными накладными расходами на его поддержку, поэтому такая организация может быть оправдана только в том случае, когда она действительно дает значительный выигрыш. Если бы мы не создавали индексное пространство, то при произвольном хранении записей в основной области нам бы в худшем случае было необходимо просмотреть все блоки, в которых хранится файл, временем просмотра записей внутри блока мы пренебрегаем, так как этот процесс происходит в оперативной памяти. Количество блоков, которое необходимо для хранения всех 100 000 записей, мы определим по следующей формуле: KBO = KZ/(LB/LZ) = 100000/(1024/128) = 12500 блоков. И это означает, что максимальное время доступа равно 12500 обращений к диску. Да, действительно, выигрыш существенный. Рассмотрим, как осуществляются операции добавления и удаления новых записей. При операции добавления осуществляется запись в конец основной области. В индексной области необходимо произвести занесение информации в конкретное место, чтобы не нарушать упорядоченности. Поэтому вся индексная область файла разбивается на блоки и при начальном заполнении в каждом блоке остается свободная область (процент расширения) (рис. 9.7):
Рис. 9.7. Пример организации файла с плотным индексом После определения блока, в который должен быть занесен индекс, этот блок копируется в оперативную память, там он модифицируется путем вставки в нужное место новой записи (благо в оперативной памяти это делается на несколько порядков быстрее, чем на диске) и, измененный, записывается обратно на диск. Определим максимальное количество обращений к диску, которое требуется при добавлении записи, — это количество обращений, необходимое для поиска записи плюс одно обращение для занесения измененного индексного блока и плюс одно обращение для занесения записи в основную область. T _{добавления} = log₂N + 1 + 1 + 1 . Естественно, в процессе добавления новых записей процент расширения постоянно уменьшается. Когда исчезает свободная область, возникает переполнение индексной области. В этом случае возможны два решения: либо перестроить заново индексную область, либо организовать область переполнения для индексной области, в которой будут храниться не поместившиеся в основную область записи. Однако первый способ потребует дополнительного времени на перестройку индексной области, а второй увеличит время на доступ к произвольной записи и потребует организации дополнительных ссылок в блоках на область переполнения. Именно поэтому при проектировании физической базы данных так важно заранее как можно точнее определить объемы хранимой информации, спрогнозировать ее рост и предусмотреть соответствующее расширение области хранения. При удалении записи возникает следующая последовательность действий: запись в основной области помечается как удаленная (отсутствующая), в индексной области соответствующий индекс уничтожается физически, то есть записи, следующие за удаленной записью, перемещаются на ее место и блок, в котором хранился данный индекс, заново записывается на диск. При этом количество обращений к диску для этой операции такое же, как и при добавлении новой записи. Файлы с неплотным индексом, или индексно-последовательные файлы Попробуем усовершенствовать способ хранения файла: будем хранить его в упорядоченном виде и применим алгоритм двоичного поиска для доступа к произвольной записи. Тогда время доступа к произвольной записи будет существенно меньше. Для нашего примера это будет: T = log₂KBO = log₂12500 = 14 обращений к диску. И это существенно меньше, чем 12 500 обращений при произвольном хранении записей файла. Однако и поддержание основного файла в упорядоченном виде также операция сложная. Неплотный индекс строится именно для упорядоченных файлов. Для этих файлов используется принцип внутреннего упорядочения для уменьшения количества хранимых индексов. Структура записи индекса для таких файлов имеет следующий вид:

Значение ключа первой записи блока

Номер блока с этой записью

В индексной области мы теперь ищем нужный блок по заданному значению первичного ключа. Так как все записи упорядочены, то значение первой записи блока позволяет нам быстро определить, в каком блоке находится искомая запись. Все остальные действия происходят в основной области. На рис. 9.8 представлен пример заполнения основной и индексной областей, если первичным ключом являются целые числа.
Рис. 9.8. Пример заполнения индексной и основной области при организации неплотного индекса Время сортировки больших файлов весьма значительно, но поскольку файлы поддерживаются сортированными с момента их создания, накладные расходы в процессе добавления новой информации будут гораздо меньше. Оценим время доступа к произвольной записи для файлов с неплотным индексом. Алгоритм решения задачи аналогичен. Сначала определим размер индексной записи. Если ранее ссылка рассчитывалась исходя из того, что требовалось ссылаться на 100 000 записей, то теперь нам требуется ссылаться всего на 12 500 блоков, поэтому для ссылки достаточно двух байт. Тогда длина индексной записи будет равна: LI = LK + 2 = 14 + 2 = 14 байт. Тогда количество индексных записей в одном блоке будет равно: KIZB = LB/LI = 1024/14 = 73 индексные записи в одном блоке. Определим количество индексных блоков, которое необходимо для хранения требуемых индексных записей: KIB = KBO/KZIB = 12500/73 = 172 блока. Тогда время доступа по прежней формуле будет определяться: T_поиска = log₂KIB + 1 = log₂172 + 1 = 8 + 1 = 9 обращений к диску. Мы видим, что при переходе к неплотному индексу время доступа уменьшилось практически в полтора раза. Поэтому можно признать, что организация неплотного индекса дает выигрыш в скорости доступа. Рассмотрим процедуры добавления и удаления новой записи при подобном индексе. Здесь механизм включения новой записи принципиально отличен от ранее рассмотренного. Здесь новая запись должна заноситься сразу в требуемый блок на требуемое место, которое определяется заданным принципом упорядоченности на множестве значений первичного ключа. Поэтому сначала ищется требуемый блок основной памяти, в который надо поместить новую запись, а потом этот блок считывается, затем в оперативной памяти корректируется содержимое блока и он снова записывается на диск на старое место. Здесь, так же как и в первом случае, должен быть задан процент первоначального заполнения блоков, но только применительно к основной области. В MS SQL server этот процент называется Full-factor и используется при формировании кластеризованных индексов. Кластеризованными называются как раз индексы, в которых исходные записи физически упорядочены по значениям первичного ключа. При внесении новой записи индексная область не корректируется. Количество обращений к диску при добавлении новой записи равно количеству обращений, необходимых для поиска соответствующего блока плюс одно обращение, которое требуется для занесения измененного блока на старое место. T_{добавления} = log₂N +1 + 1 обращений. Уничтожение записи происходит путем ее физического удаления из основной области, при этом индексная область обычно не корректируется, даже если удаляется первая запись блока. Поэтому количество обращений к диску при удалении записи такое же, как и при добавлении новой записи. Организация индексов в виде B-tree (В-деревьев) Калькированный термин «B-дерево», в котором смешивается английский символ «B» и добавочное слово на русском языке, настолько устоялся в литературе, посвященной организации физического хранения данных, что я не решусь его корректировать. Встретив как-то термин «Б-дерево», я долго его трактовала, потому что привыкла уже к устоявшемуся обозначению. Поэтому будем работать с этим термином. Построение В-деревьев связано с простой идеей построения индекса над уже построенным индексом. Действительно, если мы построим неплотный индекс, то сама индексная область может быть рассмотрена нами как основной файл, над которым надо снова построить неплотный индекс, а потом снова над новым индексом строим следующий и так до того момента, пока не останется всего один индексный блок. Мы в общем случае получим некоторое дерево, каждый родительский блок которого связан с одинаковым количеством подчиненных блоков, число которых равно числу индексных записей, размещаемых в одном блоке. Количество обращений к диску при этом для поиска любой записи одинаково и равно количеству уровней в построенном дереве. Такие деревья называются сбалансированными (balanсed) именно потому, что путь от корня до любого листа в этом древе одинаков. Именно термин «сбалансированное» от английского «balanced» — «сбалансированный, взвешенный» и дал название данному методу организации индекса. Построим подобное дерево для нашего примера и рассчитаем для него количество уровней и, соответственно, количество обращений к диску. На первом уровне число блоков равно числу блоков основной области, это нам известно, — оно равно 12 500 блоков. Второй уровень образуется из неплотного индекса, мы его тоже уже строили и вычислили, что количество блоков индексной области в этом случае равно 172 блокам. А теперь над этим вторым уровнем снова построим неплотный индекс. Мы не будем менять длину индексной записи, а будем считать ее прежней, равной 14 байтам. Количество индексных записей в одном блоке нам тоже известно, и оно равно 73. Поэтому сразу определим, сколько блоков нам необходимо для хранения ссылок на 172 блока. KIB₃ = KIB₂/KZIB = 172/73 = 3 блока Мы снова округляем в большую сторону, потому что последний, третий, блок будет заполнен не полностью. И над третьим уровнем строим новый, и на нем будет всего один блок, в котором будет всего три записи. Поэтому число уровней в построенном дереве равно четырем, и соответственно количество обращений к диску для доступа к произвольной записи равно четырем (рис. 9.9). Это не максимально возможное число обращений, а всегда одно и то же, одинаковое для доступа к любой записи. T_д = R_уровн. =4
Рис. 9.9. Построенное В-дерево Механизм добавления и удаления записи при организации индекса в виде В-дерева аналогичен механизму, применяемому в случае с неплотным индексом. И наконец, последнее, что хотелось бы прояснить, — это наличие вторых названий для плотного и неплотного индексов. В случае плотного индекса после определения местонахождения искомой записи доступ к ней осуществляется прямым способом по номеру записи, поэтому этот способ организации индекса и называется индексно-прямым. В случае неплотного индекса после нахождения блока, в котором расположена искомая запись, поиск внутри блока требуемой записи происходит последовательным просмотром и сравнением всех записей блока. Поэтому способ индексации с неплотным индексом называется еще и индексно-последовательным. Моделирование отношений «один-ко-многим» на файловых структурах Отношение иерархии является типичным для баз данных, поэтому моделирование иерархических связей является типичным для физических моделей баз данных. Для моделирования отношений 1:М (один-ко-многим) и М:М (многие-ко-мно-гим) на файловых структурах используется принцип организации цепочек записей внутри файла и ссылки на номера записей для нескольких взаимосвязанных файлов. Моделирование отношения 1:М с использованием однонаправленных указателей В этом случае связываются два файла, например F1 и F2, причем предполагается, что одна запись в файле F1 может быть связана с несколькими записями в файле F2. Условно это можно представить в виде, изображенном на рис. 9.10.
Рис. 9.10. Иерархическая связь между файлами При этом файл F1 в этом комплексе условно называется «Основным», а файл F2 — «зависимым» или «подчиненным». Структура основного файла может быть условно представлена в виде трех областей. «Основной файл» F1.

Ключ

Запись

Ссылка-указатель на первую запись в «Подчиненном» файле, с которой начинается цепочка записей файла F2, связанных с данной записью файла F1

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

Указатель на следующую запись в цепочке

Содержимое записи

В качестве примера рассмотрим связь между преподавателями и занятиями, которые эти преподаватели проводят. В файле F1приведен список преподавателей, а в файле F2— список занятий, которые они ведут.

F1
Номер записи	Ключ и остальная запись	Указатель
1	Иванов И. Н. …	1
2	Петров А. А.	3
3	Сидоров П. А.	2
4	Яковлев В. В.
F2
Номер записи	Указатель на следующую запись в цепочке	Содержимое записи
1	4	4306 Вычислительные сети
2	—	4307 Контроль и диагностика
3	6	4308 Вычислительные сети
4	5	84305 Моделирование
5	—	4309 Вычислительные сети
6	—	84405 Техническая диагностика
7	—

• Шаг 1. Ищется запись в «основном» файле в соответствии с его организацией (с помощью функции хэширования, или с использованием индексов, или другим образом). Если требуемая запись найдена, то переходим к шагу 2, в противном случае выводим сообщение об отсутствии записи основного файла.
• Шаг 2. Анализируем указатель в основном файле если он пустой, то есть стоит прочерк, значит, для этой записи нет ни одной связанной с ней записи в «подчиненном файле», и выводим соответствующее сообщение, в противном случае переходим к шагу 3.
• Шаг 3. По ссылке-указателю в найденной записи основного файла переходим прямым методом доступа по номеру записи на первую запись в цепочке «Подчиненного» файла. Переходим к шагу 4.
• Шаг 4. Анализируем текущую запись на содержание если это искомая запись, то мы заканчиваем поиск, в противном случае переходим к шагу 5.
• Шаг 5. Анализируем указатель на следующую запись в цепочке если он пуст, то выводим сообщение, что искомая запись отсутствует, и прекращаем поиск, в противном случае по ссылке-указателю переходим на следующую запись в «подчиненном файле» и снова переходим к шагу 4.

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

Алгоритм удаления записи из цепочки «подчиненного» файла

• Шаг 1. Ищется удаляемая запись в соответствии с ранее рассмотренным алгоритмом. Единственным отличием при этом является обязательное сохранение в специальной переменной номера предыдущей записи в цепочке, допустим, это переменная NP.
• Шаг 2. Запоминаем в специальной переменной указатель на следующую запись в найденной записи, например, заносим его в переменную NS. Переходим к шагу 3.
• Шаг 3. Помечаем специальным символом, например символом звездочка (*), найденную запись, то есть в позиции указателя на следующую запись в цепочке ставим символ «*» — это означает, что данная запись отсутствует, а место в файле свободно и может быть занято любой другой записью.
• Шаг 4. Переходим к записи с номером, который хранится в NP, и заменяем в ней указатель на содержимое переменной NS.

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

1. Добавление записи на первое место в цепочке.

2. Добавление записи в конец цепочки.

3. Добавление записи на заданное место в цепочке.

Задание для самостоятельной работы

Разработать алгоритмы добавления записи для всех трех случаев

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

В «основном файле» один указатель равен номеру первой записи в цепочке записей «подчиненного файла», а второй — номеру последней записи.

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

Для нашего примера это выглядит следующим образом:

Номер записи

Ключ и остальная запись

Указатель на первую запись

Указатель на последнюю запись