Поиск в индексно-последовательном файле

Двоичный поиск.

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

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

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

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

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

5. Поиск в индексно - произвольном файле.

Произвольный (неупорядоченный) файл можно также индексировать, однако, в этом случае, необходимо делать ссылки на каждую запись БД. Такой индекс может использоваться в индексно-последовательном файле для поиска по вторичным ключам.

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

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

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

Дата добавления: 2014-01-11