B+ stromy, tries

Hierarchicke indexy, B / B+ stromy, tries

PV 062 Organizace souboru Jan Staudek http://www. .muni.cz/usr/staudek/vyuka/

}

w A| y < 5 4 23 1 0 / -. , )+ ( %&' $ # !"

Æ

Verze : jaro 2017

Osnova predna sky Vyklad pokrocile technologicke baze pouzvane pro indexovan zaznam u v souboru 2 Grafy, stromova grafova struktura, vyhledavac strom 2 B stromy 2 B+ stromy 2 tries Bazov a technologie indexovan zaznam u souboru na vnejs pameti linearn indexy, tj. tabulky, resp. hierarchie tabulek, nebyv a vzdy efektivn. Cl { bez ohledu na rozsah souboru vyresit dotaz nekolika malo operacemi bez aplikace hasovan Jan Staudek, FI MU Brno

|

PV062 Organizace souboru { Hierarchicke indexy, B+ / B stromy

1

Indexy na bazi vyhledavac ch stromu 2

Indexovan { mechanismus pro r esen odpovedi na dotaz zjist'ujc hodnotu zaznamu, jehoz klc vyhovuje zadane podmnce X mechanismus {

sekundarn soubor ve schematu organizace souboru { linearn index { tabulka { hierarchicky index indexsekvencn organizace { index na bazi vyhledavac ho stromu 2

2

linearn index je pro vnejs pameti nefektivn byv a staticky, byv a rozsahl y hierarchicky index indexsekvencn organizace je v podstate rovnez staticky Jan Staudek, FI MU Brno

|


2

Indexy na bazi vyhledavac ch stromu 2 2 2

2

indexy na bazi vyhledavac ch stromu jsou alternativn organizac vu ci index-sekvencn organizaci souboru, obe organizace zefektivnuj r esen dotazu nad souborem obe organizace podporuj r esen dotazu pro prpad jedineho dotazovacho klc e udrzovan m sekundarn ho souboru { indexu ALE . . .

Jan Staudek, FI MU Brno

|


3

Problem doby prohledav an rozsahl ych indexu X

lze r esit vceurov nov ymi indexy, sni zuje se pocet pot rebnych diskovych p r stupu { 3x pro index (4. urove n je v RAM), 1x pro data { sekundarn data zabraj 10 % pameti, vynikajc zisk

X

Kdy z se do indexu vlo z nejmens klc ze vsech klc u a indexove bloky jsou plne, p redel av a se uspo rad an 888 000 indexovych bloku { nep rijatelna cena


|


4

Negativa rozsahl e / staticke indexove struktury 2

staticky index X X X X

2

velmi neefektivn pro dynamicke soubory, reorganizace indexu jsou c asove naro cne, behem reorganizace nejsou data dostupna reorganizace se mus delat ,,mimo pracovn dobu" { nevhodne pro provoz 24x7 (rezervace letenek, bankomaty)

co delat, kdyz index je prlis rozsahl y ? X nelze jej umstit do RAM X disk je pomaly na sekvencn prohledav an linearn ho indexu X r esenm je napr. vceurov novost indexu

{ velmi neefektivn pro dynamicke soubory


|


5

Proc nestac index-sekvencn organizace ? 2

indexy na bazi vyhledavac ch stromu r es zakladn nedostatky index-sekvencn organizace souboru X jej vyhledavac vykon klesa s (velkym) rustem souboru,

{ vytva r se mnoho pretokovych bloku { mus se periodicky provad et rezijne nakladn a reorganizace souboru X klesa jej efektivita vyuzvan pridelene pameti pri rusen zaznam u souboru


|


6

Indexy na bazi (vyhledavac ch) B stromu 2

Prednost organizac souboru s indexem na bazi B stromu X B-strom je vyva zena stromova struktura, vetve maj shodnou delku X sekundarn soubor s indexem se pri vklad an a rusen zaznam u

reorganizuje pomoc malych lokaln ch zmen v grafove strukture, X pro udrzen vykonu nen potreba reorganizovat primarn soubor { soubor primarn ch dat nen potreba usporad avat 2

S iroce se pouzvaj v mnoha aplikacch X B strom je standardn metoda organizace indexu v baz ch dat X Existuje vce verz B stromu, v praxi jsou pro velke soubory nejrozsr enejs B + stromy X Adresa re systemu NTFS jsou budovane na bazi B + stromu


|


7

Indexy na bazi (vyhledavac ch) B stromu 2

Prednosti indexu budovanych na bazi B stromu prevazuj nad jejich nedostatky X vyss prostorova rezie { ale index se pamatuje na vnejs pameti X dodatecna c asova rezie zpusobovan a s tepenm a svlev an m uzlu grafu


|


8

Grafy, pripomenut zakladn ch pojmu 2

Graf G = (V, E) X V { konecna neprazdn a mnozina uzlu a X E { mnozina hrana propojujcch uzly z V

2

hrana, orientovana hrana, orientovany graf (digraph) X X X X

2

dvojice (v, w), kde v a w jsou prvky V reprezentace vztahu (relace) mezi dvojic objektu (uzlu) orientovana hrana { usporadan a dvojice uzlu (v, w) orientovany graf { graf s orientovanymi hranami

neorientovany graf X zvla stn prpad orientovaneho grafu X ke kazde orientovane hrane (v, w) existuje i hrana (w, v)

{ take tzv. oboustranne orientovana hrana { (v, w) a (w, v) je ta z (neorientovana) hrana, { porad uzlu propojenych neorientovanou hranou je irelevantn Jan Staudek, FI MU Brno

|


9


sousedn uzly X v je sousedn s w, kdyz v grafu existuje hrana (v, w)

2

Stupen uzlu (degree)

2

arita, vystupn stupen

2

paraleln hrany

X pocet hran, ktere s uzlem inciduj X U orientovanych grafu lze rozlisovat vstupn stupen (indegree) a vystupn stupen (outdegree). X Vstupn stupen = pocet hran, ktere jsou orientovany smerem do uzlu, X Vystupn stupen = pocet hran, ktere jsou orientovany smerem z uzlu. X pocet vystupujcch hran z uzlu X binarn graf (2 vystupujc hrany), . . . , m-arn (m vystupujcch hran) X hrany zacnajc a koncc ve shodnych uzlech Jan Staudek, FI MU Brno

|


10


cesta X posloupnost uzlu, mezi kterymi vede posloupnost hran X delka cesty = pocet hran, ktere cesta obsahuje,

tj. pocet uzlu takove posloupnosti { 1

2

cyklus X cesta, ktera zacna a konc ve stejnem uzlu

2

smycka X cyklus tvoreny jedinou hranou, ktera zacna a konc v tomte z uzlu X Smycka zvysuje stupen uzlu o dve

2

jednoducha cesta X z adn y z uzlu na ceste se neopakuje Jan Staudek, FI MU Brno

|


11


Ohodnoceny graf X hrana { reprezentace vztahu mezi uzly X vaha, ohodnocen hrany { kvantitavn ohodnocen vztahu

2

Souvisly graf X graf, v nemz plat, z e pro kazde jeho dva vrcholy x, y existuje alespon jedna cesta z x do y

2

Acyklicky graf X z adn a cesta v acyklickem grafu nen cyklem

2

Jednoduchy graf X orientovany acyklicky graf, DAG, Directed Acyclic Graph X graf neobsahujc cykly, smycky a nasobn e (paraleln) hrany Jan Staudek, FI MU Brno

|


12


strom X neorientovany souvisly acyklicky graf, X X X X

stromem se nazyvaj souvisle grafy, ktere neobsahuj cykly odebran m jedne hrany ve stromu je porusena souvislost pridan m jedne hrany vznikne cyklus Strom je minimaln souvisly graf na danych vrcholech. Pro stromy plat, z e pocet hran je o jedna mens nez poctu uzlu.


|


13


korenovy strom X Korenovy strom je orientovany strom, jehoz uzly maj vstupn X X X X X X X X

stupen roven jedne az na jeden uzel, ktery ho ma roven nule. Tento specialn uzel se nazyv a koren (root). korenovy strom je hierarchicka nelinearn struktura pokud nerekneme jinak, chapeme pod pojmem strom pojem korenovy strom uzly na kazde ceste jsou r azeny do vztahu typu rodic-potomek { z rodice vede hrana (cesta) k potomkovi kazdy potomek ma prav e jednoho rodice ex. jeden vyzna cny vrchol { koren, o kterem plat, z e je jedinym uzlem v grafu bez rodice (ve stromu se nachaz prav e jeden koren) uzel stromu bez potomka je listem, resp. vnejsm nebo take koncovym uzlem uzel stromu, ktery ma alespon 1 potomka a nen korenem, je vnitrnm uzlem cesta z korene do listu se nazyv a vetev stromu Jan Staudek, FI MU Brno

|


14


podgraf H = (VH , EH ) grafu G = (VG, EG) X VH je podmnozinou VG a EH je podmnozinou EG

2

kostra grafu G X podgraf H grafu G, ktery je strom a plat VH = VG

2

podstrom X c ast stromu tvorena jednm uzlem (korenem podstromu)

a vsemi jeho potomky X mu ze byt chap an jako kompletn strom sam o sobe X kazdy uzel ve stromu mu ze tvorit koren podstromu


|


15

Strom


|


16

Charakteristiky stromu 2

hloubka uzlu ve stromu: hu = 0, 1, . . . X delka cesty vedouc od korene stromu k uzlu X hloubka korene = 0 X hloubka prmeho potomka korene = 1, . . .

2

urove n ve stromu X mnozina uzlu stromu se stejnou hloubkou uzlu hu X koren je na urovni 0 X kazda urove n d obsahuje nejvy se kd uzlu, kde k je arita stromu { v binarn m stromu ma kazda urove n obsahuje nejvy se 2d uzlu


|


17


hloubka stromu: K = 1, 2, . . . , n X pocet urovn stromu X hloubka nejvzdalen ejsho listu od korene + 1

2

S r ka stromu na jiste urovni X pocet uzlu na stejne urovni


|


18


Vy ska stromu: h = K − 1 X maximaln hloubka uzlu ve stromu X vy ska stromu pouze s korenem je 0 X Strom ma nejmens moznou vy sku prav e tehdy, kdyz na vsech

urovn ch krome posledn ma plny (maximaln e mozny) pocet uzlu X Pri sestavovan strom je mnohdy dule zite sestavovat stromy s nejmens moznou vy skou, protoze tm se zajist minimaln delky cest k uzlum (zvla ste k listum)


|


19


Vyva zeny strom X vyvazovan { rovnomerne rozklad an uzlu v urovn ch X cl vyva zen:

{ v kazde urovni krome posledn, ma maximaln e mozny pocet uzlu, ({ a v posledn urovni ma uzly co nejvce vlevo) X ma nejmens moznou vy sku pri dane arite a danem poctu uzlu 2

Usporadan y strom X strom, ve kterem jsou vsichni prm potomci kazdeho uzlu serazeni X pokud uzel ma n prmych potomku, lze urcit

prvnho prmeho potomka, druheho prmeho potomka, az n-teho prmeho potomka

2

Neusporadan y strom X strom v c iste strukturaln m smyslu X pro dany uzel nejsou jeho prm potomci usporadan Jan Staudek, FI MU Brno

|


20

Binarn strom 2

2

konecna mnozina uzlu, ktera je bud'to prazdn a nebo obsahuje koren a dva disjunktn binarn (pod)stromy { levy podstrom a pravy podstrom pocet uzlu n upln eho binarn ho stromu o K urovn ch (vy sce h) n=

h X

2i =

i=0

2

K−1 X

2i

i=0

opacna uloha { pocet urovn K binarn ho stromu o n uzlech X je-li vyva zeny pak Kmin = dlog2(n + 1)e , dale plat Kmax = n Kmin n

1 2 3 4

1 2, 3 4, 5, 6, 7 8, 9, 10, 11, 12, 13, 14, 15 Jan Staudek, FI MU Brno

|


21

Binarn strom


|


22

Binarn stromy


|


23

Binarn strom


|


24

Binarn stromy, prklady aplikac

2

stromy vyraz u X data (operandy, operatory) obsahuj jak vnitrn uzly tak i vnejs uzly

i koren


|


25


2

strom Humanova kodov an X data (kodov a slova) reprezentuj pouze vnejs uzly X hrany jsou systematicky ohodnoceny 0 a 1 X binarn kod kazdeho listu je dan r etezem ohodnocen hran

na ceste z korenu do daneho listu


|


26


2

binarn vyhledavac strom, BVS, v roli indexu X typicky se jedna se o redundantn BVS {

nektere klc e se vyskytuj jak ve vnitrnm uzlu tak i v listu X koren a vnitrn uzly hraj roli navigator u k listum { zaznam um X data (ukazatele na data) obsahuj pouze vnejs uzly, listy X v korenu a ve vnitrnch uzlech je obsazeny klc , + prpadne nejaka dals data Jan Staudek, FI MU Brno

|


27

Binarn stromy, prklady aplikac (pokrac.)

2

Napr. implementace slovnku pomoc redundantnho BVS

X (ukazatele na) hesla, pojmy (zaznamy) jsou ulozeny ve vnejsch uzlech X BVS pln funkci indexu slovnku, klc e jsou v BVS usporadan e: { klc e v levem podstromu jsou ≤ klc v korenu podstromu a

{ klc v korenu podstromu je mens nez klc e v pravem podstromu X uvedeny prklad indexu slovnku ma 4 urovn e, vy sku 3, 3 vnitrn uzly a koren a 5 vnejsch uzlu X jedna se o prklad ,,redundantnho"BVS, tzv. hranicn klc e jsou uvedeny jak v korenu a ve vnitrnch uzlech, tak i ve vnejsch uzlech Jan Staudek, FI MU Brno

|


28

Binarn vyhledavac strom, BVS 2

uzly jsou usporad any tak, aby bylo mozne rychle vyhledavat danou hodnotu reprezentovanou uzlem { klc X X X X

2

Kazdemu uzlu je prirazen urcity klc Podle hodnot techto klc u jsou uzly usporad any Levy podstrom uzlu obsahuje pouze klc e mens nez je klc tohoto uzlu Pravy podstrom uzlu obsahuje pouze klc e vets nez je klc tohoto uzlu

Vyhledav an v BVS X Zacna zpravidla v koreni X V kazdem kroku se porovna hledana hodnota { klc X X X X

s klc em zkoumaneho uzlu Pokud jsou si rovny, hodnota byla nalezena Je-li hledana hodnota mens, pokracuje hledan v levem podstromu Je-li hledana hodnota vets, pokracuje hledan v pravem podstromu Kdyz vyhledavac algoritmus naraz na neexistujc uzel (dotycny podstrom je prazdn y) strom hledanou hodnotu neobsahuje Jan Staudek, FI MU Brno

|


29

Problem vyva zen BVS 2 2

uvazme neredundatn BVS nejhors doba vyhledav an v upln em vy skove vyva zenem stromu s n uzly odpovda poctu urovn , tj. log2(n + 1)


|


30

Dobre heuristiky pro vyhledavac stromy { obecne 2 2

c asto zprstupnovan e klc e v neredundantnm stromu by mely byt umsteny blzko ke korenu pro kazdy uzel plat, z e jeho levy a pravy podstrom obsahuje tem er stejny pocet uzlu


|


31

Nahrada staticke indexove struktury dynamickou strukturou 2

pozadovane vlastnosti dynamicke indexove struktury X mus umoznit data vkladat / rusit

pri minimaln naro cnosti reorganizace X mus byt implementovatelne na disku 2 2

vhodny tip r esen { vyva zene vyhledavac stromove struktury Prklady X BVS, binarn vyhledavac strom X m-arn vyhledavac strom

2

Krucialn problem X jak zajistit dynamicky udrzovatelnou vyva zenost

pri minimaln ch ztrat ach reorganizacemi stromu?


|


32

Pozadovane vlastnosti indexu na disku 2

binarn hledan nen pro disky optimaln vyhledavac strategie X 3 az 4 vystaven disku pri hledan v indexu je na mezi prijatelnosti X binarn hledan na 4 kroky ⇒ lze hledat mezi 16 polozkami X binarn e prohlz eny index s 103 polozkami vyzaduje az 10 vystaven

2

Vklad an a rusen klc u mus byt stejne rychle jako hledan X klasicka udr zba indexu v RAM je pro vnejs pameti neakceptovatelna, X po vlozen/rusen se v indexu sm vyvolat pouze lokaln zmeny

a ne reorganizaci celeho indexu X akceptovatelna je modi kace cca do 5 ukazatelu

optimaln indexovan lze pochopitelne r esit rovnez hasovan m

2 Poznamka: ´

X viz predna ska o hasovan Jan Staudek, FI MU Brno

|


33

Dynamicke vceurov nov e indexy na bazi m-arn ch stromu 2 2

presneji { na bazi m-arn ch vyhledavac ch stromu, resp. vyhledavac ch stromu s vetvenm r adu m, kde m > 2 V prirozene interpretaci rozsr en pojmu BVS X ve vnitrnm uzlu ma vce nez 1 klc X v kazdem uzlu jsou klc e usporadan e X pro kazdy sousedn par klc u existuje podstrom obsahujc klc e

s hodnotami lezcmi mezi hodnotami tohoto paru X existuje podstrom uzlu obsahujc klc e mens nez nejmens klc v uzlu X existuje podstrom uzlu obsahujc klc e vets nez nejvets klc v uzlu 2

Proc m-arn vyhledavac strom ? X zvetsovan m arity pri zachovan poctu uzlu a vlastnosti vyva zenosti

se dosahuje snizovan vy sky stromu X dusledkem je urychlen vyhledav an dky snizovan potrebneho poctu vyhledavac ch kroku { diskovych operac pri pruchodu vetv stromu X tudz efektivn technika pro implementaci indexu souboru Jan Staudek, FI MU Brno

|


34

-arn vyhledavac strom, ilustrace struktury uzlu

m


|


35

Dynamicke vceurov nov e indexy na bazi m-arn ch stromu 2

uzel m-arn ho vyhledavac ho stromu obsahuje strukturu < p0, K1, p1, K2, . . . , pn−1, Kn, pn >, resp. < p0, K1, r1, p1, K2, r2 . . . , pn−1, Kn, rn, pn >, kde X K1 < K2 < ... < Kn jsou vyhledavac klc e X p0, p2, ..., pn jsou ukazatele potomkovych uzlu

(vyhledavac ch podstromu) nebo prazdn e ukazatele Je-li K vyhledavac klc v podstromu odkazovanem pi pak plat: je -li pi = p0,pak K < K1 je -li pi = pn,pak K > Kn je -li pi = p1, . . . , pn−1,pak Ki < K ≤ Ki+1 X [r1, r2, ..., rn jsou data nebo ukazatele na data souvisejc s klc i Ki] 2

pocet vystupn ch hran uzlu je ≤ m, tudz pocet vyhledavac ch klc u v uzlu je n ≤ m − 1 Jan Staudek, FI MU Brno

|


36

Uloha 2

Jaky je maximaln pocet uzlu v m-arn m vyhledavac m stromu vy sky h ? X X X X

v jednotlivych urovn ch i jsou pocty uzlu = mi urovn je h + 1, obsahuj m0, m1, m2, m3, . . . mh uzlu h+1 soucet prvnch h + 1 c lenu geometricke posloupnosti je mm−1−1 pro m = 3, h = 2 je to 13 uzlu, po urovn ch: 1 + 3 + 9


|


37

Uloha 2

jaky je maximaln pocet klc u v m-arn m vyhledavac m stromu vy sky h ? X kazdy uzel obsahuje az (m − 1) klc u, takze X maximaln pocet klc u v m-arn m vyhledavac m stromu vy sky h h+1 je tedy n = mm−1−1 × (m − 1) = mh+1 − 1 X pro m = 3, h = 2 je to 26 klc u, po urovn ch: 2 + 6 + 18, X pro m = 100, h = 3, 106 klc u

2

minimaln vy ska m-arn ho vyhledavac m stromu s n klc i je tudz h = O(logm(n + 1)) X pocet diskovych operac pri vyhledav an pomoc m-arn ho

vyhledavac m stromu je logaritmicky um erny poctu hodnot vyhledavac ho klc e


|


38

Uloha X maximaln pocet klc u v m-arn m vyhledavac m stromu vy sky h je n = mh+1 − 1 2

Jak vetvit m-arn strom pri zadane delce hledan a zadanem poctu klc u ? X zadane delce hledan (≈ vy sce h) a zadanemu poctu klc u { n odpovda arita alespon m = (n + 1)1/h X h = 4, n = 255, m = 4 X h = 4, n = 64K, m = 16 X h = 4, n = 1M, m = 32 X h = 3, n = 1M, m = 100


|


39

-arn vyhledavac strom, problem nevyva zenosti

m

2

Vlozenm klc u 1, 2, 3 , . . . , 14,15 do 4-arn ho vyhledavac ho stromu vznikne struktura uvedena vlevo na obrazku X degenerovany, nevyva zeny strom, slozitost hledan O(n)

2

vhodnejsm vysledkem by byl strom uvedeny vpravo { vyva zeny 4-arn vyhledavac strom

X vyhledan probehne nejhu re ve 2 krocch, slozitost hledan O(log4 n)

2

jak udrzet m-arn vyhledavac strom vyva zeny? { pomoc technologie B -stromu Jan Staudek, FI MU Brno

|


40

B-strom 2

B-strom nen ani Binarn strom, ani Balanced tree!!! X B-strom { Bayer & McCreight tree, 1972, Bayeruv strom

2

B-strom r adu m je m-arn vyhledavac strom s vlastnostmi X je to korenovy strom s jistym poctem vnitrnch uzlu a vnejsch, X

X X X

koncovych uzlu, listu Kazdy uzel obsahuje alespon jeden klc , ktery jednoznacne identi kuje zaznam v souboru a vnitrn uzel alespon dva ukazatele na potomkove uzly nebo listy. Pocet klc u a ukazatelu obsazenych v uzlu se mu ze menit ve stanovenych mezch. Pro kazdy uzel plat stejne omezen maxima poctu klc u v uzlu ...


|


41

B-strom X ... X Klc e jsou v uzlu usporadan e v neklesajcm porad. X S kazdym klc em je asociovan potomek, ktery je korenem podstromu,

ktery obsahuje vsechny uzly s klc i mensmi nebo rovnymi tomuto klc i a pritom vetsmi nez predchazej c klc . X Uzel ma nejpravejsho potomka, ktery je korenem podstromu obsahujcho uzly s klc i, ktere jsou vets nez kterykoliv klc v uzlu. X Uzel obsahuje pocet ukazatelu, ktery je o jedna vets nez pocet pocet klc u v uzlu


|


42

B-strom 2

B-strom r adu m je m-arn vyhledavac strom s omezenmi X kazdy uzel ma nejvy se m potomku (obv. 2d potomku a 2d − 1 klc u) X kazdy uzel az na koren a listy ma alespon dm/2e potomku (resp. d potomku a d − 1 klc u) X koren obsahuje alespon 1 klc a ma alespon dva potomky,

pokud nen listem X uzel s g ≤ m potomky obsahuje g − 1 vyhledavac ch klc u X vsechny listy jsou na stejne urovni 2

Vetsina vce-urov nov ych indexu pouzva B (resp. B +) stromy X pro vklad an / odstranov an klc u ponechavaj v kazdem uzlu volny

prostor (uzly jsou z poloviny az plne plne) X Uzel B (resp. B +) stromu se uchovav a v jednom bloku vnejs pameti, m typicky byv a velke (stovky), strom pak ma malou vy sku. Jan Staudek, FI MU Brno

|


43

B-strom 2

3-arn B-strom (radu 3) po vlozen zaznam u s klc i 8, 5, 1, 7, 3, 12 , 9, 6

2

B-strom je ,,neredundantn"strom X Klc e se v cele grafove strukture vyskytnou prav e jednou X Zaznamy jsou umsteny v uzlech s klc i nebo jsou z nich adresovane


|


44

B-strom 2 2 2 2 2

2

Vklad an klc e do neplneho uzlu nemen strukturu stromu Vklad an klc e do plneho uzlu men strukturu stromu, zpusob s tepen preplnovan eho uzlu na dva uzly S tepen se mu ze rozsr it na vce urovn Rusen klc e v uzlu, ktere nesnz pocet klc u v uzlu pod jednu polovinu, nemen strukturu stromu Rusen klc e v uzlu, ktere snz pocet klc u v uzlu pod jednu polovinu, zpusob slev an sousednch uzlu, men strukturu stromu Slev an se mu ze rozsr it na vce urovn


|


45

B-strom 2

Vklad an klc e (zaznamu dat) X B-strom se zacna tvorit jako jednouzlovy strom (koren) X Pokud uzel obsahuje men e nez maximum klc u, klc se vloz do uzlu a

klc e v uzlu se usporadaj X pri vklad an m-teho klc e do korene se koren s tep na dva uzly { potomky, v korenu se ponecha stredn klc a ostatn se umst pul na pul do potomku X pri vklad an m-teho klc e do nekorenoveho uzlu se uzel s tep na dva uzly na stejne urovni a stredn klc s ukazateli na rozstepene uzly se presouva do rodicovskeho uzlu X s tepen se rozsiruje az do korenu, ktery se pri pokusu o preplnen rovnez s tep (viz vy se) a zvysuje tm vy sku stromu


|


46

B-strom 2

Rusen klc e (zaznamu dat) X pokud pri rusen zaznamu klesne pocet klc u v uzlu pod 1/2 m,

sousedn uzly se slevaj vc. prpadne redukce rodice X slev an se rozsiruje az do korenu a potencialn e se tm snizuje vy ska stromu


|


47

B-strom, ilustrace konstrukce vklad an m 2

B-strom r adu 3 po vlozen zaznam u s klc i 8, 5, 1, 7, 3, 12 , 9, 6


|


48

B-strom, ilustrace konstrukce vklad an m 2

B-strom r adu 3 po vlozen zaznam u s klc i 8, 5, 1, 7, 3, 12 , 9, 6


|


49

B-strom, ilustrace konstrukce vklad an m


|


50

B-strom, ilustrace konstrukce vklad an m


|


51

B strom, odvozen r adu stromu 2

Necht' plat X Delka klc e, K = 9 B ,

delka bloku vnejs pameti B = 512 B delka ukazatele bloku vnejs pameti s daty, Pd = 7 B delka ukazatele bloku vnejs pameti s uzlem stromu, P = 6 B

2

Uzel bude obsahovat az X m ukazatelu na potomky, m − 1 ukazatelu na data a m − 1 klc u

2

Odvozen m: m × P

+ ((m − 1) × (Pd + K)) ≤ B

X m × 6 + ((m − 1) × (7 + 9)) ≤ 512, tj. m = 23 X budou-li uzly plne z 69 %, budou obsahovat 23×0,69=16 ukazatelu

(15 klc u), tj. na 0.,1.,2. a 3. urovni je 1 (15), 16 (240), 256 (3 840), 4096 (61 440) uzlu (klc u/dat), tj. indexacn kapacita tohoto 4 urov nov eho B-strom je 65 535 polozek Jan Staudek, FI MU Brno

|


52

B-strom, jeste jeden prklad vklad an


|


53

B-strom, jeste jeden prklad vklad an


|


54

B-strom, komplexnejs prklad vklad an a rusen


|


55



|


56



|


57



|


58



|


59



|


60



|


61



|


62



|


63



|


64



|


65



|


66



|


67



|


68



|


69



|


70



|


71



|


72



|


73



|


74



|


75



|


76



|


77



|


78



|


79

B+ strom 2

B+ strom je redundantn varianta B-stromu Vyva zeny vyhledavac strom, vsechny listy jsou na stejne urovni nejsr ej pouzvany index zaznamy s daty jsou adresovane pouze z listu listy jsou navc r etezene pri zachovan porad podle klc u do seznamu vnitrn uzly B+ stromu hraj roli indexu k listum Vsechny uzlu jsou alespon z poloviny plne ve vnitrnch uzlech se t.zv. hranicn klc e mohou opakovat, podmnka pro leve podstromy je ≤ Ki X vnitrn uzly r adu m mohou obsahovat az m − 1 klc u X r ad listu ml udav a, kolik obsahuje ukazatelu na zaznamy, je roven poctu klc u v listu X podporuj jak prmy tak i sekvencn prstup X X X X X X X


|


80

B+ strom


|


81

B+ strom 2

Prednost indexu typu B-strom X nekdy lze nalezt vyhledavac klc drve nez v listu

2

Nedostatky indexu typu B-strom X pouze mala c ast vsech hodnot vyhledavac ch klc u se najde "brzo\ X uzly B-stromu jsou vets nez nelistove uzly B+ stromu (o ukazatele dat)

do uzlu B-stromu se vejde men e klc u, strom bude vyss , pruchod dels X vklad an a rusen zaznam u je u B-stromu komplikovanejs nez u B+ stromu X implementace B-stromu je obtz nejs nez implementace B+ stromu X prednosti B-stromu obvykle nevyva z jejich nedostatky


|


82

B+ strom, prklad, m = 3


|


83

B+ strom, ty z prklad, m = 5


|


84

B+ strom, alternativn de nice, m = 3


|


85

B+ strom, poznamky 2 2 2 2

Nelistove uzly vytva rej vce-urov nov y r dky index listu Hranicn hodnotu klc e v korenu (pod)stromu urcuje hodnota klc e nejpravejsho listu v jeho levem podstromu Ponevadz meziuzlova propojen jsou implementovana ukazateli, logicky blzke bloky nemus byt fyzicky blzke Pri zpracovav an dotazu se prochaz cesta stromem od korenu k nekteremu listu X Jestlize v souboru je n hodnot vyhledavac ho klc e, pak tato cesta nen dels nez dlogdm/2e ne X uzel ma obvykle rozmer diskoveho bloku, napr. 4KB { m pak bude napr. 100 (40 B na jednu indexovou polozku) { a pokud je v souboru 1 milion hodnot zaznam u (n), pak vy ska stromu nepresahne log50 106 = 4,

{ tj. vyhledan zaznamu si vyzad a az 4 diskove operace, tj. pri 10 ms/diskovou operaci se vyhledan odehraje do 40 ms Jan Staudek, FI MU Brno

|


86

B+ strom, vklad an 2

Nalezni odpovdajc listovy uzel L a vloz data do L X Jestlize je v L dostatecny prostor { HOTOVO X Jestlize se L prepln { { L se rozstep na L a novy uzel L2 { Data se rovnomerne rozloz mezi L a L2 { prostredn klc se kopruje do rodice L { do rodice L se vloz odkaz na L2

2

Tento postup se mu ze rekurzivne opakovat ve vntrnch uzlech X pri s tepen indexoveho uzlu se prostredn klc posouva o urove n vy s

2 2

S tepenm strom expanduje S tepenm korene se zvysuje vy ska stromu Jan Staudek, FI MU Brno

|


87

B+ strom, m = 3, vlozen 8, 5, 1, 7, 3, 12, 9, 6


|


88

B+ strom, rusen 2

Nalezni odpovdajc listovy uzel L a zrus data v L X Jestlize L zust av a alespon z 1/2 plny { HOTOVO X Jestlize L nen alespon z 1/2 plny { { { Zkus redistribuovat data do L ze sourozence L { pokud redistribuce selze, sluc L a sourozence L

2 2

Pokud se slucovalo, mus se v rodici L odstranit odkaz na L nebo na jeho sourozence Slucovan se mu ze rozsr it az ke korenu, pak se snizuje vy ska stromu


|


89

B+ strom, m = 5, zrusen 19, 20, 24


|


90

B+ strom, prklad 2

Vypoctete optimaln r ad B+ stromu v prostred X X X X

2

klc ma delku V =9B diskovy blok ma delku B = 512 B ukazatel na zaznam s daty ma delku R=7B ukazatel na indexovy zaznam delku P =6B

Vnitrn uzly B+ stromu jsou umst'ovane po jednom v jednom diskovem bloku a kazdy obsahuje az m ukazatelu a az m − 1 klc u, takze r ad vnitrnch uzlu bude m × P + (m − 1) × V ≤ B 6m + 9(m − 1) ≤ 512 ⇒ m = 34

2

Podobne pro r ad listu plat ml × (R + V ) + P ≤ B 16ml + 6 ≤ 512 ⇒ ml = 31


|


91

B+ strom,prklad 4


|


92

B+ strom,prklad 4


|


93

B+ strom,prklad 4


|


94

B+ strom,prklad 4


|


95

B+ strom,prklad 4


|


96

B+ strom,prklad 4


|


97

B+ strom,prklad 4


|


98

B+ strom, odvozen r adu stromu 2 2 2

2

budou-li nelistove uzly plne z 69 %, budou obsahovat 34×0,69=23 ukazatelu, tj. 22 klc u budou-li listove uzly plne z 69 %, budou obsahovat 31×0,69=21 ukazatelu dat tj. na 0.,1.,2. a 3. urovni 1, 23, 529, 12 167 uzlu, tj. kapacita 4 urov nov eho indexu typu B +-strom pokryje 12 167 × 21 = 255 507 zaznam u vypoctenou aritu v reale snz potreba uchovavat organizacn informace o uzlu (vnitrn/vnejs, okamzity pocet klc u v uzlu, . . . )


|


99

Trie, radix tree, pre x tree, . . . 2 2

E.Fredkin, 1960, information retrieval trie (vyslov ,,try"jako ,,sky") je m-arn strom X datova struktura stromoveho typu pouzvana pro reprezentaci X X X X

(uchovav an ) r etezcu nad danou abecedou Na rozdl od vyhledavac ch stromu z adn y uzel trie neuchovav a klc souvisejc s danym uzlem naopak, pozice uzlu v trie ukazuje, ktery klc s n souvis kazdy uzel trie obsahuje pole ukazatelu, kazdy jeden z nich odpovda znaku abecedy vsichni nasledn ci uzlu trie maj spolecny pre x r etezu souvisejcho s danym uzlem


|


100

Trie, radix tree, pre x tree, . . . X X X X X X X 2

Koren trie je asociovan s prazdn ym r etezem hodnoty (data) se bezne neasociuj s kazdym uzlem trie, pouze s listy trie je strom, kde kazdy uzel reprezentuje jedno slovo nebo pre x slova koren stromu reprezentuje prazdn y r etez uzly { prm nasledn ci korene { reprezentuj pre xy delky 1 uzly vzdalen e 2 hrany od korene reprezentuj pre xy delky 2, . . . listovy uzel vzdalen y k hran od korene reprezentuje slovo delky k

trie nen m-arn vyhledavac strom X r azen klc ovych hodnot v uzlech nedodrzuje pravidla

pro m-arn vyhledavac strom


|


101

Trie, prklad 2

Index slov aeroplane, bycicle, bike, bus, caravan, carriage, car, train


|


102

Trie 2

jestlize je trie pouzity jako index X pak listy obsahuj adresy zaznam u s odpovdajcmi hodnotami klc u

2

jestlize je trie pouzity jako reprezentator hodnot X pak listy jsou indikatory existence zaznam u s platnymi hodnotami klc u

2

Oblast pouzit X Rychle prohledav an rozsahl ych textu via preprocesing

{ vyhledav an vzoru, pre xu porovnav an m, . . . X Konstrukce adresa ru pro rychle prochazen adresa ru kapes s hasovanymi zaznamy pri extenzibilnm (rozsiritelnem) hasovan X ...


|


103

Trie 2

klc v trie je uchovavan y v uzlech na ceste z korene k vnejsmu uzlu a nikoliv jako celek v jednom uzlu X klc e mus byt delitelne na vhodne komponentn jednotky

(symboly: znaky, cifry, . . . )

2

uzel m-arn ho trie X X X X

2

m-prvkove pole

kazdy prvek pole odpovda jednomu ,,radu"kl c e prvek pole obsahuje ukazatel nebo indikator prazdn eho msta pozice prvku pole, obsahujc ukazatel, urcuje hodnotu r adu

Jiny nazev { radix searching

X zaklad je odvozeny z abecedy pouzite pro kodov an klc e X m je dano zakladem pouzitym pro vyjad ren klc e trie

{ 10, dekadicke cifry, { 26/27, znaky/vc. mezery { ...


|


104

Trie, vlastnosti 2

2 2 2 2 2

Necht' S je mnozina s klc u vytvorenych z usporadan e abecedy komponent Σ takova, z e z adn y klc v S nen pre xem jineho klc e { S tvor napr. s vybranych slov jisteho jazyka, { Σ je abeceda tohoto jazyka Kazdy uzel usporadan eho trie T , s vyjimkou korene, obsahuje znak c z S T ma s takovych vnejsch uzlu, z e zretezen znaku na kazde ceste z korene do vnejsho uzlu tvor klc z S Kazdy vnitrn uzel T ma nejvy se |Σ| potomku T ma s vnejsch uzlu Vy ska T je rovna delce nejdelsho klc e v S Jan Staudek, FI MU Brno

|


105

Co mohou byt klc e v tries ? 2 2 2 2 2 2 2

r etezce (slozene ze znaku) prirozena c sla (slozena z c slic) cela c sla (slozena z c slic, +, -) zlomky (slozene z c slic, +, -, /) realn a c sla (slozena z c slic, +, -, .) slova poctace (slozena z 0, 1) objekty (slozene z objektu)


|


106

Vlastnosti trie 2 2

vy ska trie je dana delkou nejdelsho klc e vyhody X delka hledan v trie je um erna delkce klc e

X X X X

{ nikoli logaritmu poctu uzlu ve stromu { neusp es ne hledan mu ze skoncit na kterekoliv urovni pro prpad velkeho mnozstv kratk ych klc u je prostorove efektivn, inicialn sekvence se sdl pocet vnitrnch uzlu je dany delkami klc u, neni nutne strom vyvazovat pri vklad an jsou rychlejs nez hasovane tabulky, nemus se prepracovavat indexy pri preplnen ...


|


107

Trie, prklad 2

mnozina hodnot klc u X 293...,2960, 2966, 2967, 25..., 73...,


|


108

Trie, prklad, rozsiritelne hasovan 2

implementace pomoc trie a pomoc tabulky


|


109

B+ stromy, tries

Recommend Documents