- 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álmu:
Najdi záznam, který má být vymazán a vymaž ho z hlavního souboru (dat) a také z bucketu (pokud existuje)
Vyjmi dvojici (klíč, ukazatel) z listu pokud zde není žádný bucket nebo je prázdný
Pokud má list příliš málo záznamů (díky odstranění) a záznamy v listu a v sousedních listech se vejdou do jednoho listu pak:
Vlož všechny klíče ze dvou listů do jednoho (do toho víc nalevo) a vymaž ten druhý list
Vymaž dvojicí (Ki-1, Pi), kde Pi je ukazatel na vymazaný list, z rodiče, to vše rekursivně použitím tohoto algoritmu
Jinak, pokud má list příliš málo záznamů (díky odstranění) a záznamy v listu a v sousedních listech se Nevejdou do jednoho listu, pak:
Přerozděl ukazatele mezi list a sousední list, tak že oba mají více (nebo stejně) než minimální počet záznamů v listu
Obnov odpovídající klíč v rodiči
Výmaz záznamu může opět probíhat směrem nahoru dokud není nalezena větev (list) se stejně nebo více než ukazateli. Pokud má kořen pouze jeden ukazatel (po výmazu), pak je smazán a jeden následník se stane kořenem
Odstranění listu obsahující „Downtown“ nevyústí v to, že by jeho rodič měl příliš málo ukazatelů. Takže kaskádní výmaz se zastaví výmazem záznamu z rodiče mazaného listu
Rodič vymazaného „Perryridge“ je nyní příliš malý, ale sousedi nemají místo, aby přijali další ukazatel. Takže je nutné přerozdělení. Vidíme, že kořen jako výsledek operace se změní i klíč kořene.
Organizace souboru B+-stromu:
Zmenšení účinnosti indexačního souboru je vyřešena použitím B+-stromových indícií. Totéž platí pro datový soubor použitím organizace souboru B+-stromu.
Listy v organizaci souboru B+-stromu ukládají přímo záznamy místo ukazatelů
Protože záznamy jsou větší než ukazatele, maximální počet záznamů, které mohou být uloženy v listu je menší než počet ukazatelů ve větvi
Listy musí mít stále více než polovinu položek
Vkládání a mazání je prováděno stejně jako vkládání a mazání záznamů u B+-stromů
Dobré využití místa je nutné, protože záznamy vyžadují více místa než ukazatele. Pro zvýšení využití místa je při přerozdělování (během rozdělování a spojování listů) dobré zahrnout více sousedních listů.
Vloženo: 24.04.2009
Velikost: 130,04 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2025 unium.cz
