Главная Промышленная автоматика.

чем, нельзя пользоваться, если мы имеем дело с закрепленными записями) является замена удаленной записи на последнюю запись в цепочке блоков сегмента h(x). Если такое изъятие последней записи приводит к опустошению последнего блока в сегменте h{x), этот пустой блок можно затем вернуть файловой системе для повторного использования.

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

Индексированныефайлы

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

Пример U.4. На рис. И.6 показан файл, а таюке соответствуюший ему файл разреженного индекса. Предполагается, что три записи основного файла (или три пары индексного файла) умешаются в один блок. Записи основного файла представлены только значениями ключей, которые в данном случае являются целочисленными величинами. D

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

(3j) (10,j}{23,)

(28,у)(42,)


28 31 38

42 46

Рис. 11.6. Основной файл и его разреженный индекс

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

Разработано несколько стратегий просмотра индексного файла. Простейшей из них является линейный поиск. Индексный файл читается с самого начала, пока не встретится пара (х, Ь) или (у, Ь), причем у > х. В последнем случае у предыдушей пары (z, б) должно быть г < X, и если запись с ключом х действительно сушествует, она находится в блоке Ь.



Линейный поиск годится лишь для небольших индексных файлов. Более эффективным методом является двоичный поиск. Допустим, что индексный файл хранится в блоках by, 62, ••• ,fcn- Чтобы отыскать значение ключа х, берется средний блок fy„/2] и X сравнивается со значением ключа у в первой паре данного блока. Если х < у, поиск повторяется в блоках by, 62, ••• .6(п/2)-1- Если х > у, ко х меньше, чем ключ блока fyn/2]-l-i» используется линейный поиск, чтобы проверить, совпадает ли х с первым компонентом индексной пары в блоке 6[п/2]- В противном случае повторяется поиск в блоках 6[n/2)+i»6[n/2]+2, - ,Ь„. При использовании двоичного поиска нужно проверить лишь [log2(n+ 1)] блоков индексного файла.

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

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

Если новая запись не умешается в блок В;, можно применить одну из нескольких стратегий. Простейшая из них заключается в том, чтобы перейти на блок B,+i (который мокно найти с помошью индексного файла) и узнать, можно ли последнюю запись В, переместить в начало B,+i. Если можно, последняя запись перемешается в Bi+y, а новую запись мокно затем вставить на подходящее место в В,. В этом случае, конечно, нужно скорректировать вход индексного файла для B,+i (и, возможно, для В().

Если блок В,+1 таюке заполнен или если В,- является последним блоком (i = т), из файловой системы нужно получить новый блок. Новая запись вставляется в этот новый блок, который должен размешаться вслед за блоком В/. Затем используется процедура вставки в индексном файле записи для нового блока,

Несортированные файлы с плотным индексом

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

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



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

в то время как хешированные и индексированные структуры ускоряют вьшолне-ние операций с файлами, основьшаясь главным образом на ключах, ни один из этих методов не помогает, когда операция связана с поиском записей, если заданы значения полей, не являюшихся ключевыми. Если требуется найти записи с указанными значениями в некоторой совокупности полей Fi,F2, ... Л, нам понадобится вторичный индекс для этих полей. Вторичный индекс - это файл, состояший из пар (и, р), где V представляет собой список значений, по одному для каждого из полей 1. <Fkr ар- указатель на запись. В файле вторичного индекса может быть несколько пар с заданным V, и каждый сопутствуюший указатель должен указывать на запись в основном файле, которая содержит v в качестве списка значений полей Fi,F2< ,Ft.

Чтобы отыскать записи, когда заданы значения полей Fi, F2, ... ,Fi,, мы отыскиваем в файле вторичного индекса запись (или записи) с заданным списком значений. Сам файл вторичного индекса может быть организован любым из перечисленных выше способов организации файлов по значениям ключей. Таким образом, мы предполагаем, что V является ключом для пары (v, р).

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

Если файл вторичного индекса организован по методу хеширования или разреженного индекса, может возникнуть желание сэкономить память, объединив все записи с одинаковыми значениями, т.е. пары (v, pi), (v, Рз) (yPm) можно заменить на V, за которым следует списокр!, Рг» - ,Рт-

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 [105] 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0019