\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