\input style
%% 562
LIONU, IH BUDET PRIMERNO 20. nO ESLI RAZDELITX DEREVO NA "STRANICY" PO 7 
UZLOV V KAZHDOJ, KAK POKAZANO PUNKTIROM NA RIS.~29, I ESLI V KAZHDYJ MOMENT 
VREMENI DOSTUPNA LISHX ODNA STRANICA, TO POTREBUETSYA PRIMERNO V TRI RAZA 
MENXSHE OBRASHCHENIJ, T. E. POISK USKORITSYA V TRI RAZA!

gRUPPIROVKA UZLOV V STRANICY, PO SUSHCHESTVU, PREOBRAZUET BINARNYE DEREVXYA V 
OKTARNYE, RAZVETVLYAYUSHCHIESYA V KAZHDOJ STRANICE-UZLE NA 8 PUTEJ. eSLI 
DOPUSTIMY STRANICY BOLXSHIH RAZMEROV, RAZVETVLYAYUSHCHIESYA NA 128 PUTEJ POSLE 
KAZHDOGO OBRASHCHENIYA K DISKU, TO MOZHNO NAHODITX TREBUEMYJ KLYUCH V TABLICE 
IZ MILLIONA |LEMENTOV, PROSMOTREV LISHX TRI STRANICY. mOZHNO POSTOYANNO 
HRANITX KORNEVUYU STRANICU VO VNUTRENNEJ PAMYATI;
TOGDA POTREBUYUTSYA LISHX DVA OBRASHCHENIYA K DISKU, HOTYA V LYUBOJ MOMENT 
VREMENI VO VNUTRENNEJ PAMYATI BUDET NE BOLEE 254 KLYUCHEJ.

rAZUMEETSYA, NE SLEDUET DELATX STRANICY OCHENX BOLXSHIMI, TAK KAK RAZMERY 
VNUTRENNEJ PAMYATI OGRANICHENY I CHTENIE BOLXSHEJ STRANICY ZANIMAET BOLXSHE 
VREMENI. pREDPOLOZHIM, NAPRIMER, CHTO CHTENIE STRANICY, DOPUSKAYUSHCHEJ 
RAZVETVLENIE NA $m$ PUTEJ, ZANIMAET $72.5+0.05m$ MS. vREMYA NA VNUTRENNYUYU 
OBRABOTKU KAZHDOJ STRANICY SOSTAVIT OKOLO $a+b\log m$ MS, GDE $a$ MALO PO 
SRAVNENIYU S $72.5$, TAK CHTO POLNOE VREMYA, TREBUYUSHCHEESYA NA POISK V BOLXSHOJ 
TABLICE, PRIMERNO PROPORCIONALXNO $\log N$, UMNOZHENNOMU NA
$$
(72.5 + 0.05m)/\log m +b.
$$
eTA VELICHINA DOSTIGAET MINIMUMA PRI $m\approx350$; V DEJSTVITELXNOSTI 
|TOT MINIMUM OCHENX "SHIROK". zNACHENIYA, OCHENX BLIZKIE K OPTIMALXNOMU, 
DOSTIGAYUTSYA PRI $m$ OT~200 DO~500. nA PRAKTIKE POLUCHENIE PODOBNOGO 
DIAPAZONA HOROSHIH ZNACHENIJ $m$ ZAVISIT OT HARAKTERISTIK ISPOLXZUEMYH 
VNESHNIH ZAPOMINAYUSHCHIH USTROJSTV I OT DLINY ZAPISEJ V TABLICE.

u. i. lANDAU|R [{\sl IEE Trans.\/}, {\bf EC-12} (1963), 863--871] 
PREDLOZHIL STROITX $m$-ARNYE DEREVXYA SLEDUYUSHCHIM OBRAZOM: RAZMESHCHATX UZLY 
NA UROVNE $l+1$, LISHX ESLI UROVENX $l$ POCHTI ZAPOLNEN. eTA SHEMA TREBUET 
DOVOLXNO SLOZHNOJ SISTEMY POVOROTOV, TAK KAK DLYA VSTAVKI ODNOGO NOVOGO 
|LEMENTA MOZHET POTREBOVATXSYA OSNOVATELXNAYA PERESTROJKA DEREVA; 
lANDAU|R ISHODIL IZ PREDPOLOZHENIYA, CHTO POISK PRIHODITSYA 
PROIZVODITX GORAZDO CHASHCHE VSTAVOK I UDALENIJ.

eSLI FAJL HRANITSYA NA DISKE I YAVLYAETSYA OB�EKTOM SRAVNITELXNO REDKIH 
VSTAVOK I UDALENIJ, TO DLYA EGO PREDSTAVLENIYA PODHODIT TREHUROVNEVOE 
DEREVO, GDE PERVYJ UROVENX RAZVETVLENIYA OPREDELYAET, KAKOJ CILINDR BUDET 
ISPOLXZOVATXSYA, SLEDUYUSHCHIJ UROVENX RAZVETVLENIYA OPREDELYAET 
SOOTVETSTVUYUSHCHUYU DOROZHKU NA |TOM CILINDRE, A TRETIJ UROVENX SODERZHIT SOBSTVENNO
%% 563
ZAPISI. tAKOJ METOD NAZYVAETSYA \dfn{INDEKSNO-POSLEDOVATELXNOJ} 
ORGANIZACIEJ FAJLA [SR. {\sl JACM\/}, {\bf 16} (1969), 569--571].

r. mYUNC I r. uZGALIS [Proc. Princeton Conf. on Inf. Sciences and Systems, 
4 (1970), 345--349] PREDLOZHILI MODIFIKACIYU ALGORITMA 6.2.2t, GDE VSE 
VSTAVKI POROZHDAYUT UZLY, PRINADLEZHASHCHIE TOJ ZHE STRANICE, CHTO I IH 
PREDSHESTVENNIK (ESLI TOLXKO |TO VOZMOZHNO); ESLI STRANICA POLNOSTXYU ZANYATA, 
ZAVODITSYA NOVAYA STRANICA (ESLI TAKOVAYA IMEETSYA). pRI NEOGRANICHENNOM 
KOLICHESTVE STRANIC I SLUCHAJNOM PORYADKE POSTUPAYUSHCHIH DANNYH SREDNEE 
CHISLO OBRASHCHENIJ, K DISKU, KAK MOZHNO POKAZATX, PRIBLIZHENNO 
RAVNO $H_N/(H_m-1)$, CHTO LISHX NEMNOGIM BOLXSHE CHISLA OBRASHCHENIJ V SLUCHAE 
NAILUCHSHEGO VOZMOZHNOGO $m$-ARNOGO DEREVA (SM. UPR.~10).

\section B-DEREVXYA. v 1970~G. r. b|JER I e. mAK-kR|JT 
[{\sl Acta Informatica\/}, (1972), 173--189] 
I NEZAVISIMO OT NIH PRIMERNO V TO ZHE VREMYA m. kAUFMAN [NEOPUBLIKOVANO] 
PREDLOZHILI NOVYJ PODHOD K VNESHNEMU POISKU POSREDSTVOM SILXNO VETVYASHCHIHSYA 
DEREVXEV. iH IDEYA OSNOVYVAETSYA NA PODVIZHNOSTI NOVOGO TIPA STRUKTUR DANNYH,
 NAZVANNYH \dfn{B-DEREVXYAMI}, I POZVOLYAET PROIZVODITX POISK ILI IZMENYATX 
BOLXSHOJ FAJL S "GARANTIROVANNOJ" |FFEKTIVNOSTXYU V NAIHUDSHEM SLUCHAE, 
ISPOLXZUYA PRI |TOM SRAVNITELXNO PROSTYE ALGORITMY.

\dfn{B-DEREVOM PORYADKA $m$} NAZYVAETSYA DEREVO, OBLADAYUSHCHEE SLEDUYUSHCHIMI SVOJSTVAMI:
\medskip
\item{i)} kAZHDYJ UZEL IMEET NE BOLEE $m$ SYNOVEJ.
\item{ii)} kAZHDYJ UZEL, KROME KORNYA I LISTXEV, IMEET NE MENEE
$m/2$ SYNOVEJ.
\item{iii)} kORENX, ESLI ON NE LIST, IMEET NE MENEE 2 SYNOVEJ.
\item{iv)} vSE LISTXYA RASPOLOZHENY NA ODNOM UROVNE I NE SODERZHAT
INFORMACII.
\item{v)} nELISTOVOJ UZEL S $k$ SYNOVXYAMI SODERZHIT $k-1$ KLYUCHEJ.
\medskip
\noindent (kAK I OBYCHNO, LIST---KONCEVOJ UZEL, U NEGO NET PREEMNIKOV. tAK 
KAK LISTXYA NE SODERZHAT INFORMACII, IH MOZHNO RASSMATRIVATX KAK VNESHNIE 
UZLY, KOTORYH V DEJSTVITELXNOSTI NET V DEREVE, TAK CHTO $\NULL$---|TO 
UKAZATELX NA LIST.)

nA RIS.~30 POKAZANO B-DEREVO PORYADKA 7. kAZHDYJ UZEL (KROME KORNYA I 
LISTXEV) IMEET OT~$\lceil 7/2\rceil$ DO~7 PREEMNIKOV I SODERZHIT 3, 4, 5 
ILI 6 KLYUCHEJ. kORNEVOJ UZEL MOZHET SODERZHATX OT~1 DO~6 KLYUCHEJ (V DANNOM 
SLUCHAE 2). vSE LISTXYA NAHODYATSYA NA TRETXEM UROVNE. zAMETXTE, CHTO (a) 
KLYUCHI RASPOLOZHENY V VOZRASTAYUSHCHEM PORYADKE SLEVA NAPRAVO, ESLI 
ISPOLXZOVATX ESTESTVENNOE OBOBSHCHENIE PONYATIYA SIMMETRICHNOGO PORYADKA, I 
(b) KOLICHESTVO LISTXEV ROVNO NA EDINICU BOLXSHE KOLICHESTVA KLYUCHEJ.

B-DEREVXYA PORYADKA 1 I~2, OCHEVIDNO, NEINTERESNY; PO|TOMU MY RASSMOTRIM LISHX 
SLUCHAJ $m\ge 3$. zAMETXTE, CHTO (3-2)-DEREVXYA,
%% 564
\picture{rIS. 30. B-DEREVO PORYADKA 7}
%% 565
OPREDELENNYE V KONCE P.~6.2.3, YAVLYAYUTSYA B-DEREVXYAMI PORYADKA 3;
I OBRATNO, B-DEREVO PORYADKA 3 ESTX (3-2)-DEREVO.

uZEL, SODERZHASHCHIJ $j$ KLYUCHEJ I $j+1$ UKAZATELEJ, MOZHNO PREDSTAVITX V VIDE
\picture{uZEL B-DEREVA}
GDE $K_1<K_2<\ldots <K_j$, A $P_i$ UKAZYVAET NA PODDEREVO KLYUCHEJ, BOLXSHIH 
$K_i$ I MENXSHIH $K_{i+1}$. sLEDOVATELXNO, POISK V B-DEREVE ABSOLYUTNO 
PRYAMOLINEEN: POSLE TOGO KAK UZEL (1) RAZMESHCHEN VO VNUTRENNEJ PAMYATI, MY 
ISHCHEM DANNYJ ARGUMENT SREDI KLYUCHEJ $K_1$, $K_2$, \dots, $K_j$. (pRI BOLXSHIH 
$j$, VEROYATNO, PROIZVODITSYA BINARNYJ POISK, A PRI MALYH $j$ NAILUCHSHIM 
BUDET POSLEDOVATELXNYJ POISK.) eSLI POISK UDACHEN, NUZHNYJ KLYUCH NAJDEN; 
ESLI POISK NEUDACHEN V SILU TOGO, CHTO ARGUMENT LEZHIT MEZHDU $K_i$,
 I~$K_{i+1}$, MY "PODKACHIVAEM" (VYZYVAEM V OPERATIVNUYU PAMYATX) UZEL, 
UKAZANNYJ $P_i$, I PRODOLZHAEM PROCESS. uKAZATELX $P_0$ ISPOLXZUETSYA, 
ESLI ARGUMENT MENXSHE $K_1$, a $P_j$ ISPOLXZUETSYA, ESLI ARGUMENT BOLXSHE 
$K_j$. pRI $P_i=\NULL$ POISK NEUDACHEN.

pRIVLEKATELXNOJ CHERTOJ B-DEREVXEV YAVLYAETSYA ISKLYUCHITELXNAYA PROSTOTA, S 
KOTOROJ PROIZVODYATSYA VSTAVKI. rASSMOTRIM, NAPRIMER, RIS.~30; KAZHDYJ LIST 
SOOTVETSTVUET MESTU VOZMOZHNOJ VSTAVKI. eSLI NUZHNO VSTAVITX NOVYJ KLYUCH 
$337$, MY PROSTO MENYAEM UZEL
\picture{vSTAVKA V B-DEREVO}
s DRUGOJ STORONY, PRI POPYTKE VSTAVITX NOVYJ KLYUCH $071$ MY OBNARUZHIVAEM, 
CHTO V SOOTVETSTVUYUSHCHEM UZLE UROVNYA 2 NET MESTA---ON UZHE "POLON". eTU 
TRUDNOSTX MOZHNO PREODOLETX, RASSHCHEPIV UZEL NA DVE CHASTI PO TRI KLYUCHA V 
KAZHDOJ I PODNYAV SREDNIJ KLYUCH NA UROVENX 1:
\picture{rASSHCHEPLENIE UZLA PRI VSTAVKE}
%% 566 

vOOBSHCHE, ESLI NUZHNO VSTAVITX NOVYJ |LEMENT V B-DEREVO PORYADKA $m$, VSE 
LISTXYA KOTOROGO RASPOLOZHENY NA UROVNE $l$, NOVYJ KLYUCH VSTAVLYAYUT V 
PODHODYASHCHIJ UZEL UROVNYA $l-1$. eSLI UZEL TEPERX SODERZHIT $m$ KLYUCHEJ, T. E. 
IMEET VID (1) S $j=m$, EGO RASSHCHEPLYAYUT NA DVA UZLA
\picture{rASSHCHEPLENIE UZLA: OBSHCHIJ VID}
I VSTAVLYAYUT KLYUCH $K_{\lceil m/2\rceil}$ V UZEL-OTEC. (tAKIM OBRAZOM, 
UKAZATELX $P$ V NEM ZAMENYAETSYA POSLEDOVATELXNOSTXYU $P$, $K_{\lceil 
m/2\rceil}$, $P'$.) eTA VSTAVKA V SVOYU OCHEREDX MOZHET PRIVESTI K 
RASSHCHEPLENIYU UZLA-OTCA. (sR. S RIS.~27, GDE IZOBRAZHEN SLUCHAJ $m=3$.) 
eSLI NUZHNO RASSHCHEPITX KORNEVOJ UZEL, KOTORYJ NE IMEET OTCA, TO PROSTO 
SOZDAYUT NOVYJ KORENX I POMESHCHAYUT V NEGO EDINSTVENNYJ KLYUCH $K_{\lceil 
m/2\rceil}$, V TAKOM SLUCHAE DEREVO STANOVITSYA NA EDINICU VYSHE.

oPISANNAYA PROCEDURA VSTAVKI SOHRANYAET VSE SVOJSTVA B-DEREVXEV; CHTOBY 
OCENITX VSYU KRASOTU IDEI, CHITATELX DOLZHEN VYPOLNITX UPR.~1. zAMETXTE, 
CHTO DEREVO MALO-POMALU RASTET VVERH OT VERHNEJ CHASTI, A NE VNIZ OT NIZHNEJ 
CHASTI, TAK KAK EDINSTVENNAYA PRICHINA, SPOSOBNAYA VYZVATX ROST 
DEREVA,---RASSHCHEPLENIE KORNYA.

uDALENIYA IZ B-DEREVXEV LISHX NEMNOGIM SLOZHNEE VSTAVOK (SM. UPR.~7).

\section gARANTIROVANNAYA |FFEKTIVNOSTX. rASSMOTRIM, K SKOLXKIM UZLAM BUDET 
PROISHODITX OBRASHCHENIE V NAIHUDSHEM SLUCHAE PRI POISKE V B-DEREVE PORYADKA 
$m$. pREDPOLOZHIM, CHTO IMEETSYA $N$ KLYUCHEJ, A NA UROVNE $l$ RASPOLOZHENO 
$N+1$ LISTXEV. tOGDA CHISLO UZLOV NA UROVNYAH 1, 2, 3, \dots NE MENEE 2, 
$2\lceil m/2\rceil$,  $2\lceil m/2\rceil^2$, \dots; SLEDOVATELXNO,
$$
N+1\ge 2\lceil m/2\rceil^{l-1}.
\eqno (5)
$$

iNYMI SLOVAMI,
$$
l\le 1+\log_{\lceil m/2\rceil}\left({N+1\over2}\right);
\eqno(6)
$$
|TO OZNACHAET, NAPRIMER, CHTO PRI $N=1999998$ I $m=199$ IMEEM $l \le  3$. 
tAK KAK PRI POISKE PROISHODIT OBRASHCHENIE SAMOE BOLXSHEE K $l$ UZLAM, |TA 
FORMULA GARANTIRUET MALOE VREMYA RABOTY ALGORITMA.

pRI VSTAVKE NOVOGO KLYUCHA MOZHET PONADOBITXSYA RASSHCHEPITX $l$ UZLOV. oDNAKO 
SREDNEE CHISLO RASSHCHEPLYAEMYH UZLOV MNOGO MENXSHE, TAK KAK OBSHCHEE KOLICHESTVO 
RASSHCHEPLENIJ PRI POSTROENII DEREVA ROVNO NA EDINICU MENXSHE KOLICHESTVA 
UZLOV, KOTOROE MY OBOZNACHIM CHEREZ $p$. v DEREVE NE MENEE 
$1 + (\lceil m/2\rceil-1) (p-1)$

\bye