В. И. Швецов Базы данных
 Скачать 8.45 Mb.
|
9.4.5. Размещение записей с использованием хэшированияКак в любом другом способе организации структур хранения, логические записи группируются в физические записи (блоки) по k штук. Однако в отличие от всех других способов организации структур хранения здесь выбран особенный способ группировки. Определенным образом выбирается так называемая хэш-функция f. Аргументом этой функции является значение x первичного ключа логической записи. Тогда f(x) указывает адрес расположения блока, в котором должна находиться логическая запись со значением ключа x. Функция f должна, по возможности, равномерно распределять значения x по физическим блокам. Обсуждению возможных хэш-функций посвящено достаточно много литературы, поэтому здесь мы не будем касаться этого вопроса. Можно лишь добавить, что иногда, исходя из специфики множества значений x первичного ключа, можно построить функцию f, удовлетворяющую всем необходимым условиям. Таким образом, логическая запись таблицы со значением x первичного ключа размещается в блоке внешней памяти по адресу f(x). В этом блоке может находиться не более k записей. Может оказаться, что выбранная функция отображает в один адрес памяти (один блок) более k записей. Возникает так называемая коллизия. Возможным способом разрешения коллизий является использование дополнительной области переполнения следующим образом. Если очередная запись распределяется с помощью функции хэширования в блок, а он полностью заполнен, то в области переполнения формируется список записей, соответствующих этому блоку, с включением в него указанной записи, а в сам блок заносится указатель – адрес связи на первую запись этого списка. Возможны и другие способы разрешения коллизий. Рассмотрим реализацию основных операций и дадим оценку числа обращений к ВП при их выполнении. Поиск записи с заданным значением ключа и чтение По заданному значению ключа x подсчитывается значение функции f(x). Далее из ВП считывается блок, находящийся по адресу f(x). В ОП внутри этого блока перебором ищется нужная запись. Если записей в блоке нет, то по указателю в блоке (адресу связи) читается первая запись списка переполнения, относящаяся к этому блоку. Далее необходимая запись ищется по этому списку. Число обращений к ВП при этом равно:
Модификации записи Осуществляется поиск и чтение записи, затем в ОП модифицируются поля записи (не являющиеся первичным ключом), запись заносится на свое место. Число обращений к ВП в этом случае на единицу больше, чем при чтении записи. Если модифицируется значение ключа, то занесение записи осуществляется как ввод новой записи (добавление). Удаление записи Осуществляется поиск и чтение записи. Если удаляемая запись находилась в блоке основной памяти, на ее место заносится «пустая» запись (или признак «пустой» записи). Если удаляемая запись находилась в списке области переполнения, удаление ее производится по правилам удаления элемента списка. Число обращений к ВП при удалении находится примерно в тех же пределах, что и для предыдущих операций. Добавление записи При добавлении записи со значением ключа x подсчитывается адрес соответствующего блока f(x). Блок считывается в ОП. Если в нем есть место, запись заносится в блок, блок записывается в ВП по своему адресу. Если блок заполнен, из него выбирается адрес начала списка записей, переполняющих блок. Далее добавление записи в список производится по правилам добавления элемента в список. Число обращений к ВП при добавлении записей находится примерно в тех же пределах, что и для предыдущих операций. Таким образом, описанная структура хранения с использованием хэширования является наиболее эффективной (из рассмотренных выше) по критерию минимизации числа обращений к ВП при реализации основных операций. 9.4.6. Комбинированные структуры храненияНеобходимо заметить, что в СУБД могут использоваться как каждая из вышерассмотренных структур в отдельности, так и их комбинация. Так, например, в ряде промышленных систем UNIBAD, БАНК для ЭВМ типа IBM 360/370 (ЕС ЭВМ), PARADOX для персональных ЭВМ используются следующие комбинации методов:
Краткие итоги: Лекция посвящена вопросам физической организации данных в памяти компьютера (организации структур хранения). Физические модели представления данных жестко заложены в структуру конкретной СУБД и различны в различных системах управления базами данных. Заметим, что в данной лекции рассматриваются не структуры хранения конкретной СУБД, а некоторые типовые структуры хранения, на основе которых и реализуются физические модели организации данных в конкретных СУБД. Здесь описывается двухуровневая структура памяти компьютера как среда размещения данных; организация обмена между внешней и оперативной памятью, определяющая специфику обработки данных. Представлены типовые физические модели (структуры хранения данных) во внешней памяти ЭВМ (последовательное размещение физических записей, размещение физических записей в виде списковой структуры, использование индексов, организация данных в виде В-дерева, размещение записей с использованием хэширования, атакже комбинированные структуры хранения). Для основных структур хранения сделана оценка числа действий при выполнении операций поиска данных, чтения, занесения данных, модификации (корректировки), удаления. Более подробно с материалами этой лекции можно ознакомиться в [1-7]. Контрольные тесты. Задача 1. Общая характеристика внутреннего уровня базы данных. Вариант 1. Что такое внутренний уровень базы данных? ð концептуальное представление ð концептуальная модель, специфицированная в терминах СУБД ð+ структура хранения данных в памяти компьютера ð+ отображение концептуальной модели базы данных в физическую организацию данных Вариант 2. Что такое физическая модель данных? ð+ внутренний уровень базы данных ð концептуальная модель, специфицированная в терминах СУБД ð структура памяти компьютера ð+ отображение концептуальной модели базы данных в физическую организацию данных. Вариант 3. В каком виде концептуальная модель базы данных представляется в памяти компьютера? ð в виде модели данных ð+ в виде физической модели ð+ в виде структуры хранения ð+ как наборы физических записей Задача 2. Представление экземпляра логической записи Вариант 1. В каком виде представляется экземпляр логической записи? ð линейная последовательность байтов переменной длины ð+ линейная последовательность байтов фиксированной длины ð линейная последовательность байтов фиксированной длины с возможным указателем на другую область памяти ð линейная последовательность байтов переменной длины с возможным указателем на другую область памяти Вариант 2. Какие параметры характеризуют поле логической записи при его физическом представлении? ð+ количество занимаемых байтов ð+ тип представления данных ð наименование поля ð количество символов в значении поля Вариант 3. Какие параметры поля логической записи не являются характеристиками его физическом представлении? ð количество занимаемых байтов ð тип представления данных ð+ наименование поля ð+ количество символов в значении поля Задача 3. Организация обмена между оперативной и внешней памятью. Вариант 1. Что является единицей обмена между внешней и оперативной памятью? ð экземпляр логической записи ð логический файл ð физический файл ð+ физическая запись ð+ страница Вариант 2. Почему обмен между оперативной и внешней памятью осуществляется страницами или физическими записями? ð+ для сокращения времени обработки ð для сокращения занимаемого объема оперативной памяти ð для сокращения занимаемого объема внешней памяти ð+ для сокращения числа обращений к внешней памяти Вариант 3. Почему обмен между оперативной и внешней памятью нецелесообразно осуществлять отдельными экземплярами логических записей? ð+ затрачивается большое время на обработку данных ð используется чрезмерно много оперативной памяти ð используется чрезмерно много внешней памяти ð трудно осуществлять поиск необходимых данных Задача 4. Последовательное размещение физических записей во внешней памяти. Вариант 1. Как осуществляется поиск записи с заданным значением ключа при последовательном размещении физических записей во внешней памяти? ð+ полным перебором ð по заданному адресу ð дихотомическим методом ð чтением записи с заданным значением ключа Вариант 2. Какой формулой оценивается среднее число обращений к внешней памяти при поиске записи с заданным значением ключа при последовательном размещении физических записей во внешней памяти (N - число экземпляров логических записей, k - коэффициент блокировки)? ð+ (1+  )/2 ð N ð log2(1+  )/2 ð  Вариант 3. Когда при добавлении новой физической записи при последовательном размещении физических записей во внешней памяти требуется затратить меньше действий? ð+ при добавлении в конец физического файла ð при вставке в нужное место физического файла ð при вставке в начало физического файла ð при добавлении новой физической записи на место удаляемой физической записи. Задача 5. Размещение физических записей в виде списковой структуры. Вариант 1. Как осуществляется поиск записи с заданным значением ключа при размещении физических записей в виде списковой структуры? ð+ полным перебором ð по заданному адресу ð дихотомическим методом ð чтением записи с заданным значением ключа Вариант 2. Какой формулой оценивается среднее число обращений к внешней памяти при поиске записи с заданным значением ключа при размещении физических записей в виде списковой структуры? (N число экземпляров логических записей, k коэффициент блокировки)? ð+ (1 + )/2 ð N ð log2(1+  )/2 ð log2 N/k Вариант 3. Как примерно соотносится объем затрачиваемых действий при добавлении новой физической записи при размещении физических записей в виде списковой структуры? ð меньше при добавлении в конец физического файла ð больше при вставке в нужное место физического файла ð меньше при вставке в начало физического файла ð больше при добавлении новой физической записи на место удаляемой физической записи ð+ примерно равны Задача 6. Использование индексов Вариант 1. Как хранятся физические записи в памяти при использовании индексации? ð упорядочены по значениям ключа ð+ в виде неупорядоченной последовательности ð в виде списка ð+ используется дополнительный файл Вариант 2. Что такое индекс? ð+ дополнительная таблица ð адрес связи у физической записи основного файла ð В-дерево ð Хэш-функция Вариант 3. К чему приводит использование индекса? ð+ к сокращению времени поиска ð к сокращению времени добавления записи ð+ к сокращению числа обменов между оперативной и внешней памятью ð+ к увеличению объема занимаемой памяти ð+ к дублированию информации Задача 7. Использование В-дерева. Вариант 1. Из каких полей состоит запись всех уровней В-дерева, кроме нижнего? ð+ из поля ключа и поля ссылки на нижележащий уровень ð из поля ключа и поля ссылки на вышележащий уровень ð из полей логической записи и поля ссылки на нижележащий уровень ð из полей логической записи и поля ссылки на вышележащий уровень Вариант 2. Что происходит при добавлении записи в В-дерево? ð+ может увеличиться число блоков нижнего уровня ð+ может увеличиться число блоков всех уровней ð+ может увеличиться число уровней ð структура дерева не меняется Вариант 3. К чему приводит использование В-дерева? ð+ к сокращению времени поиска ð к сокращению времени добавления записи ð+ к сокращению числа обменов между оперативной и внешней памятью ð+ к увеличению объема занимаемой памяти ð+ к дублированию информации Задача 8. Размещение физических записей с использованием хэширования Вариант 1. Как осуществляется поиск записи с заданным значением ключа при размещении физических записей с использованием хэширования? ð полным перебором ð+ по вычисленному адресу ð дихотомическим методом ð чтением записи с заданным значением ключа Вариант 2. Как примерно оценивается среднее число обращений к внешней памяти при поиске записи с заданным значением ключа при размещении физических записей с использованием хэширования? (N число экземпляров логических записей)? ð пропорционально N ð+ небольшое число ð пропорционально log 2 N ð как некоторая функция f(N) Вариант 3. Как примерно соотносится объем затрачиваемых действий при добавлении новой физической записи при размещении физических записей с использованием хэширования? ð меньше при добавлении в конец физического файла ð больше при вставке в нужное место физического файла ð меньше при вставке в начало физического файла ð больше при добавлении новой физической записи на место удаляемой физической записи ð+ примерно равны Литература
Лекция 10. Структура современной СУБД на примере Microsoft SQL Server 2008 В лекции рассматривается архитектура системы управления базами данных на примере одной из наиболее распространенных клиент-серверных СУБД - Microsoft SQL Server 2008 (логический и физический уровни). Ключевые термины: структура СУБД, архитектура СУБД, логический уровень, архитектура СУБД, физический уровень СУБД, архитектура Microsoft SQL Server 2008. Цель лекции: показать основные элементы структуры современной СУБД (архитектуры базы данных и структуры программного обеспечения) на примере Microsoft SQL Server 2008. 10.1 Общая структура СУБД Для лучшего понимания принципов работы современных СУБД рассмотрим структуру одной из наиболее распространенных клиент-серверных СУБД - Microsoft SQL Server 2008. Несмотря на то, что каждая коммерческая СУБД имеет свои отличительные особенности, информации о том, как устроена какая-то из СУБД, обычно бывает достаточно для быстрого первоначального освоения другой СУБД. Краткий обзор возможностей Microsoft SQL Server - 2008 был приведен в разделе, посвященном краткому обзору современным СУБД. В данном разделе рассмотрим основные моменты, связанные со структурой соответствующей СУБД (архитектурой базы данных и структурой программного обеспечения) Под архитектурой (структурой) базы данных конкретной СУБД будем понимать основные модели представления данных, используемые в соответствующей СУБД а также взаимосвязи между этими моделями. В соответствии с рассмотренными в лекции 3 различными уровнями описания данных различают разные уровни абстракции архитектуры базы данных Логический уровень (уровень модели данных СУБД) - средство представления концептуальной модели). Здесь каждая СУБД имеет некоторые отличия, но они являются не очень значительными. Отметим, что у разных СУБД существенно отличаются механизмы перехода от логического к физическому уровню представления. Физический уровень (внутреннее представление данных в памяти ЭВМ - физическая структура базы данных). Данный уровень рассмотрения подразумевает изучение базы данных на уровне файлов, хранящихся на жестком диске. Структура этих файлов – особенность каждой конкретной СУБД, в т.ч. и Microsoft SQL Server.  Рис. 10.1. Архитектура базы данных в Microsoft SQL Server 2008 10.2. Архитектура базы данных. Логический уровень Рассмотрим логический уровень представления базы данных (http://msdn.microsoft.com). Microsoft SQL Server 2008 представляет собой реляционную СУБД (данные представляются в виде таблиц). Таким образом, основной структурой модели данных этой СУБД являются таблицы. |