Удаление записей из базы данных (логическое и физическое удаление)

Существует две разновидности удаления записей: логическое и физическое.

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

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

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

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

 

Ввод и запоминание новых записей

При вводе и запоминании новой записи система ищет ей свободное место в области хранения.

Размещение новых записей осуществляется разными способами в случае цепей и в случае динамической реорганизации блоков.

Корректировка значений элементов данных.

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

Доступ к записям БД.

Областью БД может быть файл или другое множество блоков.

Последовательная обработка предполагает выборку записей из области (файла) базы данных.

Доступ по КБД

КБД определяет место расположения записи в памяти ЭВМ. Зная КБД, система может наиболее быстро извлечь требуемую запись. В большинстве СУБД КБД выдается пользователям и его можно применять при обработке записей.

Доступ по первичному ключу.

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

 

Индексы

Как бы не были организованы индексы в конкретной СУБД, их основное назначение состоит в обеспечении эффективного прямого доступа к кортежу отношения по ключу. Обычно индекс определяется для одного отношения, и ключом является значение атрибута (возможно, составного). Если ключом индекса является возможный ключ отношения, то индекс должен обладать свойством уникальности, т.е. не содержать дубликатов ключа. На практике ситуация выглядит обычно противоположно: при объявлении первичного ключа отношения автоматически заводится уникальный индекс, а единственным способом объявления возможного ключа, отличного от первичного, является явное создание уникального индекса. Это связано с тем, что для проверки сохранения свойства уникальности возможного ключа так или иначе требуется индексная поддержка.

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

Наконец, одним из способов оптимизации выполнения эквисоединения отношений (наиболее распространенная из числа дорогостоящих операций) является организация так называемых мультииндексов для нескольких отношений, обладающих общими атрибутами. Любой из этих атрибутов (или их набор) может выступать в качестве ключа мультииндекса. Значению ключа сопоставляется набор кортежей всех связанных мультииндексом отношений, значения выделенных атрибутов которых совпадают со значением ключа.

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

B-деревья

Видимо, наиболее популярным подходом к организации индексов в базах данных является использование техники B-деревьев. С точки зрения внешнего логического представления B-дерево - это сбалансированное сильно ветвистое дерево во внешней памяти. Сбалансированность означает, что длина пути от корня дерева к любому его листу одна и та же. Ветвистость дерева - это свойство каждого узла дерева ссылаться но большое число узлов-потомков. С точки зрения физической организации B-дерево представляется как мультисписочная структура страниц внешней памяти, т.е. каждому узлу дерева соответствует блок внешней памяти (страница). Внутренние и листовые страницы обычно имеют разную структуру.

В типовом случае структура внутренней страницы выглядит следующим образом:

При этом выдерживаются следующие свойства:

· ключ(1) <= ключ(2) <=... <= ключ(n);

· в странице дерева Nm находятся ключи k со значениями ключ(m) <= k <= ключ(m+1).

Листовая страница обычно имеет следующую структуру: Листовая страница обладает следующими свойствами:

· ключ(1) < ключ(2) <... < ключ(t);

· сп(r) - упорядоченный список идентификаторов кортежей (tid), включающих значение ключ(r);

· листовые страницы связаны одно- или двунаправленным списком.

Поиск в B-дереве - это прохождение от корня к листу в соответствии с заданным значением ключа. Заметим, что поскольку деревья сильно ветвистые и сбалансированные, то для выполнения поиска по любому значению ключа потребуется одно и то же (и обычно небольшое) число обменов с внешней памятью. Более точно, в сбалансированном дереве, где длины всех путей от корня к листу одни и те же, если во внутренней странице помещается n ключей, то при хранении m записей требуется дерево глубиной log_n(m), где log_n вычисляет логарифм по основанию n. Если n достаточно велико (обычный случай), то глубина дерева невелика, и производится быстрый поиск.

Основной "изюминкой" B-деревьев является автоматическое поддержание свойства сбалансированности. Рассмотрим, как это делается при выполнении операций занесения и удаления записей.

При занесение новой записи выполняется:

· Поиск листовой страницы. Фактически, производится обычный поиск по ключу. Если в B-дереве не содержится ключ с заданным значением, то будет получен номер страницы, в которой ему надлежит содержаться, и соответствующие координаты внутри страницы.

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

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

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

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

· Предельным случаем является переполнение корневой страницы B-дерева. В этом случае она тоже расщепляется на две, и заводится новая корневая страница дерева, т.е. его глубина увеличивается на единицу.

При удалении записи выполняются следующие действия:

· Поиск записи по ключу. Если запись не найдена, то значит удалять ничего не нужно.

· Реальное удаление записи в буфере, в который прочитана соответствующая листовая страница.

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

· Иначе производится слияние с правым или левым братом, т.е. в буфере производится новый образ страницы, содержащей общую информацию из данной страницы и ее левого или правого брата. Ставшая ненужной листовая страница заносится в список свободных страниц. Соответствующим образом корректируется список листовых страниц.

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

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

Как видно, при выполнении операций вставки и удаления свойство сбалансированности B-дерева сохраняется, а внешняя память расходуется достаточно экономно.

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

· упреждающие расщепления, т.е. расщепления страницы не при ее переполнении, а несколько раньше, когда степень заполненности страницы достигает некоторого уровня;

· переливания, т.е. поддержание равновесного заполнения соседних страниц;

· слияния 3-в-2, т.е. порождение двух листовых страниц на основе содержимого трех соседних.

Следует заметить, что при организации мультидоступа к B-деревьям, характерного при их использовании в СУБД, приходится решать ряд нетривиальных проблем. Конечно, грубые решения очевидны, например монопольный захват B-дерева на все выполнение операции модификации. Но существуют и более тонкие решения, рассмотрение которых выходит за пределы нашего курса.

 

Хеширование

При запоминании новой записи специальная программ, называемая программой хеширования, ставит в соответствие значению первичного ключа номер блока, куда следует поместить запись. Так, все записи распределяются по блокам области хранения, в определенном порядке, вырабатываемом хеш-функцией (hash - размешивание).

Записи, для которых алгоритм хеширования выдает одинаковый результат, называются синонимами. Синонимы объединяются в цепной список, начало которого находится в заголовке блока. Если при запоминании очередного синонима для него не хватило места в блоке, то он размещается в другом блоке файла, но включается в цепь синонимов того блока, куда был хеширован.

При извлечении записи по первичному ключу, СУБД подключает программу хеширования, вычисляет номер блока, а затем просматривает цепь синонимов в это блоке.