- Stahuj zápisky z přednášek a ostatní studijní materiály
- Zapisuj si jen kvalitní vyučující (obsáhlá databáze referencí)
- Nastav si své předměty a buď stále v obraze
- Zapoj se svojí aktivitou do soutěže o ceny
- Založ si svůj profil, aby tě tví spolužáci mohli najít
- Najdi své přátele podle místa kde bydlíš nebo školy kterou studuješ
- Diskutuj ve skupinách o tématech, které tě zajímají
Studijní materiály
Hromadně přidat materiály
B_plus_minus_stromy
PB154 - Základy databázových systémů
Hodnocení materiálu:
Zjednodušená ukázka:
Stáhnout celý tento materiáldeno efektivně, protože rekonstrukce indexu je logaritmická v čase
Dotazy v B+-stromech:
Najdi všechny záznamy s klíčem k:
Začni na kořenu:
Urči větev s nejmenší hodnotou klíče, která je ale větší než k
Pokud taková hodnota existuje, předpokládejme, že jde o Ki. Potom skoč na následníka, na který ukazuje Pi
Jinak k > Km-1, kde m je počet ukazatelů ve větvi. V tomto případě skoč na větev na kterou ukazuje Pm.
Pokud skokem dosažená větev není zároveň listem, zopakuj předchozí algoritmus na aktuální větev (jako kdyby to byl kořen).
Pokud se jedná o list, pak prohledej ten list a když bude nějaký klíč Ki roven klíči k, pak ukazatel Pi ukazuje do souboru na požadovanou strukturu nebo do seznamu ukazatelů na tyto struktury. Pokud není žádný takový klíč nalezen záznam pro klíč k neexistuje
Při provádění dotazu je provedena cesta napříč stromem od kořene k listu
Pokud soubor obsahuje K klíčů, cesta není dešlí než
…. Blabla, keci o tom kolik se ušetří… viz slide 11.24
Vkládání do stromu:
Najdi list ve kterém by se měl nový klíč nacházet…
Pokud je klíč již v listu, pak přidej záznam dat do souboru a pokud je to potřeba, tak přidej záznam do seznamu ukazatelů na struktury v souboru (dále jen bucket = košík, viz originální text)
Pokud není klíč v listu, potom přidej záznam do hlavního souboru (dat) a vytvoř bucket pokud je to potřeba. Pak:
Pokud je místo v listu, vlož dvojici (klíč, ukazatel na záznam nebo bucket) do listu na odpovídající pozici
Pokud není v listu místo rozděl a vlož dvojici (klíč, ukazatel na záznam nebo bucket) podle algoritmu dále
Rozdělení listu:
Vezmi n dvojic (klíč, ukazatel na záznam nebo bucket) a to včetně vkládaného, to vše srovnané. Umísti prvních do původního listu a zbytek do nového listu
Nechť nový list je p a ať k je nejmenší klíč v p. Vlož dvojici (k, p) do rodiče položky, která byla rozdělena. Pokud je rodič plný, rozděl ho také podle tohoto algritmu.
Rozdělování listů (větví) probíhá do té doby (směrem nahoru) dokud není nalezen list (větev), který by nebyl plný. V nejhorším případě musí být rozdělen kořen a tím zvětšen počet úrovní stromu.
Mázání ze stro
Vloženo: 24.04.2009
Velikost: 130,04 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2025 unium.cz
