Implementace databázových systémů/Indexace

okruhy 09/10 (pro srovnání): Metody indexace relací, datové struktury na externí pameti: hašování, B-stromy. Vícerozmerné dotazy pomocí hašovacích metod, vícerozmerných mrížek, vícerozmerných stromu. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: indexy, signatury, metody implementace signatur (vrstvené kódování), usporádání odpovedí.

okruhy 14/15: Indexace relacních dat: B-stromy, hašování, GRACE algoritmus. Prístupové metody k prostorovým objektum: R-stromy a jejich varianty. Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace.

Interní hašování

viz společná část "Hašování" dá se to přežít jenom s interním hashováním

Externí hašování

hashovací struktura se nevejde do hlavní paměti (RAM), efektivnost se počítá podle počtu přístupů k blokům v externí paměti (HDD)

Statické hashovací metody

• hashovací fce mapuje klíče do fixního počtu adres/stránek
• umožňují přidávat klíče ale neumožňují rozšiřovat adresní prostor bez přehashování celého indexu
• vhodné pro statické databáze

Cormack (perfektní hashování)

Pre pristup najprv vypocitame riadok s adresata funkciou h(k) = j . Adresa v hlavnom subore bude potom j.p + hⱼᵢ (k, j.r)

V vyzdvyhnutiu lubovolneho zaznamu su potrebne najviac dva pristupy na disk. Ak je adresar ulozeny v pamati tak potom jeden.

Potrebujeme:

• Hlavnu hashovaciu funkciu h(k) ktora vracia [0...n] Pre pristup k riadku adresara
• Pomocnu hashovaciu funkcia hᵢ(k, r) vracia hodnotu s ⟨0, r - 1⟩ napr hᵢ(k, r) = (k mod (2i + 100r + 1)) mod r
• Adresar ( Velkost O(n) kde n je velkost suboru ) ktory obsahuje parametre druhej hashovacej funkcie ( p : index do primarneho adresara, i index hashovacej funcie , r pocet miest na kolko hashovacia funcia hᵢ prvky hashuje)
• Primarny subor obsahuje data a je ulozeny na disku.

FIND: Pre pristup najprv vypocitame riadok s adresata funkciou h(k) = j . Adresa v hlavnom subore bude potom j.p + hⱼᵢ ( k, j.r )

INSERT: Vsetky hodnoty adresara su na zaciatku 0.

• Zistime riadok adresara
  • Ak je prvy najdeme pre neho volne miesto , ulozime ho a zauktualizujeme adresar
  • Ak nieje prvy zobereme kolidujuce zaznamy a pozrieme ci nemame koliziu. Ak nie najdeme novu funciu ktora bude mat obor hodnot tak aby sme zaheshovali n + 1 prvkov , najdeme volne miesto a zaktualizujeme adresar.

Příklad

Vysvetlivky: p ... pointer do primarniho souboru i ... index pouzite hashovaci funkce r ... pocet kolidujicich prvku/rozsah pro hi (velikost bloku v prim. souboru, jehoz zacatek dostanu pomoci has. fce h) Hashovaci funkce: h(k) = k mod 7 hi(k,r) = (k >> i) % r Vkladane prvky: 8, 9, 23, 5, 12, 22, 2 i(8): p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ 8 │ 1 │ 0 │ 0 │ 1 │ └────┘ 2 │ │ │ │ \ 3 │ │ │ │ primarni soubor 4 │ │ │ │ 5 │ │ │ │ 6 │ │ │ │ - adresar └────┴───┴───┘ -------------------------------------------------------------------------- i(9): p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ 8 │ 1 │ 0 │ 0 │ 1 │ 1 │ 9 │ 2 │ 1 │ 0 │ 1 │ └────┘ 3 │ │ │ │ 4 │ │ │ │ 5 │ │ │ │ 6 │ │ │ │ └────┴───┴───┘ -------------------------------------------------------------------------- i(23): 23 % 7 = 2, dochazi ke kolizi. Najdeme nove misto v prim. souboru, kam se vejdou oba kolidujici prvky (souvisly blok velikosti 2). Prvni takovy existuje na pozici 2. Zkusime pouzit fci h0: 23 % 2 = 1, ale take 9 % 2 = 1. Musime tedy zvolit jinou hasovaci funkci. Pouzijeme h1, vypocitame nove pozice prvku 9 a 23 v ramci bloku velikosti 2. (23 >> 1) % 2 = 11 % 2 = 1 (9 >> 1) % 2 = 4 % 2 = 0 Vysly ruzne hodnoty, tedy lze h1 pouzit. p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ 8 │ 1 │ 0 │ 0 │ 1 │ 1 │ │ 2 │ 2 │ 1 │ 2 │ 2 │ 9 │ 3 │ │ │ │ 3 │ 23 │ 4 │ │ │ │ └────┘ 5 │ │ │ │ 6 │ │ │ │ └────┴───┴───┘ -------------------------------------------------------------------------- i(5): p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ 8 │ 1 │ 0 │ 0 │ 1 │ 1 │ 5 │ 2 │ 2 │ 1 │ 2 │ 2 │ 9 │ 3 │ │ │ │ 3 │ 23 │ 4 │ │ │ │ └────┘ 5 │ 1 │ 0 │ 1 │ 6 │ │ │ │ └────┴───┴───┘ -------------------------------------------------------------------------- i(12): Kolize s cislem 5. Zkusime pouzit hasovaci fci h0. 5 % 2 = 1 12 % 2 = 0 p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ 8 │ 1 │ 0 │ 0 │ 1 │ 1 │ │ 2 │ 2 │ 1 │ 2 │ 2 │ 9 │ 3 │ │ │ │ 3 │ 23 │ 4 │ │ │ │ 4 │ 12 │ 5 │ 4 │ 0 │ 2 │ 5 │ 5 │ 6 │ │ │ │ └────┘ └────┴───┴───┘ -------------------------------------------------------------------------- i(22): Kolize s 8. Fci h0 nelze pouzit k rozliseni, zkusime h1. (8 >> 1) % 2 = 0 (22 >> 1) % 2 = 1 p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ │ 1 │ 6 │ 1 │ 2 │ 1 │ │ 2 │ 2 │ 1 │ 2 │ 2 │ 9 │ 3 │ │ │ │ 3 │ 23 │ 4 │ │ │ │ 4 │ 12 │ 5 │ 4 │ 0 │ 2 │ 5 │ 5 │ 6 │ │ │ │ 6 │ 8 │ └────┴───┴───┘ 7 │ 22 │ └────┘ -------------------------------------------------------------------------- i(2): Kolize s 9 a 23. Fce h0 selze, protoze 23 % 3 = 2 % 3 = 2. 9 dec = 1001 bin 23 dec = 10111 bin 12 dec = 1100 bin Zkusime h1: (9 >> 1) % 3 = 4 % 3 =1 (23 >> 1) % 3 = 11 % 3 = 2 (2 >> 1) % 3 = 1 Zkusime h2: (9 >> 2) % 3 = 2 (23 >> 2) % 3 = 2 (2 >> 2) % 3 = 0 Zkusime h3: (9 >> 3) % 3 = 1 (23 >> 3) % 3 = 2 (2 >> 3) % 3 = 0 p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ │ 8 │ 2 │ 1 │ 6 │ 1 │ 2 │ 1 │ │ 9 │ 9 │ 2 │ 8 │ 3 │ 3 │ 2 │ │ 10 │ 23 │ 3 │ │ │ │ 3 │ │ └────┘ 4 │ │ │ │ 4 │ 12 │ 5 │ 4 │ 0 │ 2 │ 5 │ 5 │ 6 │ │ │ │ 6 │ 8 │ └────┴───┴───┘ 7 │ 22 │ -------------------------------------------------------------------------- d(23): Postupujeme podobne jako u vkladani. Potrebujeme najit souvisly blok velikosti 2. Takovy je na zacatku, nemusime zvetsovat velikost prim. souboru. Zmenime tedy p na 0. Snizime r a prozkousime has. fce. Zkusime h0: 23 % 2 = 1 2 % 2 = 0 p i r ┌────┬───┬───┐ ┌────┐ 0 │ │ │ │ 0 │ 2 │ 1 │ 6 │ 1 │ 2 │ 1 │ 9 │ 2 │ 0 │ 0 │ 2 │ 2 │ │ 3 │ │ │ │ 3 │ │ 4 │ │ │ │ 4 │ 12 │ 5 │ 4 │ 0 │ 2 │ 5 │ 5 │ 6 │ │ │ │ 6 │ 8 │ └────┴───┴───┘ 7 │ 22 │ └────┘

Faginovo hashovanie pre hlbku adresara 2

Dynamické hashovací metody

• umožňuje dynamický nárůst adresního prostoru pomocí dynamické hashovací fce
• vhodné pro db s měnící se velikostí

Fagin (rozšiřitelné adresářové hashování, Koubkovo "externí hashování")

Potrebujeme

• Adresar ( Obsahuje ukazovatele / nie nutne unikatne / na stranky dat v na disku ; hlavicku v ktorej je ulozena hlbka adresara 0 < d < r) / aky pocet bitov sa bere s pseudokluca)
• Hashovaciu funkciu pre pseodukluc h(k). Pseodukluce maju vsetky rovnaku dlzku r
• Stranky na disku , stranka obsahuje lokalnu hlbku d`. Ak d` < d tak na jednu stranku vedie viac ukazovatelov

FIND:

• Spocitame pseodukluc k` = h(k)
• Vezmeme hlbku adresata (d) a precitame prvych d bitov s pseodokluca ( nazveme to p)
• Zobereme ukazovatel, ktory je umieneny v p.v ( v je velkost kazdeho pointra v bytoch ) ⇒ vedie na hladanu stranku

INSERT: Když se stránka naplní, rozštěpím ji na 2 podle dalšího bitu hash-funkce. Pokud už stránka používá stejně bitů jako adresář, musím zvětšit o 1 bit i adresář.

Příklad

Predpokladejme, ze do stranky se vejdou 2 zaznamy h(k) = k mod 32 - hasovaci fce -Vzdy na klic pouzijeme h(k) a potom vezmeme horni bity z takto ziskaneho cisla. -Pocet bitu, ktere budeme brat mame v "ousku" adresare. Pritom vzdy uvazujeme vsech pet bitu z cisla, tj napr. 2 dec = 10 bin budeme uvazovat jako 00010 Vkladane hodnoty: 5, 20, 33, 28, 30, 8, 25 i(5): // 5 dec = 00101 "ousko" adresare - rika, kolik bitu ma adresar ┌─┐/ "ousko" u stranky - rika, kolik (hornich) bitu rozlisuje │1└─┐ ┌─┐/ hodnoty 0 │ │─────│1└─┐ 1 │ │─┐ │ 5 │ └───┘ │ │ │ │ └───┘ └┌─┐ │1└─┐ │ │ │ │ └───┘ i(20): // 20 dec = 10100 ┌─┐ │1└─┐ ┌─┐ 0 │ │─────│1└─┐ 1 │ │─┐ │ 5│ └───┘ │ │ │ │ └───┘ └┌─┐ │1└─┐ │ 20│ │ │ └───┘ i(33): // 33 mod 32 = 1 = 00001 ┌─┐ │1└─┐ ┌─┐ 0 │ │─────│1└─┐ 1 │ │─┐ │ 5│ └───┘ │ │ 33│ │ └───┘ └┌─┐ │1└─┐ │ 20│ │ │ └───┘ i(28): // 28 = 11100 ┌─┐ │1└─┐ ┌─┐ 0 │ │─────│1└─┐ 1 │ │─┐ │ 5│ └───┘ │ │ 33│ │ └───┘ └┌─┐ │1└─┐ │ 20│ │ 28│ └───┘ i(30): // 30 = 11110 Chceme umistit hodnotu do stranky, ktera je plna. Zvetsime adresar, po zmene bude dvoubitovy. Strankam, ktere nepotrebujeme stepit jen zvetsime "rozsah", prvky ze stepenych stranek rozhazime podle hornich bitu do spravnych stranek. Take si do "ouska" stranek poznamename, ze rozlisujeme hodnoty podle dvou bitu. ┌─┐ ┌─┐ │2└─┐ │1└─┐ 00 │ │─┬───│ 5│ 01 │ │─┘ │ 33│ 10 │ │───┐ └───┘ 11 │ │─┐ └─────┌─┐ └───┘ └┌─┐ │2└─┐ │2└─┐ │ 20│ │ 28│ │ │ │ 30│ └───┘ └───┘ i(8): // 8 = 01000 Vkladame do plne stranky, ta se ale da rozstepit, protoze rozlisuje hodnoty jen podle jednoho bitu. ┌──────────┌─┐ ┌─┐ │ ┌─┐ │2└─┐ │2└─┐│ │2└─┐ │ 5│ 00 │ │┘┌───│ 8│ │ 33│ 01 │ │─┘ │ │ └───┘ 10 │ │───┐ └───┘ 11 │ │─┐ └─────┌─┐ └───┘ └┌─┐ │2└─┐ │2└─┐ │ 20│ │ 28│ │ │ │ 30│ └───┘ └───┘ i(25): // 25 = 11001 Vkladame do plne stranky, jeji "rozsah" nelze rozdelit (rozlisuje hodnoty podle dvou bitu) - musime zvetsit adresar a rozdelit prislusnou stranku a zmenit "rozsahy" jednotlivych stranek. ┌─────────┌─┐ ┌─┐ │ ┌─┐ │2└─┐ │3└─┐ │ │2└─┐ │ 8│ 000 │ │─┤┌──│ 5│ │ │ 001 │ │─┘│ │ 33│ └───┘ 010 │ │─┬┘ └───┘ 011 │ │─┘ ┌─┐ 100 │ │─┬────────────│2└─┐ 101 │ │─┘ ┌─┐ │ 20│ 110 │ │─────────│3└─┐│ │ 111 │ │──┌─┐ │ 25│└───┘ └───┘ │3└─┐ │ │ │ 28│ └───┘ │ 30│ └───┘

Schéma štěpení při lineárním hašování

Litwin (lineární bezadresářové hashování)

Nevyužívá adresář, ale potřebuje oblast přetečení a tedy není zaručeno, že se ke všem datům dostaneme v 1 přístupu na disk. Data uložena ve stránkách.

Stránky jsou štěpeny nezávisle na tom, kde došlo ke kolizi, kruhovým schématem (viz obrázek). Po každých L (L je parametr metody) vloženích je rozštěpena 1 stránka. Když dochází ke štěpení stránky, přidáme 1 stránku na konec úložiště stránek . Záznamy ze štěpené stránky (a případné z oblasti přetečení, které by patřily do štěpené stránky) jsou potom rozděleny mezi novou a štěpenou stránku.

FIND: h(k) = k` (pseudoklíč má na rozdíl Fagina podle posledních bitů a jeho délku spočítá podle počtu všech stránek, pokud tam není hledáme v obl.přetečení)

INSERT: najdi místo pomocí FIND a pak vložíme, pokud se nevejde tak nacpeme do oblasti přetečení, po L INSERTech štěpíme a podle posledních bitů rozdělíme záznamy

Růst primárního souboru je lineární ⇒ lineární hashování

Příklad

Hasovaci fce - v nasem pripade pouze prevod z desitkove do dvojkove soustavy Vysvetlivky: b = 3 ...velikost bloku l = 2 ...po kolika insertech se ma stepit stranka Vkladane hodnoty: 12, 5, 4, 1, 3, 2, 7, 14 i(12): ┌────┐ Kdyz mame jedinou stranku (do 1. stepeni), vkladame do ni │ 12 │ vsechny hodnoty (nezalezi na poslednim bitu). │ │ │ │ └────┘ i(5): ┌────┐ │ 12 │ │ 5 │ │ │ └────┘ "oznaceni stranky" - posledni bit(y) cisel ve strance maji ├──────┐ / tuto hodnotu │ 0 │ 1 ┌────┐ ┌────┐ Protoze l=2 a vlozili jsme druhy prvek, dojde ke stepeni. │ 12 │ │ 5 │ Podle posledniho bitu cisel se rozhodne, do │ │ │ │ ktere pujdou stranky. │ │ │ │ └────┘ └────┘ i(4): 0 1 ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ 4 │ │ │ │ │ │ │ └────┘ └────┘ i(1): 0 1 ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ 4 │ │ 1 │ │ │ │ │ └────┘ └────┘ ├──────────────┐ │ 00 1 │10 ┌────┐ ┌────┐ ┌────┐ Vlozili jsme 4. prvek - dochazi ke stepeni. │ 12 │ │ 5 │ │ │ Hodnoty rozdelujeme podle poslednich dvou │ 4 │ │ 1 │ │ │ bitu. │ │ │ │ │ │ └────┘ └────┘ └────┘ i(3): 00 1 10 ┌────┐ ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ │ │ 4 │ │ 1 │ │ │ │ │ │ 3 │ │ │ └────┘ └────┘ └────┘ i(2): 00 1 10 ┌────┐ ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ 2 │ │ 4 │ │ 1 │ │ │ │ │ │ 3 │ │ │ └────┘ └────┘ └────┘ ├──────────────┐ 00 │ 01 10 │11 ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ 2 │ │ 3 │ │ 4 │ │ 1 │ │ │ │ │ │ │ │ │ │ │ │ │ └────┘ └────┘ └────┘ └────┘ i(7): 00 01 10 11 ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ 2 │ │ 3 │ │ 4 │ │ 1 │ │ │ │ 7 │ │ │ │ │ │ │ │ │ └────┘ └────┘ └────┘ └────┘ i(14): 00 01 10 11 ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ 12 │ │ 5 │ │ 2 │ │ 3 │ │ 4 │ │ 1 │ │ 14 │ │ 7 │ │ │ │ │ │ │ │ │ └────┘ └────┘ └────┘ └────┘ ├───────────────────────────┐ │000 01 10 11 │100 ┌────┐ ┌────┐ ┌────┐ ┌────┐ ┌────┐ │ │ │ 5 │ │ 2 │ │ 3 │ │ 12 │ │ │ │ 1 │ │ 14 │ │ 7 │ │ 4 │ │ │ │ │ │ │ │ │ │ │ └────┘ └────┘ └────┘ └────┘ └────┘

další zdroje
https://is.cuni.cz/webapps/zzp/detail/46740/

GRACE algoritmus

viz Algoritmy implementace relacních operací.

B-stromy (🎓🎓🎓🎓)

praktické použití B-stromů:
NTFS adresáře (B+) Oracle 11g (B+) MS SQL Server 2012 (B+) PostgreSQL 9.2 (B+) MySQL 5.5 (B+)

Více I2 praktický pohled z OZD - důležitá otázka pro databázisty

okruhy 14/15: B-stromy a jejich varianty

Zážitky ze zkoušek

Indexace relacnich dat (2014, Hoksza) - B-stromy a hasovani - -B B+ B* (proc se pouzivaji - velikost vnitrniho uzlu), hashování 7 druhu, viz Hoksza slajdy DS - B-stromy a jejich varianty (2014, Kopecký) - Popsal jsem definice, co splňují, operace, vyváženosti a jaké jsou varianty ((ne)redundantní, B+, B*). Pak chtěl pan Kopecký vědět, k čemu jsou dobré (zmínil jsem indexování) a dlouho se ptal na různé detaily (např. jak zabránit zamykání celého B-stromu při insertu pokud se ke stromu přistupuje paralelně - lze provádět dopředný split již naplněného uzlu, jaká varianta stromu je nejlepší pro indexování, které atributy v DB jsou vhodné pro indexování - záleží např. na doméně, atd.) DS - B-stromy a jejich varianty (2012) - tady jsem neznal úplně všechny varianty (stacily B/B+/B* jine TEORIE.PDF je neobsahuje), ale nebylo to nijak zásadní, vše hlavní a podstatné jsem věděl, takže OK. B-stromy (2012, Dvořák) Napsal sem definici, dukaz logaritmicke vysky ( hrde sem to nazval Veta o logaritmicke vysce Bstromy coz dvorak s usmevem okomentoval ze je to spis takove trivialni pozorovanicko :D ) Pak sem popsal insert a delete. Pak se ptal nato jestli se da insert udelat v jednom pruchodu ( tzn ne ze prvek zatridim a pak vstoupam vzhuru a provadim stepeni preplnenych uzlu...spravna odpoved je delat dopredne stepeni ( kdyz jdu dolu tak plne uzly preventivne rozstepim abych tam mel misto cimz amortizovane zlepsuju slozitost ) Potom A-sort, Redundantni B-stromy, B*-stromy ( tohle vsechno jen v rychlosti...proste chtel vedet ze vim jaka je tam myslenka ) DS - B-stromy + jejich varianty (2010, nějaký teoretik) - Def., operace, složitosti bez žádných větších důkazů. DS - B-stromy a ich varianty (2009, Kopecky) - Napisal som si zakladne definicie B, B+, B* a VB stromov. Pobavili sme sa o redundantych/neredundantych stromoch. Potom o dotazoch na viacero atributov z coho sme sa dostali k hasovaniu a dotazom na ciastocnu zhodu a koncilo to iba otazkou na priestorove data. Tam stacilo povedat, ze je na to dobry R-strom. (Tiez niekde v debate padla otazka na paralelny pristup do B-stromu.) Prijemne aj ked pomerne podrobne sa snazil preverit znalosti. I1/I4 DS - B-stromy (2011, Koubek/Majerech) - Zhruba 2 A4, popis (a,b)-stromu, B-strom jako spec. pripad. Odvozeni log. vysky, neformalne zakl. algoritmy, jejich slozitost, varianty B+, B*, preventivni stepeni a slevani, vyuziti: v databazich, index-sekvencni soubory, A-sort. Ptali se me na to definici (dulezity, ze u korene neplati ta podminka na pocet synu) a pak to zacalo: nejdriv rozdil mezi redudantni a neredudantni verzi a jak se tam lisi delete. :( Nejak jsem nedokazal odvodit, kde je to horsi, pak zacal diskutovat Koubek s Majerechem, ze se to takhle neda poradne rict, ze ta slozitost muze byt v nejhorsim pripade stejna (log n, coz jsem rikal), chvilku se "hadali", pak po me chteli amortizovanou slozitost posloupnosti insertu a deletu - odpoved je, ze to vyjde amortizovane O(1) na operaci, ale dokazat jsem to neumel (pry nejak pres potencial, obdobne jako u Fibonaciho haldy). No a jeste se mne docela pacili, proc jsou ty B-stromy pro databaze lepsi, nez streba BVS - no protoze ja to b muzu zvolit tak, ze pak list ~ stranka na disku. Ale pak me nechali uz zit. Asi jsem uplne neoslnil, ale aby me vyhodili, na to to zas nebylo.

Tato část je neúplná a potřebuje rozšířit. najít další zkazky a doplnit podle nich

• umožňují při daném klíči najít záznam pomocí několika málo operací, na rozdíl od hashování ale i klíče z nějakého intervalu
• nejčastější pro indexy na externí paměti, pomocí "klastrování" odfiltrujeme nerelevantní záznamy

B-strom (redundantni, neredundantni)

setříděný vyvážený m-nární strom s definovanými omezeními větvení (díky nim je rozumně široký)

💡 inserty a delety způsobují pouze lokální změny

pravidla pro neredundatní verzi:

1. kořen má ≥2 syny (pokud není list)
2. ∀vnitřní uzel (mimo kořene) má od ⌈m/2⌉ do m synů
3. ∀uzel má od ⌈m/2⌉-1 do m-1 (poiterů na) datových záznamů
4. ∀větev má stejnou délku
5. uzly vypadají takhle: p₀,(k₁,p₁,d₁),(k₂,p₂,d₂), ... ,(kₙ,pₙ,dₙ),u (p - pointery, k - klíče - řadí se podle nich, d - data/pointery na data)
6. podstromy mají hodnoty klíče mezi klíči z otce

INSERT

💡 v neredundatních se teoreticky dostaneme rychleji k záznamům (ve vnitřních uzlech)

redundatní - mají datové záznamy pouze v listech, takže klíče jsou redundantní ve vnitřních uzlech

Implementace

💡 většinou 1 stránka/blok(8kb) = 1 uzel , tedy arita B-Stromu je okolo 500 a výška se drží okolo 3

INSERT

• najdeme list kam vložit a pokud je plný uděláme split takže každý nový list je z půlky plný
• split můžeme zvýšit počet podstromů otce ⇒ split kaskáda (💡 možná optimalizace: přetékáme do sousedů = vyvažování stránek ⇒ nenastane kaskáda)

DELETE

DELETE

• pokud je po delete uzel méně než z pulky plný mergujeme se sousedem
• merge můžeme snížit počet podstromů otce ⇒ merge kaskáda

Oba algoritmy pracují v O(log N) v nejhorším případě.

B+-stromy (redundantni)

tedy data (pointry na ně) jsou pouze v listech, a listy jsou propojeny pointery (💡 nelistové vyšší úrovně mouhou být také propojeny - např. MSSQL pro intervalové zámky)

• menší vnitřní uzly ⇒ nižší výška (pže uzly mohou být větší) a tj.rychlejší hledání
• INSERT/DELETE jednodušší ⇒ jednodušší implementace (hlavně range queries)

B*-strom (redundantni, neredundantni)

generalizace vyvažování:

• kořen má ≥2 syny (pokud není list)
• ∀větev má stejnou délku
• ∀uzel má alespoň ⌈(2m-1)/3⌉ synů

INSERT/DELETE

• Štěpení se odkládá, dokud nejsou sourozenci plní, potom se štěpí buď 2 do 3. Při odebírání se slévají 3 uzly do 2.

💡 detailněji zde: B-Stromy

staré

;Vícerozměrné B-stromy slajdy Pokorný lze pomocí nich indexovat soubor podle několika atributů současně. celý strom má tolik hladin, kolik je atributů (hlavní strom není B-Strom!) pro každý atribut jsou vytvořeny stromy - pro první jeden, pro druhý tolik, kolik má první atribut různých hodnot atd. U každé hodnoty atributu (uzlu stromu) existuje index na strom s dalším atributem. jednotlivé vrstvy celého stromu jsou indexovány polem Level (vrstva = jeden atribut) - slouží pro přeskočení prvních i atributů, které nebyly v dotazu zadány stromy v jedné vrstvě jsou propojeny do spojáku pomocí NEXT v kořeni, poddoména jednoho stromu je určena pomocí LEFT a RIGHT (uloženy v kořeni), které ukazují do další hladiny na první a poslední strom, který se týká daného stromu. Tedy každý prvek z vrstvy i-1 má ve vrstvě i určeny všechny prvky ve vrstvě i+1, LEFT a RIGHT dává vše. podobná struktura by pravděpodobně šla definovat i pro obecný, nebo jakýkoliv jiný vyhledávací strom. Metody indexace relací relacie mozu byt chapane ako subory, zaznamy suboru ako n-tice relacie, samozrejme su tam rozdiely, napr.: schemy vsetkych relacii sa natiahnu naraz s celou DB, subory musime otvarat/zatvarat jednotlivo indexsekvenční soubor (indexováno jen podle primárního klíče) invertovaný soubor - lze indexovat podle čehokoliv - indexují se přímo záznamy bitová mapa pro atributy malých domén (pohlaví, typ karoserie vozu...) se pro každou doménu vytvoří bitový vektor a jednička tam kde hodnota pro daný řádek platí, tedy vždy jen jedna jednička na řádku => hodně nul, lze dobře komprimovat vyhledávání je rychlé používají se operace AND, OR atd. insertem se všechny vektroy prodlouží, přidáním další možnosti (rozšíření domény) se přidá další bitový vektor lze využívat i pro GROUP BY, COUNT atd. Datové struktury na externí paměti hromada - nehomogenni záznamy (ruzne delky) jsou ukládány za sebou (bez dalších podmínek) - vyhledání čehokoliv = projití celé hromady (v nejhorším případě) sekvenční soubor - podobný jako hromada, jen záznamy jsou pevné délky (homogenni) uspořádaný sekvenční soubor - záznamy uspořádány podle klíče, nově přidávané se ukládají do "souboru aktualizací" a občas je provedena reorganizace, kdy je "soubor aktualizací" vyprázdněn a data z něj zatříděna do uspořádaného sekvenčního souboru. Nalézt záznam lze pak půlením intervalů v case O(log_2(n)). indexsekvenční soubor - obdobně jako předchozí jsou záznamy setříděny podle klíče, navíc existují indexy do jednotlivých bloků (stránek). Indexy jsou tvořeny klíči některých záznamů. Celý index je pak jakýsi B-strom. Při přidávání není index reorganizován, ale je použita oblast přetečení, kam je nový záznam vložen. K záznamu, za který měl být nový záznam vložen se pak uloží číslo bloku i číslo záznamu, kde nový záznam leží. V oblasti přetečení jsou tak vytvářeny lineární seznamy. invertovaný (indexovaný) soubor - indexují se přímo záznamy, ne bloky (jak tomu je v indexsekvenčním souboru), data nejsou v souboru nijak uspořádána, jednotlivé bloky nemusí být na disku za sebou. Indexů může být více různých. Při přidávání není použita další struktura, přímo se upravují indexy. Používá se v DIS (invertovany soubor). ukládání pomocí hashování b-stromy Jiny (urcite lepsi :) popis: Fyzická implementace relačních databází (Databázové systémy) File Organizations (OZD 1) Definice: Klíč schématu relace R je nejmensi mnozina atributů ze schématu R, na níz celá R funkčně závisí. Jakmile tedy máme hodnoty pro klíčové atributy, máme jednoznačné určen libovolný řádek tabulky. Organizace databázových souborů (podle OZD 1) Halda (hromada / heap file) zaznamy maji ruznou delku zaznamy jsou vkladany na konec souboru Sekvenční soubor (sequential file) nesetrideny - halda s pevnou delkou zaznamu setrideny - zaznamy setridene podle klice (narocny INSERT a DELETE) Index-sekvenční soubor (indexed sequential file) index nad jednim klicem je vytvoren je to vlastne primarni soubor se setridenymi daty podle klice + indexovy soubor, ktery muze mit vice urovni indexu Indexový soubor (index file) indexy nad vice klici jsou vytvoreny muze obsahovat primarni index (coz je index nad klicem, podle ktereho je setrideny primarni soubor - asi klastrovany index) a obsahuje sekundarni indexy (asi neklastrovane indexy) Hashovaný / hešovaný soubor (hashed file) pro jeden atribut (asi i klic) existuje hesovaci funkce Vícerozměrné dotazy implementované pomocí hashovacích metod viacrozmerne dotazy - obsahuju viac atributov (n>1) na uplnu zhodu - hodnoty vsetkych n atributov su pevne dane (n=2: MENO='Jiri' AND MESTO='Praha') na ciastocnu zhodu - hodnoty niektorych atributov (<n) su pevne dane na uplnu intervalovu zhodu - pre vsetkych n atributov su dane intervaly hodnot (napr. VEK>22) na ciastocnu intervalovu zhodu - intervaly hodnot su dane len pre niektore atributy implementacia signatury - d bitove binarne retazce signatura zaznamu (dlzky d) je zretazenim signatur jednotlivych atributov, pre kazdy atribut A_i je samostatna hasovacia funkcia h_i, ktora vytvori signaturu dlzky d_i. Plati, ze d_0+d_1+...+d_n=d; n-pocet atributov. Signatura dotazu sa tvori podobne, nezadane atributy su reprezentovane retazcom nul. signatura dotazu Q sa porovnava so signaturami zaznamov S - na pozicii, kde je v Q jednicka, musi byt jednicka aj v S, inak zaznam do odpovede nepatri deskriptory stranok vrstvia sa deskriptory zaznamov v danej stranke pomocou logickeho OR. Deskriptor zaznamu je opat zretazenie deskriptorov atributov A_i, pre kazdy atribut je dana hasovacia funkcia h_i, ktora priradi kazdej hodnote atributu binarny retazec obsahujuci prave 1 jednicku. subor deskriptorov stranok je pripojeny k primarnemu suboru, ak je velky, moze byt dvojurovnovy (prim. subor sa rozdeli do segmentov, kazdy ma svoj subor deskriptorov, tie tvoria 1. uroven; 2. uroven ma deskriptory ukazujuce do 1.) rychlejsie ako signatury, lebo sa musi porovnat menej deskriptorov (ale na ukor pamate); lepsie ako indexovany subor, lebo nerastie cas vyhodnocovania s rastucim poctom atributov v dotaze, pamatove naroky su podobne grayove kody - binarne retazce, hodnoty nasledujuce za sebou sa lisia vzdy len v jednom bite adresa stranky dana signaturou je interpretovana ako grayov kod zaznamy vyhovujuce signature dotazu tvoria zhluky, kde zaznamy su fyzicky za sebou v jednej stranke (alebo viacerych po sebe iducich strankach), nikdy nie je viac pristupov na disku ako u binarneho kodovania dobre pre dotazy na ciastocnu zhodu pri malom pocte zadanych atributov a pre dotazy na intervalovu zhodu Vícerozměrná mřížka Slajdy Pokorný Vícerozměrné stromy

Přístupové metody k prostorovým objektům: R-stromy a jejich varianty (🎓🎓🎓)

Zážitky ze zkoušek

R-stromy (2012, Mlýnková) - Napsal jsem, k čemu jsou dobré, definici a štěpení uzlů dle Guttmana a Greeneové. Dále jsem se zmínil o některých variantách R stromů. Zkoušející se pak jen zeptali na pár otázek. R-Stromy (2010, Pokorný) - Zadefinovať, k čomu slúžia, nákres, štiepenie Gutmann, Green. Rozhovor pokračoval k MOO, MOK - aproximáciám, aké sú výhody jednotlivých prístupov - náročnosť uloženia vs. schopnosť aproximácie. Žiadne detaily, stačilo rozumieť. R+ stromy som len popísal kritériá výberu osi a distribúcie, vravel som, že to kludne na papier dopíšem, ale Pokorný to zjavne nevyžadoval. R-stromy (2009, Skopal) - tuhle otazku jsem tak nejak cekal :-) Bohuzel pan Skopal zkousi pro me dost neprijemnym stylem .. po prvni vete vas dokaze zaskocit nejakou treba i jednoduchou a ne spatne minenou otazkou, na kterou rychle nevite, co odpovedet a pak se do toho tak zamotate, ze zacnete placat nesmysly..on se vas snazi k necemu dokopat, ale kdyz nevite kam presne miri, da se to jen tezko odhadnout..navic z jeho vyrazu nejde vycist, jestli je to jeste v pohode nebo jste na pokraji vyhozeni :-) Nastesti jsem u pana Skopala delal predtim jednu zkousku, tak uz jsem vedel, ze takhle zkousi, ale zas tak zly to neni, jak to v prubehu zkousky vypada...navic me potesilo, ze me nerozebral hned na zacatek uplne a vcas toho nechal..

štěpení uzlu R-Stromu m=3, M=8
dle Guttmana: PickSeeds: největší nevyužitá plocha B,H=44 ∀PickNext ⇒ BDIE, FGHCA	dle Greene: Pick Axis PickSeeds: největší nevyužitá plocha B,H=44 spočteme normované vnitřní vzdálenosti: y: 5/8 x: 3/8 vybereme tu s větší normovanou vzdáleností, tedy y Distribute: setřídíme objekty podle y souřadnice a rozdělíme ⇒ ABCDE, FGIH

Typické dotazy na prostorová data jsou:

• vyhledej bod v prostoru
• vyhledej oblast v prostoru
• vyhledej okolí oblasti (bodu)

R-stromy

💡 obdoba B-stromů pro prostorové objekty (ale hledání může jít současně více cestami)

• ∀uzel E má m až M synů (až na kořen - má aspoň 2 syny) a platí: m ≤ M/2
  • E.p - identifikátor prostorového objektu (listy) nebo pointer na syna
  • E.I - MBR (minimum bounding rectangle) - minimální ohraničující obdélník (MOO)

    💡 n-dimensionální: MBB (minimum bounding box) - minimální ohraničující kostka (MOK)

    💡 jednotlivé oblasti se mohou překrývat

• všechny cesty v R-stromu jsou stejně dlouhé (listy na stejné úrovni) ≤ logₘ n

INSERT - štěpení uzlu při jeho M+1 přeplnění (hledám co nejmenší využití prostoru)

Guttman (kvadratická verze, lin.dává horší výsledky)

• PickSeeds - vybrat dvojici prvků s největší nevyužitou plochou

💡 napáchaly by největší škodu, pokud bychom je dali do stejné skupiny

• ∀(zbývající uzel) PickNext - postupně k nim přiřazujeme zbylé prvky aby přírustek nev.plochy byl co nejmenší
  • |přírustek k původnímu MBR 1.skupiny pomocí dalšího uzlu - přírustek pův. MBR 2.skupiny pomocí stejného uzlu|
  • vybereme maximální rozdíl (💡 tj.přidání do op. skupiny by napáchalo největší škodu)

Greenová (snažíme se odstranit překrytí listů - při štěpení vyberem jednu z os)

ChooseAxis (=modifikace Guttmana)

• PickSeeds - z Guttmana
• ∀ osu a MBR(2 prvků) spočti maximální normalizovanou vzdálenost (💡 vnitřní vzdálenost vydělím hranou MBR 2 prvků v dané ose)

  → vyberu osu s největší normalizovanou vzdáleností

• Distribute - větší půlka ⌈(M+1)/2⌉ se hodí do jednoho uzlu a zbytek do druhého uzlu.

💡 ne vždy je nalezena vhodná osa – může vést ke špatným výsledkům

R+-stromy

• vnitřní (nelistové) MBR uzly se nepřekrývají ⇒ měně větvení dotazu ALE více dělení a větší výška než R-Stromy
• přiřazuje prostorové objekty do všech listů, do kterých zasahují (tj. odkaz na objekt duplikován)
• u uzlů není zaručena minimální zaplněnost

štěpení uzlu R*-Stromu m=3, M=8 (jako nahoře)
	ChooseSplitAxis seradime podle osy y a počítáme h-okraje Celkem: 184 seradime podle osy x a počítáme h-okraje Celkem: 182 vybereme tu s menší hodnotou, tedy x ChooseSplitIndex - počítáme h-překryv když jsou 2 nejmenší stejné tak i h-objem zase vybereme nejmenší a podle nich rozdělíme ⇒ FAHCG, EIBD

R*-stromy

• více optimalizačních kritérií oproti R-stromům – minimalizují pokrytí a překrytí pomocí okraje
• rozdíl od R-Stromů: algoritmem na rozdělení přetečené stránky, bere v úvahu více trideni podle os, při přetečení provádí reinsertování, taky algoritmem na hledání listu pro insert (overlap místo nejmenšího rozšíření)
• při INSERTu se v předposlední úrovni vybírá takový list, kde když bude, tak celá ta množina bude mít nejmenší překrytí s ostatními množinami (dalšími listy), ve vyšších úrovních se vybírá uzel, který způsobí nejmenší zvětšení prostoru (jako u R-stromů)
• Split_RS - štěpení
  • prvky se setřídí do 2 skupin podle osy x1 a x2
    • ∀setřídění jsou vytvořeny všechny kombinace rozdělení prvků tak, aby v 1. skupině bylo aspoň (m-1)+k prvků
  • ChooseSplitAxis - ∀osu se dle ní setřídí prvky a spočítá suma margin-value všech distribucí v dané ose a vybere se osa s nejmenší (margin-value sumou)
  • ChooseSplitIndex - v této ose se vybere distribuce s nejmenší overlap-value, pokud se rovnají menší area-value
    • area-value (h-objem) - součet obou MBR distribucí
    • margin-value (h-okraj) - součet okrajů – ve 2D obvod MBR, ve 3D ohraničující plocha MBB distribucí
    • overlap-value (h-překrytí) - překrytí obou MBR distribucí
  • rozdělíme prvky do 2 distribucí
• Forced Reinsert
  • ∀prvky nodu N sestupně setřid podle vzd. od středu MBR
  • prvních p prvků odstraň z N a pak je znova insertuj

další stromy

další: radix (r^d) stromy uvažujme r=2, d=2 rozděluje plochu na 4 čtverce a každý čtverec je reprezentován uzlem stromu, a rekurzivně je dále členěn. Objekt může být uložen v mnoha listech. Strom může být nevyvážený. vhodné pouze pokud se celé vejdou do vnitřní paměti organizace prostoru – číslování do šířky, adresování cestou, z-uspořádání (peanova křivka), naivní uspořádání, spirálové uspořádání, hilbertova křivka (všechny po sobě jdoucí buňky jsou sousední v prostoru) – volbu organizace je vhodné přizpůsobit datům, pro čtvercové oblasti je vhodné spirálové uspořádání, pro obdélníky je vhodné naivní uspořádání ve směru delší strany K-D-stromy binární strom – ve vnitřím uzlu je osa podle níž se prostor půlí, v listech jsou B-kostky Buddy-stromy nepokrývají (nutně) celý prostor vhodné pro ukládání bodů (pokud chci složitější struktury je potřeba zdvojnásobit dimenzi a ukládat zvlášť dolní a zvlášť horní mez) při slévání se slévají dvě stránky, ale výsledné dělení musí být opět B-dělením (lze k němu dojít pomocí půlení prostoru) – slévat lze kostky, které jsou v poloze „buddy“ – tj. ohraničující kostka sjednocení těchto kostek má s ohraničujícími kostkami ostatních kostek v uzlu prázdný průnik prostorové spojení motivace: najdi všechny lesy v daném městě – uvažujme jakoby databázi s tabulkou lesů (id_lesu, název_lesu, území) a tabulkou města (id_města, název, území), snahou je vytvořit predikát, který bude fungovat jako spojení v relačních DB – nejčastěji by měl vracet dvojice, které mají neprázdný průnik (ale lze uvažovat i jiné predikáty) výsledkem spojení může být buď konkrétní průnik, nebo pouze ukazatele na překrývající se objekty (tzv. Id-spojení) prostorové spojení pomocí hnízděných cyklů obdoba spojení pomocí setřízení a porovnávání jako u relačních DB není možná prostorové objekty nelze jednoznačně uspořádat do 1 dimenze, jedinou variantou jsou tak hnízděné cykly (porovnají se všechny prvky z tabulky A se všemi z tabulky B) – to je náročné a tak se pokusíme optimalizovat: spočítá se spojení MOO těch objektů (kandidáti na správné hity) pomocí kvalitnějších aproximací se provede filtrace na jisté hity, jisté chybné hity a nerozhodnuté dvojice nerozhodnuté dvojice se rozhodnou pomocí přesné geometrie prostorové spojení pomocí z-uspořádání vytvoří se mřížka, políčka se očíslují pomocí z-uspořádání (Peanova křivka), objekt je potom aproximován množinou z-hodnot, při porovnávání objektů lze hledat z-hodnotu jednoho objektu mezi z-hodnotami druhého objetku prostorové spojení pomocí R-stromů nechť jsou prostorové relace uloženy v R-stromech, postupným procházením stromů je možné eliminovat řadu uzlů, protože mají prázdný průnik zametací algoritmus dvě prostorové relace (uvažujme 2D, obdélník, ev. MOO), každý obdélník je definován svým levým dolním a pravým horním rohem, provedu projekci do jedné osy, najdu obdélník s nejmenší x1 (z obou relací), nechť je to obdélník S1, nyní hledám všechny obdélníky z druhé relace (R), které mají ri.x1 menší než s1.x2. Pokračuji výběrem dalšího obdélníku, ale S1 již neuvažuji (nebude mít průnik s žádným dalším obdélníkem)

další zdroje
zapsáno podle: http://siret.ms.mff.cuni.cz/members/hoksza/lectures/ndbi003 viz wen:R-Tree

Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace (🎓)

Zážitky ze zkoušek
IDS - Vektorovy a boolovsky model (Kopecky) - princip, tvar dotazu a odpovede, implementacia