- 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
B_plus_minus_stromy
PB154 - Základy databázových systémů
Zjednodušená ukázka:
Stáhnout celý tento materiálB+ - stromy
B+ - strom – je kořenový strom s následujícími pravidly:
Všechny cesty z kořenu k listu mají stejnou délku
Každá větev, která není kořen nebo list, má mezi a n následníky
List má mezi (zaokrouhleno nahoru) a n – 1 hodnotami
Speciální případy: pokud kořen není zároveň i list má minimálně 2 následníky. Pokud je kořen list (nejsou zde žádné další větve), může mít mezi 0 a n – 1 hodnotami
Typická větev –
má tvar:
P1
K1
P2
…
Pn-1
Kn-1
Pn
Ki – je vyhledávací hodnota
Pi – je ukazatel na následníka (pro nelistovou větev) nebo ukazatel na záznamy nebo na seznamy ukazatelů na záznamy (pro list)
Vyhledávací klíče jsou seřazeny:K1 < K2 < K3 < … < Kn-1
Vlastnosti listů:
Pro i = 1, 2, …, n-1, ukazatel Pi ukazuje buď na záznam v souboru s vyhledávacím klíčem Ki nebo do seznamu ukazatelů na struktury v souboru, kde každý klíč v tomto seznamu má hodnotu Ki. Seznam ukazatelů je potřeba pouze pokud vyhledávací klíč není klíčem primárním (hodnotu vyhledávacího klíče může mít více položek v DB)
Hodnoty vyhledávacích klíčů levějších listů mají menší hodnoty než hodnoty vyhledávacích klíčů pravějších listů
Pn ukazuje na další list v pořadí vyhledávání
Větev:
Větev formuje multi-level řídký index pro listy. Pro větev s m ukazateli:
Všechny vyhledávací klíče v podstromu na který ukazuje P1 jsou menší než K1
Pro i mezi 2 a n-1 všechny vyhledávací klíče v podstromu na který ukazuje Pi jsou větší nebo stejné jako Ki-1 a zároveň menší než Ki
Všechny vyhledávací klíče na které ukazuje Pn jsou větší nebo rovny klíči Kn-1
P1
K1
P2
…
Pn-1
Kn-1
Pn
Příklad B+-stromu:
Listy musí mít mezi 2 a 4 hodnotami ( a n-1)
Větve (ne kořenové) musí mít mezi 3 a 5 následníky ( a n)
Kořen musí mít minimálně 2 následníky
Zjištění pro B+-stromy:
Protože jsou spojení mezi listy (větvemi) provedena pomocí ukazatelů není nutno předpokládat, že „logicky“ uzavřené bloky jsou též uzavřené „fyzicky“
Ne-listové úrovně formují hierarchii řídkých indicií
B+-stromy obsahují relativně malý počet úrovní (logaritmicky ve velikosti hlavního souboru), proto mohou být hledání provedena efektivně
Vkládání a odebírání může být prove
Vloženo: 24.04.2009
Velikost: 130,04 kB
Komentáře
Tento materiál neobsahuje žádné komentáře.
Copyright 2023 unium.cz. Abychom mohli web rozvíjet a dále vylepšovat podle preferencí uživatelů, shromažďujeme statistiky o návštěvnosti, a to pomocí Google Analytics a Netmonitor. Tyto systémy pro unium.cz zaznamenávají, které stránky uživatel na webové stránce navštívil, odkud se na stránku dostal, kam z ní odešel, jaké používá zařízení, operační systém či prohlížeč, či jaký má preferenční jazyk. Statistiky jsou anonymní, takže unium.cz nezná identitu návštěvníka a spravuje cookies tak, že neumožňuje identifikovat konkrétní osoby. Používáním webu vyjadřujete souhlas použitím cookies a následujících služeb: