Схемы хеширования

Традиционно принято выделять две схемы хеширования:

• хеширование с цепочками (со списками);

• хеширование с открытой адресацией.

В первом случае выбирается некая хеш-функция f(k) = i, где i трактуется как индекс в таблице списков t. Поскольку нельзя гарантировать, что не встретится двух разных ключей, которым соответствует один и тот же индекс i (коллизия), такие «однородные» ключи просто помещаются в список, начинающийся в i-ячейке хеш-таблицы t (см. рисунок). Очевидно, что процесс заполнения хеш-таблицы будет достаточно простым, но при этом доступ к элементам потребует двух операций: вычисления индекса и поиска в соответствующем списке. Операции по занесению и поиску элементов при таком виде хеширования будут вестись в незамкнутом (открытом) пространстве памяти.

Отображение ключей путем хеширования с цепочками

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

Практически порядок работы в этом случае можно представить так – вначале создается таблица с пустыми строками, которая заполняется следующим об­разом:

• по первичному ключу новой строки вычисляется значение хеш-функции f(k) и результат трактуется, как номер строки в созданной таблице;

• если строка уже занята, производится проверка следующих строк по специальному алгоритму до тех пор, пока не будет обнаружено свободное место.

Аналогично производится поиск нужной строки:

• если после вычисления f(k) на месте в таблице, которое соот­ветствует вычисленному значению, оказывается пустая строка, значит, искомой строки просто нет;

• иначе (строка занята);

• если значение ключа совпало с искомым, поиск заканчива­ется;

• иначе (значение не совпало) – проверяются следующие стро­ки до строки с нужным ключом – строка найдена или до пус­той строки – строка отсутствует.

- Основные принципы технологии клиент-сервер.

Эффективность функционирования информационной системы с базой данных во многом зависит от ее архитектуры. На сегодня наиболее распространенной и перспективной является распределенная архитектура клиент-сервер. Она предполагает наличие компьютерной сети и распределенной базы данных. Развитие этой архитектуры началось с 80-х годов XX века с развитием локальных компьютерных сетей (Local Area Network – LAN) на базе персональных компьютеров.

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

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

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

Исторически первыми были распределенные ИС архитектуры «файл-сервер». В таких ИС по запросам с пользовательских автоматизированных рабочих мест (АРМ) файлы базы данных передавались на персональные компьютеры АРМ, где и производилась их обработка. Недостатки такого варианта архитектуры очевидны – высокая интенсивность передачи данных в сети (большая загрузка сети – высокий трафик). Кроме того, – передача в большинстве случаев избыточных данных, поскольку независимо от потребностей пользователя АРМ, файлы базы данных передаются целиком.

В архитектуре файл-сервер работали СУБД семейства xBase (dBaseIII, Clipper, FoxPro, Paradox). Кроме отмеченных эти системы имели следующие недостатки.

1. Не обеспечивали приемлемой производительности с большими объемами данных.

2. Недостаточно надежны – нет средств восстановления целостности базы, нет механизмов поддержки транзакций, средств журнализации и т.п.

3. Не обеспечивали нужный уровень секретности и разграничения доступа

Приведенные недостатки решаются при переводе приложений из архитектуры "файл-сервер" в архитектуру "клиент-сервер", которая ознаменовала собой следующий этап в развитии СУБД. Характерной особенностью архитектуры "клиент-сервер" является перенос вычислительной нагрузки на сервер БД (SQL-сервер) и максимальная разгрузка приложения клиента от вычислительной работы, а также существенное укрепление безопасности данных - как от злонамеренных, так и просто ошибочных изменений.

БД в этом случае помещается на сетевом сервере, как и в архитектуре "файл-сервер", однако прямого доступа к БД из приложений не происходит. Функции прямого обращения к БД осуществляет специальная управляющая программа – сервер БД (SQL-сервер), поставляемая разработчиком СУБД.

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

Технология клиент-сервер подразумевает 4 основных принципа (элемента):

1. Логическое разделение двух типов объектов (запрашивающих и выделяющих, информационно-вычислительные ресурсы);

2. Функциональное разделение и «обособление» процессов;

3. Организация связи (мониторинг, управление) между процессами;

4. Использование различных вычислительных платформ (многоплатформенность);

Преимущества архитектуры "клиент-сервер":

• большинство вычислительных процессов происходит на сервере; таким образом снижаются требования к вычислительным мощностям компьютера клиента;

• снижается сетевой трафик за счет посылки сервером клиенту только тех данных, которые он запрашивал; например, если необходимо сделать из таблицы объемом 10 000 записей выборку, результатом которой будут всего 2 записи, сервер выполнит запрос и перешлет клиенту набор данных из 2 записей;

• упрощается наращивание вычислительных мощностей в условиях развития программного обеспечения и возрастания объемов обрабатываемых данных: проще и чаще дешевле усилить мощности на сетевом сервере или полностью заменить сервер на более мощный, нежели наращивать мощности или полностью заменять 100-500 клиентских компьютеров;

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

• сервер реализует управление транзакциями и предотвращает попытки одновременного изменения одних и тех же данных; различные уровни изоляции транзакций позволяют определить поведение сервера при возникновении ситуаций одновременного изменения данных;

• безопасность системы возрастает за счет переноса большей части бизнес-правил на сервер; падает удельный вес противоречащих друг другу бизнес-правил в клиентских приложениях, выполняющих разные действия над БД; определить такие противоречивые бизнес-правила в приложениях клиента все еще можно, однако намного труднее их выполнить ввиду автоматического отслеживания сервером БД правильности данных.