рассматривается; ее эффективность в очень большой степени зависит от систем и приложений.

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

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

16.2 Индексированный последовательный доступ

прямой подход к построению индекса заключается в сохранении массива со ссылками на ключи и элементы, упорядоченного по ключам, с последующим использованием бинарного поиска (см. раздел 12.4) для реализации операции search. При наличии N элементов для реализации этого метода потребовалось бы IgN зондирований, даже в случае очень большого файла. Наша базовая модель немедленно принуждает к рассмофению двух разновидностей этого простого метода. Во-первых, сам по себе индекс очень велик и в общем случае не помещается на одной странице. Поскольку доступ к страницам можно получить только через ссылки на страницы, вместо этого можно построить явное полностью сбалансированное бинарное дерево с ключами и указателями на страницы во внутренних узлах и с ключами и указателями на элементы во внешних. Во-вторых, затраты на доступ к М записям таблицы равны затратам на доступ к 2, поэтому можно воспользоваться Л/-арным деревом при таких же затратах на каждый узел, что и в случае применения бинарного дерева. Такое усовершенствование уменьшает количество зондирований до значения, приблизительно пропорционального log/A. Как было показано в главах 10-15, на практике это значение можно считать константным. Например, если М равно 1000, то IomN меньше 5 для N меньше 1 филлиона.

На рис. 16.1 приведен пример набора ключей, а на рис. 16.2 - пример такой структуры дерева для этих ключей. Чтобы примеры были достаточно понятными, пришлось использовать сравнительно небольшие значения М и N, тем не менее, они иллюстрируют, что деревья для большого значения М будут плоскими.

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

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

Поскольку метод индексации, показанный на рис. 16.2, объединяет последовательную организацию ключей с индексным доступом, по историческим причинам такой метод называется индексным последовательным доступом. Этот метод удобен для приложений, в которых изменения в базе данных выполняются редко. Иногда сам индекс называют каталогом. Недостаток использования индексного последовательного доступа заключается в том, что изменение каталога представляет собой операцию, сопряженную с большими затратами. Например, для добавления единственного ключа может потребоваться перестройка буквально всей базы данных с присвоением новых позиций многим ключам и новых значений индексам. Для преодоления упомянуто-

РИСУН0К16.1 ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ ВОСЬМЕРИЧНЫХ КЛЮЧЕЙ

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

ooi;

107 147

153 176 207

737Т

::*:X-Cf

524 526

737 741 742 766, 773

Г0 недостатка и обеспечения возможности увеличения базы данных в будущем в ранних системах резервировались лишние страницы на дисках и лишнее пространство на страницах; но, в конечном счете, подобная технология оказывалась не очень эффективной в динамических ситуациях (см. упражнение 16.3). Методы, которые будут рассматриваться в разделах 16.3 и 16.4, обеспечивают систематичные и эффективные альтернативы таким специализированным схемам.

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

В данном случае (и в других разделах книги) термин постоянное используется несколько вольно для обозначения значения, которое пропорционально logAfN для большого значения М. Как уже отмечалось, это оправдано для размеров файлов, встречающихся на практике. На рис. 16.3 показаны дополнительные примеры. Даже при наличии 128-разрядного ключа поиска, пригодного для указания неимоверно большого количества различных элементов, равного 2, элемент с данным ключом можно было бы найти при помощи всего 13 зондирований, при 1 ООО-позиционном ветвлении.

Мы не будем рассматривать реализации, которые обеспечивают поиск и построение индексов подобного типа, поскольку они представляют собой специальные случаи более общих механизмов, рассмотренных в разделе 16.3 (см упражнение 16.17 и программу 16.2).

Упражнения

о 16.1 Составьте таблицу значений log/A для М = 10, 100 и 1000 и Л = 10 10 10 и 10

1> 16.2 Нарисуйте структуру индексного последовательного файла для ключей 516, 177, 143, 632, 572, 161, 774, 470, 411, 706, 461, 612, 761, 474, 774, 635, 343, 461, 351, 430, 664, 127, 345, 171 и 357 при М = 5 и = 6.

о 16.3 Предположим, что мы строим структуру индексированного последовательного файла для элементов, помещаемых на страницах емкостью М, но оставляем на каждой странице к свободных ячеек для возможности расширения. Приведите формулу для определения количества зондирований, необходимых для выполнения поиска, в виде функции от Л, Ми к. Используйте эту формулу для определения количества зондирований, необходимого для выполнения поиска при А: = Ж/10, М= 10, 100 и 1000 иМ= 10 10 10 и 10

РИСУНОК 16.2 СТРУКТУРА ИНДЕКСНОГО

ПОСЛЕДОВАТЕЛЬНОГО ФАЙЛА

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