Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лекции 29 марта и 5 апреля 2013 г.
Сильно ветвящееся Б-дерево
Если сильно ветвящееся дерево имеет ту особенность, что в своих вершинах содержит не по одному, а по нескольку ключей, и это множество ключей увязано со множеством ссылок на вершины-потомки, принято говорить о Б-дереве (о сильно ветвящемся Б-дереве), а его вершины называть страницами.
Каждая страница Б-дерева возглавляет собой Б-поддерево.
Сильно ветвящимся Б-деревом называется структура, страницы которой подчинены требованиям:
Число n называется порядком Б-дерева; n ≥ 1 .
Пример Б-дерева порядка 2 показан на Рис. 1.
Рис. 1
Множество ключей на странице может быть, в простейшем случае, организовано в виде линейного списка или в виде массива с диапазоном изменения индексов (1 .. n); в последнем случае множество ссылок на странице представляется массивом с диапазоном изменения индексов (0 .. n).
Если число n велико, оправдана древовидная организация ключей на странице.
По определению Б-дерева, у каждой страницы имеется либо не менее двух страниц-потомков, либо нет ни одной страницы-потомка. Все страницы-потомки одного предка уместно называть «страницами-сёстрами». Каждая (кроме корневой) страница имеет сестру – либо старшую (слева), либо младшую (справа).
В Б-деревьях используется понятие левого потомка (левого поддерева) и правого потомка (правого поддерева) для каждого ключа. Правый потомок i – го ключа является левым потомком (i + 1) – го ключа. У каждого ключа либо есть одновременно и левый, и правый потомки, либо одновременно нет ни того, ни другого.
Например, на Рис.1 левым потомком ключа «40» корневой страницы является страница с ключами «19, 28», правым потомком – страница с ключами «48, 57, 68».
Как и в деревьях оптимального поиска, уровень корневой страницы принимается равным 1, уровень её непосредственных потомков равен двум, и т.д.
Б-дерево называется Б-деревом поиска, если выполнены условия:
Структура, изображённая на Рис.1, является Б-деревом поиска.
Далее будут рассматриваться только Б-деревья поиска. Причём, слово «поиск», для краткости, будет опущено.
Включение нового ключа в Б-дерево
Все действия по реорганизации структуры рассматриваются на примере Б-дерева порядка 2.
Внесение нового ключа производится только в терминальную страницу Б-дерева.
Процедура включения будет иметь имя IncludeKey. Место для нового ключа отыскивается, по сути, так же, как и в двоичном дереве поиска. Если терминальная страница имеет уровень L, то внесением в дерево нового ключа занимается L – й экземпляр процедуры IncludeKey, вызываемый рекурсивно.
На Рис. 2 показано последовательное внесение ключей «29», «34», «32», «23», в изначально пустое Б-дерево (случай L = 1). Происходит формирование и допустимое пополнение корневой страницы (единственной пока).
|
(а) |
(б) |
(в) |
(г) |
Рис. 2
На Рис. 3 показано внесение ключа «33», переполняющего корневую страницу.
Порядок перестроения дерева таков.
В переполненном списке (содержащем 2∙n + 1 ключей) выбирается один срединный элемент («31»), левая половина списка (n ключей, «23», «29»), правая половина списка (n ключей, «32», «34»). Создаются две новые страницы (показаны синим цветом). Первая из них заполняется левой половиной списка и делается левым потомком корневой страницы. Вторая из них заполняется правой половиной списка и делается правым потомком корневой страницы. В корневой странице остаётся единственный, средний элемент списка (и вовсе не обязательно тот, что был внесён последним).
|
(а) |
(б) |
Рис. 3
На Рис. 4 показано внесение ключа «53» в терминальную некорневую страницу (случай L ≥ 2). Ключ переполняет страницу (часть «а»). При перестроении дерева происходит нечто похожее на то, что рассмотрено на Рис. 3, но новая страница – только одна.
Порядок перестроения дерева таков.
В переполненном списке (содержащем 2∙n + 1 ключей) выбирается один средний элемент («49»), левая половина списка (n ключей, «41», «45»), правая половина списка (n ключей, «50», «53»). Средний элемент списка «всплывает» в родительскую (по отношению к переполненной) страницу и занимает там место (вставляется) в порядке сортировки по возрастанию. При этом «пододвигаемые» вправо ключи («60») смещаются вместе со своими правыми ссылками, что порождает одну «вакантную» ссылку справа от «всплывшего» ключа.
В переполненной странице сохраняется только левая половина списка «41», «45»). Создаётся новая страница (показана синим цветом) и заполняется правой половиной списка («50», «53»). «Вакантная» ссылка (зелёного цвета, как и «всплывший» ключ) нацеливается на созданную новую страницу. Переполнение устранено (часть «б»).
|
(а) |
(б) |
Рис. 4
Важно отметить, что «всплытие» ключа в родительскую страницу может повлечь и её переполнение. Обработкой этого переполнения (по уже названному алгоритму) занимается (L – 1) – й экземпляр процедуры IncludeKey. Возможна длинная цепь таких переполнений, иногда и вплоть до корневой страницы.
Исключение ключа из Б-дерева
Процедура исключения будет иметь имя ExcludeKey. Место удаляемого ключа отыскивается так же, как и в двоичном дереве поиска. После удаления возможна ситуация, при которой на странице остаётся менее n ключей. Такая ситуация далее, для краткости, будет называться «недобором».
Исключение из терминальной страницы
Если терминальная вершина имеет уровень L, то удалением ключа занимается L – й экземпляр процедуры ExcludeKey, вызываемый рекурсивно.
На Рис. 5, 6 показаны «лёгкий» и «трудный» случаи удаления ключа «49».
Из ключей «похудевшей» страницы и её ближайшей сестры (если не старшей, как на Рис. 5, 6, то младшей) формируется «длинный» список (на частях «б» показан светло-зелёным цветом). В него, в порядке сортировки, вносится тот ключ из родительской страницы, для которого две обсуждаемые сестры являются левым и правым потомками («40»). Пусть m есть длина полученного списка. Ясно, что m ≤ 4∙n.
Выбирается срединный элемент списка («37»)
Пусть m ≥ 2∙n + 1 (Рис. 5). Выбирается срединный элемент длинного списка («37»), он становится на место «бывшей главы» в родительскую страницу («40»). Левая («31, 34, 35») и правая («41, 41, 45») половины списка расставляются в страницы-сёстры, участвующие в дележе. Каждой достаётся не менее n ключей.
|
(а) |
(б) |
(в) |
Рис. 5
Пусть m ≤ 2∙n (Рис. 6). В действительности, это означает, что m = 2∙n. Длинный список («31, 34, 40, 41») помещается в старшую (левую) из участвующих в процессе страниц-сестёр. Младшая (правая) страница удаляется. «Бывшая глава» двух сестёр в родительской странице («40», часть «а») удаляется, при этом ключи, расположенные правее, сдвигаются влево вместе со своими правыми ссылками, а ссылка на удалённую страницу исчезает.
|
|
||
|
(а) |
(б) |
(в) |
Рис. 6
Важно отметить, что удалением ключа из родительской страницы и обработкой возможного случая недобора занимается (L – 1) – й экземпляр процедуры ExcludeKey. При этом L – й экземпляр процедуры даёт лишь информацию процедуре-предку о необходимости удаления.
Исключение из нетерминальной страницы
Этот случай несколько сложнее (Рис. 7). Идея решения состоит в том, чтобы обменять удаляемый ключ («31») местами с самым правым из его левых потомков («27»). После этого удаляемый ключ встанет на терминальную страницу, процесс удаления с которой уже изучен.
Казалось бы, плохо, что Б-дерево после такого обмена перестаёт быть деревом поиска (часть «б», Рис. 7). Но после ликвидации целевого ключа («31») дерево вновь становится Б-деревом поиска.
Рис. 7 (а)
Рис. 7 (б)
Фрагменты кода
const
nKnot = 2; // Минимальное число ключей на странице
type
MyRecord = record
// Тип записи для компоненты файла дерева
nData: integer;
mData: array[1 .. 2 * nKnot + 1] of integer;
mLink: array[0 .. 2 * nKnot + 1] of longint;
end;
MyRecordLong = record
// Тип записи для слияния двух компонент в одну
nData: integer;
mData: array[1 .. 4 * nKnot] of integer;
mLink: array[0 .. 4 * nKnot] of longint;
end;
procedure IncludeKey(sFind: integer;
var lStartPage: longint;
var sUp: integer;
var lUp: longint);
// sUp - ключ, который должен подняться вверх
// lUp - ссылка с того ключа, который должен подняться вверх
// lUp - номер новой страницы, если старая разделилась на две
var
R, RAux: MyRecord;
i, iL, iR: integer;
bTerminal: boolean;
procedure ClearPage;
var
i: integer;
begin
R.nData := 0;
for i := 1 to 2 * nNode + 1 do
begin
R.mData[i] := -1;
R.mLink[i] := -1;
end;
R.mLink[0] := -1;
end;
procedure InsertItem(iNew: Integer;
sNew: string; lNew: longint);
var
i: integer;
begin
for i := R.nData downto iNew do
begin
R.mData[i + 1] := R.mData[i];
R.mLink[i + 1] := R.mLink[i];
end;
R.mData[iNew] := sNew;
R.mLink[iNew] := lNew;
Inc(R.nData);
if R.nData > 2 * nNode then
// => R.nData = 2 * nNode + 1
begin
for i := 1 to nNode do
begin
RAux.mData[i] := R.mData[i + nNode + 1];
RAux.mLink[i] := R.mLink[i + nNode + 1];
end;
RAux.mLink[0] := R.mLink[nNode + 1];
R.nData := nNode;
RAux.nData := nNode;
sUp := R.mData[nNode + 1];
for i := nNode + 1 to 2 * nNode + 1 do
begin
R.mData[i] := -1;
R.mLink[i] := -1;
RAux.mData[i] := -1;
RAux.mLink[i] := -1;
end;
if lStartPage = 0 then
begin
lUp := FileSize(F);
SeekAndWrite(lUp, R);
ClearPage;
R.nData := 1;
R.mData[1] := sUp;
R.mLink[0] := lUp;
lUp := FileSize(F);
SeekAndWrite(lUp, RAux);
R.mLink[1] := lUp;
sUp := -1;
lUp := -1;
end
else
begin
lUp := FileSize(F);
SeekAndWrite(lUp, RAux);
end;
end
else
begin
sUp := -1;
lUp := -1;
end;
SeekAndWrite(lStartPage, R);
end;
begin
if FileSize(F) < 1 then
begin
ClearPage;
InsertItem(1, sFind, -1);
SeekAndWrite(0, R);
Exit;
end;
SeekAndRead(lStartPage, R);
if R.mLink[0] < 0 then bTerminal := True else bTerminal := False;
// Других потомков тоже нет
iR := StringCompare(sFind, R.mData[1]);
if iR = 0 then
begin
nRFound := lStartPage;
nDFound := 1;
Exit;
end;
if iR < 0 then
begin
if bTerminal then
begin
InsertItem(1, sFind, -1);
end
else
begin
IncludeKey(sFind, R.mLink[0], sUp, lUp);
if lUp > -1 then
InsertItem(1, sUp, lUp);
end;
Exit;
end;
iR := StringCompare(sFind, R.mData[R.nData]);
if iR = 0 then
begin
nRFound := lStartPage;
nDFound := R.nData;
Exit;
end;
if iR > 0 then
begin
if bTerminal then
InsertItem(R.nData + 1, sFind, -1)
else
begin
IncludeKey(sFind, R.mLink[R.nData], sUp, lUp);
if lUp > -1 then
InsertItem(R.nData + 1, sUp, lUp);
end;
Exit;
end;
for i := 1 to R.nData do
begin
iL := iR;
if iL = 0 then
begin
nRFound := lStartPage;
nDFound := i;
// Это глобальные переменные.
// Нужны для показа места найденного ключа.
Exit;
end;
if i = R.nData then Break;
iR := StringCompare(sFind, R.mData[i + 1]);
if iR < 0 then
// iL > 0, раз сюда попали и не выскочили по iL = 0.
begin
if bTerminal then
InsertItem(i + 1, sFind, -1)
else
begin
IncludeKey(sFind, R.mLink[i], sUp, lUp);
if lUp > -1 then
InsertItem(i + 1, sUp, lUp);
end;
Exit;
end;
end;
end;
procedure ExcludeKey(sFind: integer; iLevel: integer;
var lStartPage: longint;
var bBecameTooFew: boolean);
// bBecameTooFew = True =>
// на ДАННОЙ странице стало слишком мало ключей ( < nNode)
var
R, RAux: MyRecord;
i, j, iR, iDownRight, nDownRight: integer;
lRightest: longint;
mDownRight: array of longint;
sAux: MyString;
procedure RemoveItem(iRemove: integer);
var
i: integer;
begin
for i := iRemove to 2 * nNode do
begin
R.mData[i] := R.mData[i + 1];
R.mLink[i] := R.mLink[i + 1];
end;
Dec(R.nData);
if iLevel = 1 then // < 1 не бывает!
bBecameTooFew := (R.nData < 1)
else
bBecameTooFew := (R.nData < nNode);
end;
procedure MergeTwoPages(iLeft: integer;
var sHead: MyString);
var
i, i1, i2, j, k: integer;
R0: MyRecordAux;
lDied: longint;
begin
j := 0;
lDied := -1;
SeekAndRead(R.mLink[iLeft], RAux);
i1 := RAux.nData;
R0.mLink[0] := RAux.mLink[0];
for i := 1 to i1 do
begin
Inc(j);
R0.mData[j] := RAux.mData[i];
R0.mLink[j] := RAux.mLink[i];
end;
SeekAndRead(R.mLink[iLeft + 1], RAux);
i2 := RAux.nData;
Inc(j);
R0.mData[j] := sHead;
R0.mLink[j] := RAux.mLink[0];
for i := 1 to i2 do
begin
Inc(j);
R0.mData[j] := RAux.mData[i];
R0.mLink[j] := RAux.mLink[i];
end;
// Итак, две соседние страницы, на которые указывали ссылки
// R.mLink[iLeft] и R.mLink[iLeft + 1],
// временно слили в одну "длинную" страницу R0.
// А далее будет решено, действительно ли состоится слияние В ФАЙЛЕ,
// или же страница R0 просто "поровну" раздаст ключи
// между страницами, на которые указывали ссылки
// R.mLink[iLeft] и R.mLink[iLeft + 1].
// j - кол-во ключей в R0.
if j <= 2 * nNode then
begin
bBecameTooFew := True;
// Слияние состоится.
sHead := -1;
RAux.mLink[0] := R0.mLink[0];
RAux.nData := j;
for i := 1 to j do
begin
RAux.mData[i] := R0.mData[i];
RAux.mLink[i] := R0.mLink[i];
end;
SeekAndWrite(R.mLink[iLeft], RAux);
lDied := R.mLink[iLeft + 1];
SeekAndRead(lDied, RAux);
RAux.nData := 0;
SeekAndWrite(lDied, RAux);
// Компонент с номером lDied погиб???
end
else
begin
bBecameTooFew := False;
// Слияния не будет. Будет раздача поровну.
k := (i1 + i2 + 1) div 2;
RAux.mLink[0] := R0.mLink[0];
for i := 1 to k do
begin
RAux.mData[i] := R0.mData[i];
RAux.mLink[i] := R0.mLink[i];
end;
RAux.nData := k;
SeekAndWrite(R.mLink[iLeft], RAux);
j := k + 1;
sHead := R0.mData[j];
RAux.mLink[0] := R0.mLink[j];
i := 0;
while j < i1 + i2 + 1 do
begin
Inc(i);
Inc(j);
RAux.mData[i] := R0.mData[j];
RAux.mLink[i] := R0.mLink[j];
end;
RAux.nData := i;
SeekAndWrite(R.mLink[iLeft + 1], RAux);
end;
if bBecameTooFew then
RemoveItem(iLeft + 1);
// ВАЖНО!
// ДО вызова процедуры RemoveItem
// переменная bBecameTooFew = True,
// если слияние страниц, подчинённых записи R, состоялось,
// bBecameTooFew = False, если не было слияния.
// ПОСЛЕ вызова процедуры RemoveItem
// переменная bBecameTooFew = True,
// если на САМОЙ записи R (а не на её потомках)
// стало слишком мало ключей,
// bBecameTooFew = False, если ключей достаточно.
if (lStartPage = 0) and bBecameTooFew then
begin
// Единственный ключ на корневой странице удалён.
// Значит, осталась ссылка на единственного потомка.
lDied := R.mLink[0];
SeekAndRead(lDied, RAux);
R := RAux;
// Это важно!
// Только ЗДЕСЬ содержимое стартовой страницы
// заменится содержимым её единственного потомка.
RAux.nData := 0;
SeekAndWrite(lDied, RAux);
// Компонент с номером lDied погиб???
end;
SeekAndWrite(lStartPage, R);
end;
begin
lRightest := FileSize(F);
if lRightest < 1 then
begin
MsgBox('lFS < 1');
Application.Terminate;
Exit;
end;
if lRightest < 1 + lStartPage then
begin
MsgBox('lFS < 1 + lStartPage');
Application.Terminate;
Exit;
end;
SeekAndRead(lStartPage, R);
if R.mLink[0] < 0 then
begin
// Сюда попали => страница терминальная
for i := 1 to R.nData do
begin
iR := StringCompare(sFind, R.mData[i]);
if iR = 0 then
begin
RemoveItem(i);
// ТОЛЬКО ЗДЕСЬ удаляется ключ!
// bBecameTooFew пойдёт к процедуре-предку.
SeekAndWrite(lStartPage, R);
Exit;
end;
end;
MsgBox('Ключ "' + sFind + '" не найден!');
bFound := False;
Exit;
end;
// Сюда попали => страница НЕтерминальная
for i := 1 to R.nData do
begin
iR := StringCompare(sFind, R.mData[i]);
if iR = 0 then
begin
bFound := True;
lRightest := R.mLink[i - 1];
SeekAndRead(lRightest, RAux);
// В RAux - левый потомок ключа R.mData[i].
while RAux.mLink[0] > -1 do
begin
// Движемся к самому правому потомку RAux.
lRightest := RAux.mLink[RAux.nData];
SeekAndRead(lRightest, RAux);
end;
// Напоминаем: надо удалить ключ R.mData[i],
// который находится на НЕтерминальной странице.
sAux := R.mData[i];
R.mData[i] := RAux.mData[RAux.nData];
RAux.mData[RAux.nData] := sAux;
SeekAndWrite(lStartPage, R);
SeekAndWrite(lRightest, RAux);
// А мы вот взяли и обменяли значениями
// ключи R.mData[i] и RAux.mData[RAux.nData].
// Чем это лучше?
// Тем, что теперь надо удалять ключ RAux.mData[RAux.nData]
// из ТЕРМИНАЛЬНОЙ страницы.
// А чем это хуже?
// Тем, что дерево испорчено. Оно теперь НЕ ЕСТЬ дерево поиска.
// Почему?
// Доступ к удаляемому ТЕРМИНАЛЬНОМУ ключу
// возможен только от ЛЕВОЙ ссылки под R.mData[i]
// (а не от правой, как должно быть у дерева поиска).
// Но возможен же! Так что получим этот доступ и удалим.
ExcludeKey(sFind, iLevel + 1, R.mLink[i - 1], bBecameTooFew);
// Всё! Дерево вновь стало нормальным деревом поиска.
if bBecameTooFew then
MergeTwoPages(i - 1, R.mData[i]);
Exit;
end;
end;
for i := 1 to R.nData do
begin
iR := StringCompare(sFind, R.mData[i]);
if iR < 0 then
begin
ExcludeKey(sFind, iLevel + 1, R.mLink[i - 1], bBecameTooFew);
// Это bBecameTooFew пришло СЮДА от дочернего экземпляра ExcludeKey
// и будет использовано ЗДЕСЬ.
if bBecameTooFew then
MergeTwoPages(i - 1, R.mData[i]);
// А вот в MergeTwoPages
// переменная bBecameTooFew может измениться и она, далее,
// будет передана родительскому экземпляру ExcludeKey
Exit;
end;
end;
// Сюда попали =>
// StringCompare(sFind, R.mData[R.nData]) > 0
i := R.nData;
ExcludeKey(sFind, iLevel + 1, R.mLink[i], bBecameTooFew);
if bBecameTooFew then
MergeTwoPages(i - 1, R.mData[i]);
end;