ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 1581
Скачиваний: 23
151
Рис
Пример
структуры
индекса
типа
В
-
дерева
Рассмотрим
,
например
,
как
происходит
поиск
записи
индексируемого
файла
,
у
которой
индексируемое
поле
имеет
значение
Москва
.
Сравнение
этого
значения
со
значениями
ключевой
корневой
страницы
индексной
структуры
приводит
по
указателю
ко
второй
странице
следующего
уровня
дерева
(
так
как
Москва
по
алфавиту
расположена
ниже
Липецка
,
но
выше
Ростова
).
Сравнение
152
искомого
значения
со
значениями
ключей
второй
страницы
среднего
уровня
приводит
по
указателю
к
четвертой
странице
нижнего
(
листового
)
уровня
дерева
(
Москва
по
алфавиту
выше
Норильска
),
в
которой
находится
сам
указатель
на
соответствующую
запись
индексируемого
файла
данных
.
Одним
из
недостатков
обычных
иерархических
древовидных
структур
является
нарушение
их
сбалансированности
после
операций
удаления
и
вставки
элементов
дерева
.
Однако
,
достоинством
В
+
-
деревьев
является
то
,
что
в
них
достаточно
просто
возможно
автоматическое
поддержание
сбалансированности
дерева
,
то
есть
поддержание
более
-
менее
равномерной
заполненности
страниц
индексной
структуры
и
одинаковой
длины
пути
от
корня
до
листа
дерева
для
поиска
любых
значений
не
зависимо
от
их
расположения
в
файле
данных
.
Рассмотрим
алгоритм
перестройки
В
-
дерева
при
вставке
в
индексируемый
файл
новой
записи
.
В
В
-
дереве
производится
поиск
листовой
страницы
,
соответствующей
новому
значению
вводимой
записи
.
Если
в
В
-
дереве
даже
не
содержится
ключа
с
заданным
значением
,
то
находится
номер
страницы
,
в
котором
он
должен
содержаться
и
координаты
этого
значения
внутри
страницы
.
Листовая
страница
,
в
которую
требуется
занести
запись
,
считывается
в
буфер
оперативной
памяти
.
Операция
вставки
записи
осуществляется
в
этом
буфере
,
при
этом
его
размеры
должны
превышать
размеры
страницы
внешней
памяти
.
Если
после
выполнения
вставки
записи
в
буфер
размер
используемой
части
буфера
не
превысил
размера
страницы
,
то
на
этом
выполнение
операции
вставки
записи
заканчивается
.
Буфер
может
быть
или
немедленно
выгружен
во
внешнюю
память
,
или
временно
сохранен
в
оперативной
памяти
,
в
зависимости
от
политики
управления
буферами
.
Если
же
возникло
переполнение
буфера
(
т
.
е
.
размер
его
используемой
размер
то
расщеп
сво
фицируются
ссылки
по
списку
листовых
страниц
.
Чтобы
обеспечить
доступ
от
корня
дерева
к
заново
заведенной
странице
,
необходимо
соответствующим
образом
модифицировать
внутреннюю
страницу
В
-
дерева
,
являющуюся
предком
ранее
существовавшей
(
расщепленной
)
листовой
страницы
,
т
.
е
.
вставить
в
нее
соответствующее
ключевое
значение
и
ссылку
на
новую
страницу
.
При
выполнении
этого
действия
,
которое
также
осуществляется
в
буфере
оперативной
памяти
,
может
снова
произойти
переполнение
теперь
уже
внутренней
страницы
,
и
она
будет
расщеплена
на
две
.
В
результате
потребуется
вставить
значение
ключевого
значения
и
ссылку
на
новую
страницу
во
внутреннюю
страницу
-
предок
выше
по
иерархии
дерева
и
т
.
д
.
части
превысил
страницы
),
выполняется
ление
страницы
.
Для
этого
запрашивается
новая
страница
внешней
памяти
,
используемая
часть
фера
разбивается
пополам
и
вторая
полови
бу
на
записывается
во
вновь
выделенную
страницу
,
а
в
старой
странице
модифицируется
значение
размера
бодной
памяти
.
Естественно
,
моди
153
Предельным
случаем
является
переполнение
корневой
страницы
В
-
дерева
.
В
этом
случае
она
также
расщепляется
на
две
,
и
заводится
новая
корневая
страница
дерева
,
т
.
е
.
его
глубина
увеличивается
на
единицу
.
При
удалении
записи
выполняются
следующие
действия
.
Производится
поиск
записи
в
листовой
странице
по
ключевому
значению
.
Если
запись
не
найдена
,
то
,
следовательно
,
удалять
ничего
не
нужно
.
Если
запись
найдена
,
то
соответствующая
ей
листовая
страница
считывается
в
буфер
оперативной
памяти
.
В
буфере
производится
реальное
удаление
записи
.
Если
после
выполнения
этой
подоперации
размер
занятой
в
буфере
области
оказывается
таковым
,
что
его
сумма
с
размером
занятой
области
в
слияние
из
данной
образом
на
освобожденную
страницу
из
внутренней
страницы
В
-
дерева
,
являющейся
предком
освобожденной
страницы
.
При
этом
,
из
-
за
уменьшения
занятой
области
этой
страницы
-
предка
может
возникнуть
потребность
в
ее
слиянии
уже
с
ее
левым
или
правым
«
братьями
»
и
т
.
д
.
Предельным
случаем
является
полное
опустошение
корневой
страницы
дерева
,
которое
возможно
после
слияния
последних
двух
потомков
корня
.
В
этом
случае
корневая
страница
освобождается
.
Как
видно
из
вышеизложенного
,
при
выполнении
операций
вставки
и
удаления
свойство
сбалансированности
В
-
дерева
сохраняется
,
а
внешняя
память
расходуется
достаточно
экономно
,
обеспечивая
среднее
заполнение
страниц
больше
,
чем
наполовину
.
Говоря
о
повышении
скорости
доступа
к
данным
при
использовании
индексирования
полей
,
следует
иметь
в
виду
,
что
индексирование
повышает
эффективность
именно
операции
выборки
,
т
.
е
.
чтения
данных
.
Если
же
выполняется
операция
,
связанная
с
изменением
данных
,
т
.
е
.
вставка
или
удаление
кортежа
,
изменение
значения
атрибута
,
по
которому
построен
индексный
файл
,
то
наличие
индексации
приводит
к
замедлению
операции
.
Дело
в
том
,
что
каждое
такое
изменение
приводит
к
необходимости
соответствующей
перестройки
индексных
файлов
,
относящихся
к
модифицируемым
полям
,
что
,
очевидно
,
требует
дополнительного
времени
.
листовых
страницах
,
являющихся
левым
или
правым
«
братом
»
данной
страницы
,
больше
,
чем
размер
страницы
,
то
операция
завершается
.
Если
эта
сумма
оказывается
меньше
размера
страницы
,
то
производится
данной
страницы
с
ее
левым
или
правым
«
братом
»,
т
.
е
.
в
буфере
формируется
образ
новой
страницы
,
содержащей
общую
информацию
страницы
и
ее
левого
или
правого
«
брата
».
Ставшая
ненужной
листовая
страница
заносится
в
список
свободных
страниц
.
При
этом
соответствующим
корректируется
список
листовых
страниц
.
Чтобы
устранить
возможность
доступа
от
корня
к
освобожденной
странице
,
нужно
удалить
соответствующее
ключевое
значение
и
ссылку
12.
Управление
транзакциями
и
целостность
баз
данных
Одним
из
важнейших
требований
к
функционированию
любых
информационных
систем
с
базами
данных
является
поддержание
хранимых
данных
в
целостном
,
логически
согласованном
состоянии
.
Только
при
выполнении
этого
требования
данные
представляют
какую
-
либо
ценность
для
пользователей
.
База
данных
находится
в
согласованном
(
целостном
)
состоянии
,
если
в
ней
выполнены
(
удовлетворены
)
все
ограничения
целостности
,
определенные
для
базы
данных
.
На
практике
,
однако
,
в
случае
,
когда
данные
в
базе
данных
не
являются
статическими
,
а
изменяются
во
времени
,
обеспечение
этого
требования
сопряжено
с
целым
рядом
серьезных
трудностей
.
Дело
в
том
,
что
при
осуществлении
целого
ряда
операций
над
данными
оказывается
принципиально
невозможным
избежать
состояния
базы
данных
,
когда
содержащиеся
в
ней
данные
находятся
в
логически
несогласованном
,
не
целостном
состоянии
.
Рассмотрим
пример
.
Пусть
в
базе
данных
имеются
два
отношения
:
отношение
Студент
,
имеющее
два
атрибута
Имя
_
студента
и
Средний
_
балл
,
и
отношение
Успеваемость
с
атрибутами
Имя
_
студента
,
Дисциплина
,
Оценка
.
Значение
атрибута
Средний
_
балл
отношения
студент
представляет
собой
среднее
значение
оценок
конкретного
студента
,
полученных
им
по
всем
сданным
дисциплинам
.
Если
теперь
,
мы
производим
ввод
в
отношение
Успеваемость
данных
об
оценке
,
полученной
неким
студентом
по
сданной
им
новой
дисциплине
,
то
помимо
ввода
соответствующего
нового
кортежа
в
отношение
Успеваемость
,
в
отношении
СТУДЕНТ
должно
быть
скорректировано
и
значение
атрибута
СРЕДНИЙ
БАЛЛ
для
этого
студента
.
Очевидно
,
что
из
-
за
последовательного
во
времени
выполнения
этих
двух
действий
,
имеется
момент
времени
,
когда
база
данных
находится
в
рассогласованном
,
не
целостном
состоянии
,
т
.
е
.
когда
находящееся
в
базе
данных
значение
среднего
балла
студента
не
соответствует
его
новому
фактическому
значению
после
ввода
новой
оценки
студента
.
Такого
рода
ситуации
встречаются
при
модификации
содержимого
базы
данных
достаточно
часто
.
Таким
образом
,
в
процессе
выполнения
операций
над
хранимыми
данными
происходит
переход
базы
данных
из
одного
согласованного
состояния
в
другое
согласованное
состояние
.
Между
двумя
этими
состояниями
данные
в
базе
данных
могут
быть
рассогласованными
.
Потенциальная
опасность
такого
рода
ситуаций
состоит
в
том
,
что
возможны
случаи
,
когда
вследствие
внешних
155
причин
(
например
,
аварийного
сбоя
системы
)
операция
по
модификации
данных
не
выполняется
до
конца
,
и
база
данных
остается
в
рассогласованном
состоянии
.
Еще
одной
возможной
причиной
возникновения
рассогласованности
данных
в
базе
данных
является
одновременное
выполнение
операций
по
модификации
данных
несколькими
пользователями
одной
базы
данных
.
Механизмом
,
предназначенным
в
СУБД
для
обеспечения
при
модификации
данных
корректного
перевода
базы
данных
из
одного
согласованного
состояния
в
другое
,
является
механизм
управления
транзакциями
.
Наличие
и
поддержание
механизма
транзакций
является
одним
из
важных
показателей
уровня
развитости
СУБД
,
уровня
обеспечения
в
управляемой
ею
базе
данных
целостности
данных
и
их
устойчивости
к
возможным
сбоям
аппаратных
и
программных
средств
и
конфликтам
при
совместной
работе
с
данными
нескольких
пользователей
.
Транзакция
–
это
логическая
единица
работы
СУБД
,
это
последовательность
операторов
манипулирования
данными
,
выполняющаяся
как
единое
целое
и
переводящая
базу
данных
из
одного
согласованного
состояния
в
другое
.
Лозунг
транзакции
– «
все
или
ничего
».
Транзакция
обладает
четырьмя
важными
свойствами
:
•
А
томарность
,
•
С
огласованность
,
•
И
золированность
и
•
Д
олговечность
.
Их
обычно
называют
свойствами
АСИД
(
по
первым
буквам
свойств
).
Атомарность
.
Транзакция
выполняется
как
атомарная
,
неделимая
операция
–
либо
выполняется
вся
операция
целиком
,
либо
она
целиком
не
выполняется
(
все
или
ничего
).
Согласованность
.
Транзакция
переводит
базу
данных
из
одного
согласованного
(
целостного
)
состояния
в
другое
согласованное
(
целостное
)
состояние
,
без
обязательной
поддержки
согласованности
данных
во
все
промежуточные
моменты
времени
.
Изолированность
.
Транзакции
отделены
(
изолированы
)
одна
от
другой
.
Это
означает
,
что
транзакции
,
инициированные
разными
пользователями
не
должны
влиять
друг
на
друга
(
тем
более
мешать
друг
другу
),
т
.
е
.
они
должны
выполняться
так
,
как
если
бы
они
выполнялись
по
очереди
,
последовательно
друг
за
другом
.
Долговечность
.
Если
транзакция
выполнена
,
то
результаты
ее
работы
должны
сохраниться
в
базе
данных
,
даже
если
в
следующий
момент
произойдет
сбой
системы
.
Обычно
транзакция
начинается
автоматически
с
момента
присоединения
пользователя
(
запроса
)
к
базе
данных
и
продолжается
до
тех
пор
,
пока
не
произойдет
одно
из
следующих
событий
.