Базы Данных, 23 лекция (от 24 ноября)

Материал из eSyr's wiki.

Предыдущая лекция | Следующая лекция

Б-деревья

те, кто не пришли горько пожалеют.

Если нужна точная информация, то лучше прочитать Искусство программирования, т. 3 «Сортировка и поиск»

Технология деревьев прошла в два этапа. Сначала, с чего всё начаналось, потом тот вид, который последние 52-30 лет.

Классические В-деревья. Они именно В, поотму что потом будут В+(*)-деревья

Полностью сбалансированные сильно ветвистые деревья.

<Значение ключа, запись>

Лектор говорит про уникальные В-деревья, то есть для каждого знач клбюча всего одна запись.

Когда говорят про ключ доступ к файлу, там много ключей, и по нему имеется поиск.

Тут совершенно неважно, является ли ключ частью записи или это просто некоторая внешняя вещь.

Требуется только одна вещь – ТД, по которому определяется ключ, должен быть упорядочен (=, !=, >, <, >=, <=).

Вообще, В-дерево выглядит так:

Причём требуется, чтобы длина всех путей была одна и та же.

Различие в том, как организованы блоки.

Листовой блок:

Ключ1, запись1, ключ2, запись2, ..., ключН, записьН.

Для нелистовых:

Ключ1, запись1, номер блока1, ключ2, запись2, ноер блока2, ... ключН, записьН.

Ключ1 меньше ключ2 меньше ... меньше ключн

В блоке, на который ссылка номер блока1:

Ключ11, запись11, ключ12, запись12, ..., ключ1Н, запись1Н

Ключ1 меньше Ключ11 меньше ключ12 меньше ... меньше ключ1н меньше ключ2

Когда дерево создаётся, есть только один блок. Потом туда заносятся ссылки на детей.

Когда метса не хватает, он расщепляется пополам и поверх ставится новый корень:

ключ1, запись1, номер блока1, ключ2, запись2, номер блока2 

где ключ2, запись2 берутся из середины переполненного.

При удалении делается обратная операция – если блок становится маленьким, то делается слияние.

Почему это не будет расск подробно, и почему это не используется – потому что лектор про балансировку сказал неправду. Там ещё есть много тонких моментов балансировки, здесь в классических б-деревьях, как для АВЛ-деревьевЮ надо делать поворот. Для АВЛ-деревьев поворот делать нетрудно, а для в-деревьев трудно, потому что они во внешней памяти. Это первое.

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

Ещё одна проблема – то, что ветвистость определяется не столько размером ключа, сколько размером записи, а они могут быть большими.

Ещё здесь не выполняется последнее условие – одно и то же время поиска.

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

В+(*)-деревья.

Есть две разновидности блока:

1. Промежуточные. Строятся таким вот образом:

ключ1 Nsigma1 ключ2 Nsigma2 ключн Nsigman ключ1 <= ключ2 <= ключн

1. Листовые блоки

ключ11 запись11 ... ключ1н запись1н Тут записи только в листовых записях. Такая структура гораздо более плотная, чем справа.

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

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

При проектировании СУБД приходится иногда принимать непопулярные решения.

Ткеперь поговорим про изменния.

Изменения – вставка и удаления.

Забудем про то, что В-деревья можно исп для любого файла.

Мы хотим иметь ассоц. доступ к таблицам БД. В терминах БД запись – последовательность тидов

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

В БД этот ключ может быть одним столбцом таблицы (индекс на стобце а) или списком столбцов произв. размера. Все эти столбцы должны быть в одной таблице. Для них порядок сравнения – лексикографический.

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

Операции модификации В-дерева.

1. Вставка
2. Удаление

После перерыва, естественно.

Берётся Б-дерево и делаяется та же самая операция, как мы бы хотели найти ключ, то есть смотрим, куда попадает новый ключ. В конце концов попадаем в листовой блок. По нему идём последовательно, раздвигаем содержимое блока, втыкаем новое значение, ставим на место. Что делаетсяЮ, если он переполняется. Тогда начинает работать процедура, которая называется расщепление (splitting). На самом деле, для работы с Б-деревьями выбираются буфера памяти в два раза больше, чем основной памяти, и всегда вставка делается по месту в основной буфер, считается, что предельный размер пары ключ-тид не больше блока. Теперь смотрим, влезает в блок буфер или нет. Тогда грубо говоря находится такой ключ к, который находится примерно по серединке, то есть бъёт буфер попола,. У него первая половинка пишется в блок, а для второй половинки пишется новый бло. Теперь получаетмя, что у первого ссылка есть, а вторгой – беспризорник. Теперь берётся ключ к, и пишется в предка ключ и ссылку. Делается всё то же самое. Это делается до тех пор, пока не успокоимся, или пока не дойдём до корня. Если корень переполнился, то заводится новый корень, и в нём будет всего две ссылки. ОК.

Что делается при удалении.

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

Гречушкин выпендривается – сказал, что нехорошо, если будем ровно половину, то при каждом добавлении будет то разбиение, то слияние. Лектор ему ответил, что он торопится, что он тоже может рассказывать всё сразу, даже те вещи, которые он не ожидает, и всё это одновременно, но это же нехорошо. Лектор хочет сказать всё одновременно, но он терпит и оставляет на потом.

Самое противное в В-деревьях – нееоторая дерготня, которая происходит, когда то удаляем, то вставляем. Рано или поздно система попадает в ситуацию, что при каждом удалении или вставке дерево перестраивается. Поэтому есть эмперическое правило, надо смотреть на lockload. Правило железное такое – 75%. Если ёмкость достигла 75 процентов, то надо расщеплять. Если можем слить, но слияние будет больше 75%, то лучше подождать. Это штука эмпирическая, и за ней нужно следить. - имхо, то же самое.

Потом появились разные штучки:

1. Слияние 3-в-2
2. Расщепление 2-в-3

При операции вставки мы видим предка и его симплингов, то смотрим не на одного брата, а на много братьев.

Позволяют увеличить коэфициент заполненности блоков.

Перекливание:

прежде, чем разделить, смотьрим, не живёт ли брат слишком комфортно. Переливание – хороший шаг перед расщеплением.

Очень много приходится выполнять операций со сдвижкой – расдвижкой блоков. Больше всего ошибок лектор делал при ошибках сдвижки, как правило, на один байт.

Дублирующие ключи

Отказались от требования уникальности. То есть при вставке находим ключ с тидами и дописываем тид. Может получиться так, что ключ маленький, а тидов много, и может получиться так: ключ тид1 тид2 тидн и так на весь блок. Приходится его расщеплять, и это формальное расщепление, но это надо делать. На самом деле, если я ищу ключ 55, то я иду по самой левой ссылке, и потом пойду последовательно. С другой стороны, когда нормальные совершенно индексы, где по 3-4-5 значений с одним ключом. Но при реализации приходится думать о том, что их больше половины.

Составные ключи

составной ключ:

мама папа даша

мама папа лола

Эти мама и папа будут повторяться столько разЮ, сколько у них детей. А составные ключи обычно строятся из строк.

Жену лектора зовут Дмитришвили.

Можно делать компрессию Она хороша, когда мы экономим память, но плоха, когда мы желаем поиск.

Если в какой -нибудь опенсорц субд создаётся первич ключ, то по ней создаётся индекс и б-дерево.

Кластеризация

Таблица

Я хочу, чтобы клстеризовать записи по столбцу А, то есть по возможности чтобы они сидели с разных блоках памяти.

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

Кластеризация, которая придумана в Систем Р.

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

В заключение лектор скажет очень быстро, что кластеризация вещь безумно полезная, безумна важная, но очень ненадёжная, потому что могут возникнуть перекосы. Хорошо работает кластеризация при равномер распред ключа, и когда немного записей с одним и тем же ключом. Вторая вещь состоит в том, что это удаётся как-то соптимизировать. Тиды мы менять не хотим. Мы заранее думаем, а сколько примерно будет строк с таким знач ключа, и начинаем пихать близкие в один блок. Вот мы хорошо прокластеризовали записи в ключами 5, 8, 12 и тут попёрли шестёрки. Это называется вырождение кластеризации. И надо запускать реорганизацию.