Тема_8 (1122356), страница 8

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 8)

Кузнецов. Базы данных.105Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (15)Индексы (3)Общей идеей любой организации индекса,поддерживающего прямой доступ по ключу ипоследовательный просмотр в порядкевозрастания или убывания значений ключаявляетсяхранение упорядоченного списка значений ключа спривязкой к каждому значению ключа спискаидентификаторов кортежейОдна организация индекса отличается от другойглавным образом в способе поиска ключа сзаданным значением12.11.2009С.Д. Кузнецов.

Базы данных.106Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (16)Индексы (4) B+-деревья (1)Наиболее популярным подходом к организации индексов в базахданных является использование техники B+-деревьевТехника B- и B+-деревьев была предложена в начале 1970-х гг.Рудольфом Байером (Rudolf Bayer) и Эдом Маккрейтом (Ed McCreight)С точки зрения внешнего логического представления B-дерево – этосбалансированное сильно ветвистое дерево во внешней памятиСбалансированность означает, что длина пути от корня дерева клюбому его листу одна и та жеВетвистость дерева – это свойство каждого узла дерева ссылаться набольшое число узлов-потомковС точки зрения физической организации B-дерево представляется какмультисписочная структура страниц внешней памяти,т.е.

каждому узлу дерева соответствует блок внешней памяти (страница)В B+-дереве внутренние и листовые страницы обычно имеют разнуюструктуру12.11.2009С.Д. Кузнецов. Базы данных.107Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (17)Индексы (5) B+-деревья (2)N1 ключ1 N2 ключ2 N3 ключ3 . . . Nm ключm Nm+1 Типовая структура внутренней страницы B+-дереваВыдерживаются следующие свойства:ключ1 ≤ ключ2 ≤ ... ≤ ключm;в странице дерева Nm находятся ключи k со значениямиключm <= k <= ключm+1ключ1 список1 ключ2 список2 .

. . ключk списокkСтруктура листовой страницы B+-дерева.Листовая страница обладает следующими свойствами:ключ1 < ключ2 < ... < ключk;списокr – упорядоченный список идентификаторов кортежей (tid),включающих значение ключr; листовые страницы связаны одно- или двунаправленным списком12.11.2009С.Д. Кузнецов. Базы данных.108Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (18)Индексы (6) B+-деревья (3)Поиск в B+-дереве – это прохождение от корня к листу всоответствии с заданным значением ключаЗаметим, что поскольку B+-деревья являются сильноветвистыми и сбалансированными, для выполнения поиска по любому значению ключапотребуется одно и то же (и обычно небольшое) числообменов с внешней памятьюБолее точно, в сбалансированном дереве, где длины всехпутей от корня к листу одни и те же, если во внутреннейстранице помещается n ключей, то при хранении m записейтребуется дерево глубиной logn(m)Если n достаточно велико (обычный случай), то глубинадерева невелика, и производится быстрый поиск12.11.2009С.Д.

Кузнецов. Базы данных.109Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (19)Индексы (7) B+-деревья (4)Основной «изюминкой» B+-деревьев является автоматическоеподдержание свойства сбалансированностиРассмотрим, как это делается при выполнении операцийзанесения и удаления записей.При занесение новой записи выполняются следующие действияПоиск листовой страницыФактически, производится обычный поиск по ключуЕсли в B+-дереве не содержится ключ с заданным значением, то будетполучен номер страницы, в которой ему надлежит содержаться, исоответствующие координаты внутри страницыПомещение записи на местоЕстественно, что вся работа производится в буферах оперативнойпамятиЛистовая страница, в которую требуется занести запись, считывается вбуфер, и в нем выполняется операция вставкиРазмер буфера должен превышать размер страницы внешней памяти12.11.2009С.Д.

Кузнецов. Базы данных.110Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (20)Индексы (8) B+-деревья (5)Если после выполнения вставки новой записи размер используемойчасти буфера не превосходит размера страницы, тона этом выполнение операции занесения записи заканчиваетсяБуфер может быть немедленно вытолкнут во внешнюю память, иливременно сохранен в основной памяти в зависимости от политикиуправления буферамиЕсли же возникло переполнение буфера (т.е. размер егоиспользуемой части превосходит размер страницы), товыполняется расщепление страницыДля этого запрашивается новая страница внешней памяти,используемая часть буфера разбивается, грубо говоря, пополам (так,чтобы вторая половина также начиналась с ключа), ивторая половина записывается во вновь выделенную страницу, ав старой странице модифицируется значение размера свободной памятиЕстественно, модифицируются ссылки по списку листовых страниц12.11.2009С.Д.

Кузнецов. Базы данных.111Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (21)Индексы (9) B+-деревья (6)Чтобы обеспечить доступ от корня дерева к зановозаведенной странице, необходимосоответствующим образом модифицировать внутреннююстраницу, являющуюся предком ранее существовавшейлистовой страницы,oт.е. вставить в нее соответствующее значение ключа и ссылку нановую страницуПри выполнении этого действия может снова произойтипереполнение теперь уже внутренней страницы, и она будетрасщеплена на двеВ результате потребуется вставить значение ключа и ссылку нановую страницу во внутреннюю страницу-предка выше поиерархии и т.д.Предельным случаем является переполнение корневойстраницы B+-дереваВ этом случае она тоже расщепляется на две, и заводится новаякорневая страница дерева, т.е.

его глубина увеличивается наединицу12.11.2009С.Д. Кузнецов. Базы данных.112Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (22)Индексы (10) B+-деревья (7)При удалении записи выполняются следующиедействияПоиск записи по ключуЕсли запись не найдена, то, значит, удалять ничего ненужно.Реальное удаление записи в буфере, в которыйпрочитана соответствующая листовая страницаЕсли после выполнения этой подоперации размерзанятой в буфере области оказывается таковым, чтоего сумма с размером занятой области в листовыхстраницах, являющихся левым или правым братомданной страницы, больше, чем размер страницы,операция завершается12.11.2009С.Д.

Кузнецов. Базы данных.113Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (23)Индексы (11) B+-деревья (8)Иначе производится слияние с правым или левымбратом,т.е. в буфере производится новый образ страницы,содержащей общую информацию из данной страницы иее левого или правого братаСтавшая ненужной листовая страница заносится в списоксвободных страницСоответствующим образом корректируется списоклистовых страницЧтобы устранить возможность доступа от корня косвобожденной странице, нужно удалитьсоответствующее значение ключа и ссылку наосвобожденную страницу из внутренней страницы – еепредкаПри этом может возникнуть потребность в слиянии этойстраницы с ее левым или правыми братьями и т.д.12.11.2009С.Д. Кузнецов.

Базы данных.114Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (24)Индексы (12) B+-деревья (9)Предельным случаем является полноеопустошение корневой страницы дерева,которое возможно после слияния последнихдвух потомков корняВ этом случае корневая страница освобождается, аглубина дерева уменьшается на единицуКак видно, при выполнении операцийвставки и удаления свойствосбалансированности B+-деревасохраняется, а внешняя памятьрасходуется достаточно экономно12.11.2009С.Д.

Кузнецов. Базы данных.115Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (25)Индексы (13) B+-деревья (10)Проблемой является то, что при выполнении операциймодификации слишком часто могут возникать расщепленияи слиянияЧтобы добиться эффективного использования внешнейпамяти с минимизацией числа расщеплений и слияний,применяются более сложные приемы, в том числе: упреждающие расщепления,переливания,т.е. расщепления страницы не при ее переполнении, а несколькораньше, когда степень заполненности страницы достигаетнекоторого уровня;т.е. поддержание равновесного заполнения соседних страниц;слияния 3-в-2,т.е. порождение двух листовых страниц на основе содержимоготрех соседних12.11.2009С.Д.

Кузнецов. Базы данных.116Организация данныхОбщие принципы организации данных во внешней памяти в SQL-ориентированных СУБД (26)Индексы (14) B+-деревья (11)Следует заметить, что при организациимультидоступа к B+-деревьям, характерного приих использовании в СУБД, приходится решатьряд нетривиальных проблемКонечно, грубые решения очевидны, например,возможен монопольный захват B+-дерева (т.е.его корневого блока) на все выполнениеоперации модификацииНо существуют и более тонкие решения,рассмотрение которых выходит за пределыматериала этой лекции12.11.2009С.Д. Кузнецов.

Характеристики

Список файлов лекций