Л. Партыка, И. И. Попов системы управления базами данных
Адресация с помощью ключей, преобразуемых в адрес
жүктеу/скачать 4,64 Mb.
|
Голицына О Л Партыка Т Л Попов И И Системы
| Адресация с помощью ключей, преобразуемых в адрес. Известно много методов преобразования ключа непосредственно в значение адреса в файле. В тех случаях, когда возможно преобразование значения ключа непосредственно в значение адреса в файле, такой способ адресации обеспечивает самый быстрый доступ; при этом нет необходимости организовывать поиск внутри файла или выполнять операции с индексами.
В некоторых приложениях адрес может быть вычислен на основе значений некоторых элементов данных записи. К недостаткам данного способа относится малое заполнение файла: в файле остаются свободные участки, поскольку ключи преобразуются не в непрерывное множество адресов. Другим недостатком схем прямой адресации является их малая гибкость. Машинные адреса записей могут измениться при обновлении файла. Для устранения этого недостатка прямую адресацию обычно выполняют в два этапа. Сначала ключ преобразуется в порядковый номер, который затем преобразуется в машинный адрес. Хэширование. Простым и полезным способом вычисления адреса является хэширование (перемешивание). В данном методе ключ преобразуется в квази случайное число, которое используется для определения местоположения записи. Более экономичным является указание на область, в которой размещается группа записей. Эта область называется участком записей (slot, bucket). При первоначальной загрузке файла адрес, по которому должна быть размещена запись, определяется следующим образом:
ключ записи преобразуется в квази случайное число, находящееся в диапазоне от 1 до числа участков, используемых для размещения записей; число преобразуется в адрес участка, и, если на участке есть свободное место, логическая запись размещается на нем; если участок заполнен, запись должна быть размещена на участке переполнения — следующий по порядку участок либо участок в отдельной области переполнения. При чтении записей из файла их поиск выполняется аналогично, причем может оказаться, что для поиска записи потребуется чтение нескольких участков переполнения. Из-за вероятностной природы алгоритма в этом способе не удается достичь 100%-ной плотности заполнения памяти, однако для большинства файлов может быть достигнута плотность 80 или 90 %; при этом память для индексов не требуется. Большинство записей можно найти за одно обращение, но для некоторых потребуется второе обращение (при переполнении). Для очень небольшой части записей потребуется третье или четвертое обращение к файлу. Кроме того, в этом случае менее эффективно используется память, чем в индексных методах; записи не упорядочены для последовательной обработки.
жүктеу/скачать 4,64 Mb. Достарыңызбен бөлісу:
|