Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### B-stromy

Definice (B-strom)

B-strom řádu je výškově vyvážený strom, který má násl. vlastnosti:

1. Kořen má minimálně 2 syny, pokud není sám listem.
2. Každý jiný uzel kromě listů má nejméně a nejvíce synů a vždy o 1 méně dat. záznamů (listy mají jen datové záznamy).
3. Klíče všech záznamů v -tém podstromu uzlu jsou větší než klíč -tého záznamu uzlu a menší nebo rovny klíči -tého záznamu.
4. všechny větve (cesty od kořene k listu) jsou stejně dlouhé.

Variantou jsou redundantní B-stromy, kdy všechna data jsou umístěna v listech, vnitřní uzly obsahují pouze vyhledávací klíče. Jiná možnost je použití pouze klíče a odkazu na celý záznam, místo vkládání kompletních záznamů do stromu.

Algoritmus (Operace na B-stromě)

Vyhledávání v B-stromech podle klíče se provádí jednoduchým průchodem do hloubky.

Vkládání se děje nalezením místa pro vložení. Pokud ještě daný rodič neobsahuje synů, jednoduše nového syna vložím. Pokud ano, je nutné rozštěpit rodičovský uzel na dva (do každého dám polovinu synů). Toto se může opakovat směrem k vyšším vrstvám, případně až do kořene.

Odebírání prvků je opačný postup, v případě podtečení uzlu (zůstane v něm méně než synů) musím přebírat data od sousedních uzlů nebo slévat. V redundantních B-stromech není nutné při mazání odstraňovat vyhledávací klíč z vnitřních uzlů - prvek s touto hodnotou se ve stromě už nebude nacházet, ale vyhledávat podle jeho klíče je dál možné.

Lepší naplněnosti uzlů za cenu snížení rychlosti se dá dosáhnout pomocí vyvažování stránek - při přetečení stránky nejdřív kontroluji, jestli nejsou volné sousední; pokud ano, přerozdělím data a upravím klíče. Podobně je možné postupovat při mazání (i pokud není třeba slévat).

Dalším vylepšením je odložení štěpení - ke každému listu nebo skupině listů přísluší stránka přetečení, kam se vkládají záznamy, které se už do daného místa nevejdou. Nové vkládání a štěpení je provedeno až tehdy, jestliže se stránka přetečení i všechny příslušné uzly naplní. Takto upravený strom s více než 1 úrovní má vždy všechny listy zaplněné (za předpokladu nepoužití mazání). Přísluší-li stránky přetečení skupinám listů, musím je při mazání a přidávání listů taktéž štěpit a slévat.

Definice (B+ stromy)

B+ stromy jsou mírným vylepšením B-stromů pro zrychlení intervalových dotazů: všechny uzly ve stejné úrovni (a nebo jenom listy) jsou spojeny do spojového seznamu (možná je jednosměrná i obousměrná varianta).

Definice (B* stromy)

B* stromy (řádu ) jsou úpravou B-stromů na základě vyvažování stránek. Druhá podmínka B-stromů se upraví tak, že každý uzel kromě kořene a listů má minimálně a max. synů a odpovídající počet dat. záznamů. Listy mají opět jen stejné rozmezí pro počet dat. záznamů. Při vkládání prvků se stěpení odkládá opět do té doby, dokud nejsou plní i sourozenci daného listu; potom se štěpí buď 2 listy do 3, nebo 3 do 4 (buď s pomocí jednoho nebo dvou sousedních sourozenců). Odebírání podobně zahrnuje slévání 3 uzlů do 2 (nebo 4 do 3). Při obém lze ve složitější variantě zapojit ještě více uzlů.

Definice (Prefixové stromy (Trie))

Tento druh stromů slouží k uložení dat, klíčovaných řetězci. Jde o redundantní stromy, data jsou uložena až v listech; vyhledávací klíče jsou vždy co nejkratší možné prefixy řetězců, nutné k odlišení uzlů. Celé hodnoty klíčů (a další data) se nacházejí až v listech. Při vkládání a štěpení stránek se nějakou heuristikou hledá nejkratší prefix, který by vzniklé stránky oddělil. Vylepšená varianta neukládá u synů předponu klíče, kterou má rodič - je to paměťově efektivnější, ale zvyšuje výpočetní nároky.

Definice (Stromy s proměnnou délkou záznamu)

Jde o modifikaci B-stromu, která umožňuje do něj uložit záznamy proměnné délky. Listy se neštěpí podle počtu záznamů, ale zhruba na poloviny podle velikosti dat. Druhá podmínka B-stromů se upraví následovně: celková délka záznamů v jednom uzlu je minimálně a maximálně (kde je nějaká zvolená hodnota, větš. velikost stránky na disku). Existuje i varianta s podmínkou , jako mají B*-stromy.

Problémem této struktury je tendence delších záznamů ke stoupání ke kořeni, čímž se snižuje arita záznamů. To se řeší hledáním dělícího záznamu s min. délkou tak, aby vzniklé uzly splňovaly podmínky stromu (a je to docela náročné). Navíc štěpení je složitější - 1 stránka se může štěpit na 3 (vložím-li hodně dlouhý záznam), může dojít ke zmenšení stromu při vložení apod., běžně se používá obecný algoritmus nahrazování, jehož speciální případy jsou insert a delete.

Definice (Vícerozměrné B-stromy)

Používají se, je-li potřeba efektivně hledat záznamy podle více atributů. Jde o propojenou množinu stromů. K jednotlivým atributům příslušejí prvky pole odkazů na seznamy stromů, ve kterých se podle daných atributů dá hledat. Pro první atribut je potřeba jen 1 strom, v něm je pro každý klíč odkaz na celý strom 2. atributu (pro další je to podobné). Stromy stejného atributu jsou ve spojovém seznamu. Mohu hledat všechny záznamy, pro které znám hodnoty všech atributů, nebo jenom jejich podmnožinu - vyžaduje to projít více stromů, ale není třeba množinových operací.