Структуры данных и алгоритмы (1021739), страница 87
Текст из файла (страница 87)
Если среднее количество записей в сегменте намного превосходит количество записей, которые могут уместиться водном блоке, можно периодически реорганизовывать таблицу сегментов, удваиваяколичество сегментов и деля каждый сегмент на две части. Этот прием описан вконце раздела 4.8.Индексированные файлыЕще одним распространенным способом организации файла записей являетсяподдержание файла в отсортированном (по значениям ключей) порядке. В этом случае файл можно было бы просматривать как обычный словарь или телефонный справочник, когда мы просматриваем лишь заглавные слова или фамилии на каждойстранице. Чтобы облегчить процедуру поиска, можно создать второй файл,называемый разреженным индексом, который состоит из пар (ж, Ъ), где х — значениеключа, а Ь — физический адрес блока, в котором значение ключа первой записиравняется х.
Этот разреженный индекс отсортирован по значениям ключей.Пример 11.4. На рис. 11.6 показан файл, а также соответствующий ему файл разреженного индекса. Предполагается, что три записи основного файла (или три парыиндексного файла) умещаются в один блок. Записи основного файла представленытолько значениями ключей, которые в данном случае являются целочисленными величинами. DИндексный файл3 5 84246Рис.
11.6. Основной файл и его разреженный индексЧтобы отыскать запись с заданным ключом х, надо сначала просмотреть индексный файл, отыскивая в нем пару (х, Ь). В действительности отыскивается наибольшее г, такое, что z < х и далее находится пара (г, Ь). В этом случае ключ х оказывается в блоке Ъ (если такой ключ вообще присутствует в основном файле).Разработано несколько стратегий просмотра индексного файла. Простейшей изних является линейный поиск.
Индексный файл читается с самого начала, пока невстретится пара (х, Ь) или (у, Ь), причем у > х. В последнем случае у предыдущей пары (z, Ъ') должно быть г < х, и если запись с ключом х действительно существует,она находится в блоке Ь'.11.3. ХРАНЕНИЕ ДАННЫХ В ФАЙЛАХ327Линейный поиск годится лишь для небольших индексных файлов. Более эффективным методом является двоичный поиск. Допустим, что индексный файл хранитсяв блоках bi, Ь2, ... ,Ь„. Чтобы отыскать значение ключа х, берется средний блок fyn/2]и х сравнивается со значением ключа у в первой паре данного блока. Если х < у, поиск повторяется в блоках bi, Ь2, ...
,6[n/2)-i- Если х > у, но х меньше, чем ключ блокаfyn/2]+i» используется линейный поиск, чтобы проверить, совпадает ли х с первымкомпонентом индексной пары в блоке ЬЫ2\. В противном случае повторяется поиск вблоках b[n/2]+i, 6[n/2j+2» — <Ь„. При использовании двоичного поиска нужно проверитьлищь [Iog2(n + 1)] блоков индексного файла.Чтобы создать индексированный файл, записи сортируются по значениям ихключей, а затем распределяются по блокам в возрастающем порядке ключей.
В каждый блок можно упаковать столько записей, сколько туда умещается. Однако в каждом блоке можно оставлять место для дополнительных записей, которые могутвставляться туда впоследствии. Преимущество такого подхода заключается в том,что вероятность переполнения блока, куда вставляются новые записи, в этом случаеоказывается ниже (иначе надо будет обращаться к смежным блокам). После распределения записей по блокам создается индексный файл: просматривается по очередикаждый блок и находится первый ключ в каждом блоке. Подобно тому, как это сделано в основном файле, в блоках, содержащих индексный файл, можно оставить какое-то место для последующего "роста".Допустим, есть отсортированный файл записей, хранящихся в блокахBI, B2, ...
,Вт. Чтобы вставить в этот отсортированный файл новую запись, используем индексный файл, с помощью которого определим, какой блок В, должен содержать новую запись. Если новая запись умещается в блок Bj( она туда помещается вправильной последовательности. Если новая запись становится первой записью вблоке BI, тогда выполняется корректировка индексного файла.Если новая запись не умещается в блок В,-, можно применить одну из несколькихстратегий.
Простейшая из них заключается в том, чтобы перейти на блок Bi+1 (которыйможно найти с помощью индексного файла) и узнать, можно ли последнюю запись Btпереместить в начало В(+1. Если можно, последняя запись перемещается в Bj+1, а новуюзапись можно затем вставить на подходящее место в В,.
В этом случае, конечно, нужноскорректировать вход индексного файла для В(+1 (и, возможно, для В,-).Если блок В(+1 также заполнен или если В, является последним блоком (i = m), изфайловой системы нужно получить новый блок. Новая запись вставляется в этот новый блок, который должен размещаться вслед за блоком Bt. Затем используется процедура вставки в индексном файле записи для нового блока,Несортированные файлы с плотным индексомЕще одним способом организации файла записей является сохранение произвольного порядка записей в файле и создание другого файла, с помощью которогобудут отыскиваться требуемые записи; этот файл называется плотным индексом.Плотный индекс состоит из пар (х, р), где р — указатель на запись с ключом х восновном файле.
Эти пары отсортированы по значениям ключа. В результатеструктуру, подобную упоминавшемуся выше разреженному индексу (или В-дереву,речь о котором пойдет в следующем разделе), можно использовать для поискаключей в плотном индексе.При использовании такой организации плотный индекс служит для поиска в основном файле записи с заданным ключом. Если требуется вставить новую запись,отыскивается последний блок основного файла и туда вставляется новая запись.
Если последний блок полностью заполнен, то надо получить новый блок из файловойсистемы. Одновременно вставляется указатель на соответствующую запись в файлеплотного индекса. Чтобы удалить запись, в ней просто устанавливается бит удаленияи удаляется соответствующий вход в плотном индексе (возможно, устанавливая издесь бит удаления).328ГЛАВА 11. СТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ ДЛЯ ВНЕШНЕЙ ПАМЯТИВторичные индексыВ то время как хешированные и индексированные структуры ускоряют выполнение операций с файлами, основываясь главным образом на ключах, ни один из этихметодов не помогает, когда операция связана с поиском записей, если заданы значения полей, не являющихся ключевыми. Если требуется найти записи с указаннымизначениями в некоторой совокупности полей Flt F2, ... ,Fj,, нам понадобится вторичный индекс для этих полей. Вторичный индекс — это файл, состоящий из пар (и, р),где v представляет собой список значений, по одному для каждого из полей.FI, F2, ...
,Fk, ар — указатель на запись. В файле вторичного индекса может бытьнесколько пар с заданным и, и каждый сопутствующий указатель должен указывать на запись в основном файле, которая содержит v в качестве списка значенийполей FI, F2, ... ,Ft.Чтобы отыскать записи, когда заданы значения полей FI, F2, ... ,Ft, мы отыскиваем в файле вторичного индекса запись (или записи) с заданным списком значений.Сам файл вторичного индекса может быть организован любым из перечисленныхвыше способов организации файлов по значениям ключей.
Таким образом, мы предполагаем, что v является ключом для пары (v, р).Например, организация файлов с помощью хеширования практически не зависит от того, уникальны ли ключи, — хотя, если бы оказалось очень много записейс одним и тем же значением "ключа", записи могли бы распределиться по сегментам очень неравномерно, и в результате хеширование не ускорило бы доступ к записям. Рассмотрим крайний случай, когда заданы только два значения для полейвторичного индекса. При этом все сегменты, за исключением двух, были бы пустыми, и таблица хеширования, независимо от имеющегося количества сегментов,ускоряла бы выполнение операций лишь в два раза (и то в луч'шем случае).
Аналогично, разреженный индекс не требует, чтобы ключи были уникальны, но еслиони действительно не будут уникальными, тогда в основном файле может оказаться два или больше блоков, содержащих одинаковые наименьшие значения"ключа", и когда нам потребуется найти записи с этим значением, необходимо будет просмотреть все такие блоки.Если файл вторичного индекса организован по методу хеширования или разреженного индекса, может возникнуть желание сэкономить память, объединив все записи с одинаковыми значениями, т.е. пары (v, pi), (v, p2)(и, рт) можно заменитьна и, за которым следует список pi, p2, ...
, р»,.Может возникнуть вопрос, нельзя ли оптимизировать время выполнения операторов, создав вторичный индекс для каждого поля или даже для всех подмножеств полей. К сожалению, придется "платить" за каждый вторичный индекс, который мыхотим создать. Во-первых, для хранения вторичного индекса тоже требуется место надиске, а этот ресурс (объем внешней памяти) тоже, хоть и не всегда, может быть дефицитным. Во-вторых, каждый создаваемый вторичный индекс замедляет выполнение всех операций вставки и удаления. Дело в том, что когда вставляется запись,надо также вставить точку входа для этой записи в каждый вторичный индекс, чтобы эти вторичные индексы по-прежнему правильно представляли соответствующийфайл.
Обновление вторичного индекса означает, что потребуется выполнить не менеедвух обращений к блокам, поскольку мы должны и прочитать, и записать блок. Однако таких обращений к блокам может оказаться значительно больше, посколькуеще нужно найти требуемый блок, а любой способ организации файла, который используется для вторичного индекса, потребует в среднем еще нескольких обращений,чтобы найти нужный блок. Все сказанное относится и к операции удаления записей.Отсюда следует вывод, что решение использовать вторичные индексы требует взвешенного подхода, поскольку надо определить, какие совокупности полей будут указываться в операциях, выполняемых с файлами, настолько то время, которое мы собираемся сэкономить за счет применения вторичных индексов, превосходит затратына обновление этого индекса при выполнении каждой операции вставки и удаления.11.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
