Сравнение методов

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

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

Разреженный индекс для файла, состоящего из n записей, позволяет выполнять операции с файлами, ограничиваясь использованием примерно обращений к блокам в случае двоичного поиска, где b – количество записей, помещающихся в один блок, а b` – количество пар ключ-указатель, помещающихся в один блок для индексного файла. В-деревья позволяют выполнять операции с файлами с использованием примерно обращений к блокам, где m – максимальное количество сыновей у внутренних узлов, что приблизительно равняется b`. Как разреженные указатели, так и В-деревья допускают обращение к записям в отсортированной последовательности.

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

Дата добавления: 2015-07-16