Стратегия разрешения коллизий с областью переполнения
Область хранения разбивается на 2 части:
· основную область;
· область переполнения.
Для каждой новой записи вычисляется значение хэш-функции, которое определяет адрес ее расположения, и запись заносится в основную область в соответствии с полученным значением хэш-функции.
Если вновь заносимая запись имеет значение функции хэширования такое же, которое использовала другая запись, уже имеющаяся в БД, то новая запись заносится в область переполнения на первое свободное место, а в записи-синониме, которая находится в основной области, делается ссылка на адрес вновь размещенной записи в области переполнения. Если же уже существует ссылка в записи-синониме, которая расположена в основной области, то тогда новая запись получает дополнительную информацию в виде ссылки и уже в таком виде заносится в область переполнения.
Рассмотрим механизмы поиска произвольной записи и удаления записи для этой стратегии хэширования.
Вычисляется значение хэш-функции искомой записи и считывается первая запись в цепочке синонимов, которая расположена в основной области. Если искомая запись не соответствует первой в цепочке синонимов, то далее поиск происходит перемещением по цепочке синонимов, пока не будет обнаружена требуемая запись.
При удалении первой записи в цепочке синонимов на ее место в основной области заносится вторая (следующая) запись в цепочке синонимов, при этом все указатели (ссылки на синонимы) сохраняются.
Если же удаляемая запись находится в середине цепочки синонимов, то в записи, предшествующей удаляемой, в цепочке ставится указатель из удаляемой записи.
Организация стратегии свободного замещения
При этой стратегии файловое пространство не разделяется на области, но для каждой записи добавляется 2 указателя: указатель на предыдущую запись в цепочке синонимов и указатель на следующую запись в цепочке синонимов. Отсутствие соответствующей ссылки обозначается специальным символом, например нулем. Для каждой новой записи вычисляется значение хэш-функции, и если данный адрес свободен, то запись попадает на заданное место и становится первой в цепочке синонимов. Если адрес, соответствующий полученному значению хэш-функции, занят, то по наличию ссылок определяется, является ли запись, расположенная по указанному адресу, первой в цепочке синонимов. Если да, то новая запись располагается на первом свободном месте и для нее устанавливаются соответствующие ссылки: она становится второй в цепочке синонимов, на нее ссылается первая запись, а она ссылается на следующую, если таковая есть. Если запись, которая занимает требуемое место, не является первой записью в цепочке синонимов, то при появлении «законного владельца» она должна быть перемещена на новое место. Для этой записи ищется первое свободное место и корректируются соответствующие ссылки.
II. Индексирование. При этом способе сначала формируются, а затем для быстрого поиска используются индексные таблицы, с помощью которых выполняется поиск.
РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ И РАСПРЕДЕЛЕННАЯ ОБРАБОТКА ДАННЫХ
Распределённые базы данных (РБД) — совокупность логически взаимосвязанных баз данных, распределённых в компьютерной сети. Пример – поисковая БД Google. Основные цели создания распределенных БД – повышение производительности, надежность, экономия средств (один очень быстрый компьютер стоит дороже 10 медленных, суммарная производительность которых при распределенной работе = производительности быстрого компьютера).
Объединение БД-х связано с решением следующих задач:
1. Оптимизация (т.е. на какой компьютер какую часть БД разместить для достижения оптимальной производительности), распределение индексированных компонентов (т.е. на какой компьютер разместить какие служебные индексные таблицы)
2. Организация доступа к данным
3. Защита целостности данных
4. Организация обновления данных.
Распределенные системы обработки данных строятся на основе вычислительных сетей. В этих системах компоненты БД могут быть размещены на рабочих станциях, на сетевом сервере и на серверах БД.
При разработке новой сети решается задача размещения компонентов БД. Для работы в составе сети не вся информация доступна пользователю. Для регламентации работы доступа к данным используется несколько уровней:
1. Регистрация пользователей
2. Пароли
3. Предоставление доступа только к определенным каталогам и файлам.
4. Назначение пользователям опекунских прав (ограничение работы пользователей)
5. Установление маски наследования прав (т.е. наличие доступа к каталогу не дает полного доступа к его подкаталогам).
Различают 8 типов прав:
1. Тип S – Supervisory – супервизорный тип (есть все права)
2. Тип R – Read – чтение
3. Тип W – Write – запись (право открывать и модифицировать файлы)
4. Тип С – Create – создание
5. Тип Е – Erase – удаление
6. Тим M – Modify – изменение атрибутов файлов (но не их содержание)
7. F-File Scan – пользователи могут видеть каталоги и файлы внутри каталогов
8. Тип A – Access Control – управление доступом (право назначать и модифицировать опекунские права)
S – Supervisory Это право, присваиваемое пользователю на определенном каталоге, предоставляет возможность пользоваться всеми существующими правами и давать их другим пользователям или группам по отношению к данному каталогу или его подкаталогу. Само право Supervisory для доверенного лица автоматически распространяется на все подкаталоги того каталога, в котором оно было предоставлено.
R-Read
Это право дает возможность пользователю или группе открывать файлы для чтения и запускать исполняемые модули.
W-Write дает возможность пользователю или группе открывать файл и модифицировать его содержимое.
C-Create – если никаких других прав на уровне подкаталогов не предоставлено, доверенное лицо может только создавать каталоги или файлы внутри них
E-Erase
Это право указывает на возможность удаления каталога, подкаталогов или файлов в каталоге или подкаталогах.
M-Modify
Предоставляет возможность пользователям или группам устанавливать и менять атрибуты файлов и каталогов, в том числе и названия каталогов и файлов, входящих в состав этих каталогов. Modify не дает возможность изменять содержимое файлов.
F-File Scan
Благодаря File Scan пользователи или группы могут видеть каталоги и файлы внутри каталогов.
A-Access Control
Access Control предоставляет пользователю или группе возможность модифицировать права доверенных лиц или состояние маски наследования прав по отношению к каталогу или файлу. Оно не дает пользователю возможности присваивать право Supervisory, но позволяет присваивать другим права, которых сами эти пользователи не имеют.
