IfiR < 0 then

Begin

IfbTerminal then

Begin

InsertItem(1, sFind, -1);

End

Else

Begin

IncludeKey(sFind, R.mLink[0], sUp, lUp);

IflUp > -1 then

InsertItem(1, sUp, lUp);

end;

Exit;

end;

iR := StringCompare(sFind, R.mData[R.nData]);

ifiR = 0 then

Begin

nRFound := lStartPage;

nDFound := R.nData;

Exit;

end;

IfiR > 0 then

Begin

IfbTerminal then

InsertItem(R.nData + 1, sFind, -1)

Else

Begin

IncludeKey(sFind, R.mLink[R.nData], sUp, lUp);

IflUp > -1 then

InsertItem(R.nData + 1, sUp, lUp);

end;

Exit;

end;

fori := 1 toR.nData do

Begin

iL := iR;

ifiL = 0 then

Begin

nRFound := lStartPage;

nDFound := i;

// Это глобальные переменные.

// Нужны для показа места найденного ключа.

Exit;

end;

ifi = R.nData thenBreak;

iR := StringCompare(sFind, R.mData[i + 1]);

IfiR < 0 then

// iL > 0, раз сюда попали и не выскочили по iL = 0.

Begin

IfbTerminal then

InsertItem(i + 1, sFind, -1)

Else

Begin

IncludeKey(sFind, R.mLink[i], sUp, lUp);

IflUp > -1 then

InsertItem(i + 1, sUp, lUp);

end;

Exit;

end;

end;

end;

procedureExcludeKey(sFind: integer; iLevel: integer;

varlStartPage: longint;

varbBecameTooFew: boolean);

// bBecameTooFew = True =>

// на ДАННОЙ странице стало слишком мало ключей ( < nNode)

Var

R, RAux: MyRecord;

i, j, iR, iDownRight, nDownRight: integer;

lRightest: longint;

mDownRight: array oflongint;

sAux: MyString;

procedureRemoveItem(iRemove: integer);

Var

i: integer;

Begin

fori := iRemove to2 * nNode do

Begin

R.mData[i] := R.mData[i + 1];

R.mLink[i] := R.mLink[i + 1];

end;

Dec(R.nData);

ifiLevel = 1 then// < 1 не бывает!

bBecameTooFew := (R.nData < 1)

Else

bBecameTooFew := (R.nData < nNode);

end;

procedureMergeTwoPages(iLeft: integer;

varsHead: 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];

fori := 1 toi1 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];

fori := 1 toi2 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.

ifj <= 2 * nNode then

Begin

bBecameTooFew := True;

// Слияние состоится.

sHead := -1;

RAux.mLink[0] := R0.mLink[0];

RAux.nData := j;

fori := 1 toj 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];

fori := 1 tok 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;

whilej < 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;