■ ■ PA152: Efektivní využívání DB 4. Indexování Vlastislav Dohnal Poděkování ■ Zdrojem materiálů tohoto předmětu jsou: D Přednášky CS245, CS345, CS345 ■ Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer Widom ■ Stanford University, California PA152, Vlastislav Dohnal, Fl MUNI, 2009 2 Indexování klíč soubor záznam Důvod: rychlejší přístup k záznamům d než sekvenční průchod souborů Varianty: d Konvenční indexy d B-stromy D Hašování PA152, Vlastislav Dohnal, Fl MUNI, 2009 3 Základní pojmy ■ Sekvenční soubor d Index sekvenční soubor ■ Vyhledávací klíč d Primárni klíč ■ Index d Primárni index d Sekundárni index d Hustý index d Řídký index d Víceúrovňový index PA152, Vlastislav Dohnal, Fl MUNI, 2009 Soubor Sekvenční soubor Index-sekvenční soubor 11) 20 30 40 50 60 70 80 90 100 10 30 50 70 10 20 30 40 50 60 70 80 90 100 PA152, Vlastislav Dohnal, Fl MUNI, 2009 Index Položka indexu: d klíč, odkaz na záznam/blok Hustý index 50 60 70 80 Řídký index 10 30 50 70 PA152, Vlastislav Dohnal, Fl MUNI, 2009 6 Index (2) ■ Víceúrovňový index 2. úroveň 10 50 \| 1. úroveň 10 20 50 60 70 80 Soubor 10 20 30 40 50 60 70 80 Lze mít indexy vyšších úrovní husté? PA152, Vlastislav Dohnal, Fl MUNI, 2009 7 Index (3) ■ Ukazatele v indexech d Ukazatel na blok ■ Adresa bloku ■ Obvykle kratší D Ukazatel na záznam ■ Adresa bloku + offset záznamu D Soubor je spojitý a uspořádaný ■ Ukazatele na bloky se nemusí ukládat i Lze je spočítat PA152, Vlastislav Dohnal, Fl MUNI, 2009 Výpočet ukazatele na blok ■ Blok o velikosti 1 KB ■ Chceme přistoupit Index blok B3: d Offset v souboru: D (3-1)-1024=2048 KÍ K2 K3 K4 Soubor Bi B2 B3 B4 PA152, Vlastislav Dohnal, Fl MUNI, 2009 9 Duplikátní klíče ■ Vytvoření indexu d hustý index? d řídký index? Soubor 10 10 10 20 20 30 30 30 40 45 PA152, Vlastislav Dohnal, Fl MUNI, 2009 10 Duplikátní klíče: hustý index ■ Duplicity v indexu 10 10 10 20 20 30 30 30 40 45 Soubor 10 10 10 20 20 30 30 30 40 45 PA152, Vlastislav Dohnal, Fl MUNI, 2009 11 Duplikátní klíče: hustý index (2) ■ Klíče v indexu jsou unikátní Soubor 10 20 30 40 45 \ 10 10 10 20 20 30 30 30 40 45 PA152, Vlastislav Dohnal, Fl MUNI, 2009 12 Duplikátní klíče: řídký index ■ Odkazy na bloky 10 10 20 30 40 Vyhledávání záznamů!!! DNapř. klíč 20 Soubor 10 10 10 20 20 30 30 30 40 45 PA152, Vlastislav Dohnal, Fl MUNI, 2009 13 Duplikátní klíče: řídký index (2) ■ V indexu je vždy nový klíč Zrušit tuto ^> položku? 10 20 30 30 40 Soubor 10 10 10 20 20 30 30 30 40 45 PA152, Vlastislav Dohnal, Fl MUNI, 2009 14 Mazaní v indexech Řídký index D Smazání záznamu s klíčem 40 10 30 50 \ 70 PA152, Vlastislav Dohnal, Fl MUNI, 2009 Mazání v indexech: výsledek ■ Řídký index D Po smazání záznamu s klíčem 40 10 30 50 \ 70 10 20 30 TU 50 60 70 80 PA152, Vlastislav Dohnal, Fl MUNI, 2009 16 Mazaní v indexech Řídký index D Smazání záznamu s klíčem 30 10 30 50 \ 70 PA152, Vlastislav Dohnal, Fl MUNI, 2009 Mazání v indexech: výsledek ■ Řídký index D Po smazání záznamu s klíčem 30 ■ Aktualizace indexu 10 20 40 50 60 70 80 PA152, Vlastislav Dohnal, Fl MUNI, 2009 18 Mazaní v indexech Řídký index D Smazání záznamů s 30 a 40 10 30 50 \ 70 PA152, Vlastislav Dohnal, Fl MUNI, 2009 Mazaní v indexech: výsledek ■ Řídký index D Po smazání záznamů s 30 a 40 ■ Aktualizace indexu 10 50 V 70 * 10 I 20 "fŠfr ^^^\ láe- ^^^ * 50 I 60 1 70 80 PA152, Vlastislav Dohnal, Fl MUNI, 2009 Mazání v indexech ■ Hustý index - vždy aktualizace indexu D Smazání záznamu s klíčem 30 10 20 30 40 50 60 70 80 10 •20 30 40 50 60 70 80 PA152, Vlastislav Dohnal, Fl MUNI, 2009 21 Mazání v indexech: výsledek ■ Hustý index D Po smazání záznamu s klíčem 30 10 20 40 50 60 70 80 10 •20 40 50 60 70 80 PA152, Vlastislav Dohnal, Fl MUNI, 2009 22 Vkladaní v indexech Rídký index D Vložení záznamu s klíčem 34 ■ Volné místo -> bez reorganizace PA152, Vlastislav Dohnal, Fl MUNI, 2009 Vkladaní v indexech Rídký index D Vložení záznamu s klíčem 15 ■ Volné místo není -> reorganizace PA152, Vlastislav Dohnal, Fl MUNI, 2009 Vkladaní v indexech Rídký index D Vložení záznamu s klíčem 15 ■ Volné místo není -»reorganizace ■ Řešení pomocí přesunu do sousedního bloku D Alternativa: vytvoř nový blok PA152, Vlastislav Dohnal, Fl MUNI, 2009 Vkladaní v indexech Rídký index D Vložení záznamu s klíčem 25 ■ Volné místo není -> reorganizace PA152, Vlastislav Dohnal, Fl MUNI, 2009 Vkladaní v indexech Řídký index D Vložení záznamu s klíčem 25 10 30 40 60 Volné místo -»reorganizace Řešení pomocí přetokových bloků Reorganizace je provedena později 10 20 30 40 50 60 PA152, Vlastislav Dohnal, Fl MUNI, 2009 Vkládání v indexech ■ Hustý index D Vložení záznamu ■ Vždy i do indexu ■ V souboru stejné problémy jako u řídkého indexu PA152, Vlastislav Dohnal, Fl MUNI, 2009 28 Sekundární index ■ Soubor je uspořádaný podle jiného klíče ■ Vybudovaný na jiném než „primárním" klíči ■ Volba typu: d Hustý nebo řídký? PA152, Vlastislav Dohnal, Fl MUNI, 2009 29 Sekundární index 10 50 90 ■ ■ ■ Řídký pro vyšší úrovne 50 60 70 ■ ■ ■ Hustý inde Vždy odkazy na záznamy! Klíc pro uspořádaní \ 30 50 20 70 80 40 100 10 90 60 PA152, Vlastislav Dohnal, Fl MUNI, 2009 30 Duplikátní klíče: sekundární index ■ Replikace v indexu D Zvýše n í ■ Přístupového času (access time) ■ Diskových nároků 40 40 ■ ■ ■ 40 30 40 10 ^ / ^ 20 10 10 X / 10 20 20 20 30 40 40 10 40 PA152, Vlastislav Dohnal, Fl MUNI, 2009 31 Duplikátní klíče: sekundární index 2 ■ Indexová položka má seznam ukazatelů d Problém variabilní délky položky 20 10 110 \j | 20 20 40 10 40 30 40 10 40 30 40 PA152, Vlastislav Dohnal, Fl MUNI, 2009 32 Duplikátní klíče: sekundární index 3 Variabilita přesunuta do „kyblíku" 10 20 30 40 50 60 ■ ■ ■ buckets 20 10 20 40 10 40 10 40 30 40 PA152, Vlastislav Dohnal, Fl MUNI, 2009 33 Duplikátní klíče: sekundární index 4 ■ Vhodnost nepřímého odkazu na záznam dTj. „kyblíků" ■ Příklad: d Relace zaměstnanec(jméno, oddělení, dveře) D Indexy: ■ Jméno - primární ■ Oddělení - sekundární ■ Dveře - sekundární PA152, Vlastislav Dohnal, Fl MUNI, 2009 34 Duplikátní klíče: sekundární index 5 ■ Dotaz: zaměstnanci hraček v místnosti DV243 Oddělení (index) Soubor Dveře (index) Průnik kyblíků d Máme seznam ukazatelů na správné zaměstnance d Technika používaná v information retrieval PA152, Vlastislav Dohnal, Fl MUNI, 2009 35 Konvenční indexy: shrnutí ■ Základní dělení d Řídké vs. Husté ■ Vkládání / mazání d Duplikátní klíče ■ Sekundární indexy ■ Výhody d Jednoduché d Index je sekvenční soubor -» vhodné pro „full scan" ■ Nevýhody d Aktualizace drahé d Ztráta „sekvenčnosti" a vyváženosti ■ kvůli přetokovým oblastem PA152, Vlastislav Dohnal, Fl MUNI, 2009 36 B-stromy ■ Jiný typ indexu D Sekvenční uspořádání není nutné D Garance I/O pro přístup (vyváženost) ■ Více variant D B-strom, B+-strom, B*-strom, ... ■ Často se při vylovení „ B-strom" myslí „ B+-strom"\ ■ Původ D Rudolf Bayer and Ed McCreight invented the B-tree while working at Boeing Research Labs in 1971 (Bayer & McCreight 1972) ■ They did not explain what, if anything, the B stands for. ■ Douglas Comer explains: The origin of "B-tree" has never been explained by the authors. As we shall see, "balanced," "broad," or "bushy" might apply. Others suggest that the "B" stands for Boeing. Because of his contributions, however, it seems appropriate to think of B-trees as "Bayer"-trees. * Source: Wikipedia PA152, Vlastislav Dohnal, Fl MUNI, 2009 37 B+-strom ■ Příklad n-4 o o o " rsFLD/OO y&-\ i—1/ i—l f n u ^; H -------► O u PO c 1 r i r i r 1 r i r O ^H O O O ^H 1—1 1—1 1—1 ---------» o o fM 00 i—i i—i —► O KD m m n i—i i—i i—i ^ r i r y f i f i r ▼ T T 00 o CM ▼ T PA152, Vlastislav Dohnal, Fl MUNI, 2009 38 B+-strom ■ Vnitřní uzel pro n=4 / 1^ i-l LO A in/ to keys to keys < 57 57< k<81 00 to keys to keys 8195 PA152, Vlastislav Dohnal, Fl MUNI, 2009 39 B+-strom Listový uzel pro n=4 From non-leaf node /____________i to next leaf in sequence o >* o >* o >* U CD u -'5 1-5 PA152, Vlastislav Dohnal, Fl MUNI, 2009 40 B+-strom ■ Parametr n (arita stromu) ovlivňuje: D Tvar uzlu: Pí «1 P2 K2 P3 Kn-1 Pn D Minimální naplnění d Listový uzel ■ Vždy na stejné úrovni ■ Pj odkazuje na záznam s klíčem K, (data) ■ pn odkazuje na další list (zřetězení listů) D Nelistový uzel ■ p, odkazuje na uzel, kde jsou klíče K: KM < K < Kj PA152, Vlastislav Dohnal, Fl MUNI, 2009 41 B+-strom ■ Podmínky naplnění Max ukazatelů Min ukazatelů Max klíčů Min klíčů Vnitřní uzel | (ne kořen) n (potomků) ľn/2l (potomků) n-1 Tn/2l-1 Vnitřní uzel | (kořen) n (potomků) 2 (potomků) n-1 1 List | (ne kořen) n-1 (záznamů) T(n-1)/2l (záznamů) n-1 (záznamů) T(n-1)/2l (záznamů) List | (kořen)______ n-1 (záznamů) 0 (záznamů) n-1 (záznamů) 0 (záznamů) PA152, Vlastislav Dohnal, Fl MUNI, 2009 42 19 B+-strom: vkládání ■ Růst od listu ke kořenu ■ Nalézt listový uzel a vložit klíč (s odkazem na záznam) d Popř. aktualizovat rodiče ■ Případy: a) Bez reorganizace (snadné) ■ V listu je volné místo b) Štěpení listu c) Štěpení vnitřního uzlu d) Nový kořen PA152, Vlastislav Dohnal, Fl MUNI, 2009 (a) Insert key = 32 en LO PA152, Vlastislav Dohnal, Fl MUNI, 2009 44 (b) Insert key = 7 en lo o i-i en en PA152, Vlastislav Dohnal, Fl MUNI, 2009 45 (c) Insert key = 160 O VO LD LO i O 00 00 O i-i r\i PA152, Vlastislav Dohnal, Fl MUNI, 2009 46 (d) New root, insert 45 n=4 rsi en new root PA152, Vlastislav Dohnal, Fl MUNI, 2009 47 B+ n=3 -strom: štěpení listu , vkládáme 6 i—i--------------1—i--------------1—i 6 1. | 1 3 |*|-»| | 5 | | 7 || | 2. 13 \\^\ 5 6 |*f-»| | 7 | | 3. 111 H 3 |»f->| 5 6 4~H 7 n PA152, Vlastislav Dohnal, Fl MUNI, 2009 48 1 B+-strom: štěpení vnitřního uzlu n=3, vkládáme 4 3. 4. % 4 ,T ^ 4 >l I 5 I I 6 !+->! I 7 5 / »I I 5 II 6 !+-»! I 7 / \l \ \ PA152, Vlastislav Dohnal, Fl MUNI, 2009 49 B+-strom: mazání ■ Nalézt listový uzel a smazat klíč (s odkazem na záznam) d Popř. smazat list, ... ■ Případy: a) Bez reorganizace (list není „podplněn") b) Přesun do souseda a smaž uzel c) Přesuny mezi sousedy (bez mazání uzlu) d) Ad (b) a (c) pro vnitřní uzly PA152, Vlastislav Dohnal, Fl MUNI, 2009 50 (b) Coalesce with sibling D Delete 50 PA152, Vlastislav Dohnal, Fl MUNI, 2009 51 (c) Redistribute keys D Delete 50 PA152, Vlastislav Dohnal, Fl MUNI, 2009 52 (d) Non-leaf coalesce D Delete 37 new root- o o i-i r\ľ rsi en o <šľ PA152, Vlastislav Dohnal, Fl MUNI, 2009 53 B+-strom: mazání ■ Praxe: d Často nejsou přesuny mezi sousedy implementovány d Příliš složité a nemá velké efekty PA152, Vlastislav Dohnal, Fl MUNI, 2009 54 B+-strom vs. index-sekvencni soubor ■ Kapacita bloku (512 bajtů) d Statický index - implicitní indexy, 127 klíčů DB+-strom - 63 klíčů, tj. 64 potomků ■ Počet datových bloků v indexu: D2-úrovně: statický < 127, B+-strom < 64 D3-úrovně: statický < 16129, B+-strom < 4096 ■ Závěr: d B+-strom potřebuje více místa DB+-strom má složitější zamykání d Statický index vyžaduje reorganizace PA152, Vlastislav Dohnal, Fl MUNI, 2009 B+-strom vs. index-sekvenční soubor ■ Závěr (pokračování): D DB neví kdy reorganizovat! ■ B+-strom provádí pouze malé lokální reorganizace ■ Statický index provádí velké reorganizace D Buffer manager ■ B+-strom má fixní nároky (log hloubka) ■ Statický index nikoli! d Kvůli přetokovým oblastem ■ LRU není pro B+-strom vhodný! ■ B+-strom je vhodnější organizace. PA152, Vlastislav Dohnal, Fl MUNI, 2009 56 B-strom (pozor bez +) ■ Neduplikovat klíče d-> odkazy na záznamy i ve vnitřních uzlech d Podmínky pro klíče v podstromech jsou jiné Kl Pl r to record with K1 K2 P2 K3 P3 to record with K2 to record with K3 to keys k3 PA152, Vlastislav Dohnal, Fl MUNI, 2009 57 B-strom: příklad Zřetězeni listu jiz nelze využit n=3 ID ID # LO 00 LO 1 Br&rB. t LO LO v fM co ^r LO KD O O l^ 00 c5mo oL/o cs|/o Sí rsi o no ^1" LO KD o o 1^ 00 tt tt tt tttt tt tttttt PA152, Vlastislav Dohnal, Fl MUNI, 2009 58 B-strom ■ Podmínky naplnění Max ukazatelů Min ukazatelů Max klíčů (záznamů) Min klíčů (záznamů) | Vnitřní uzel | (ne kořen) n ľn/2l n-1 Tn/2l-1 Vnitřní uzel | (kořen) n 2 n-1 1 List | (ne kořen) n-1 (záznamů) Rn-1)/2l (záznamů) n-1 Rn-1)/2l List | (kořen)______ n-1 (záznamů) 0 (záznamů) n-1 0 PA152, Vlastislav Dohnal, Fl MUNI, 2009 59 19 Porovnání B-stromu a B+-stromu ■ Velikosti DBIok=100bajtů d Ukazatel = 4 bajty d Klíč = 4 bajty ■ Uvažujme vždy plný 2-úrovňový strom d 1 kořen a pak listy d Každý uzel v jednom bloku PA152, Vlastislav Dohnal, Fl MUNI, 2009 60 Porovnaní: B-strom ■ Kořen: d 8 klíčů + 8 ukazatelů na záznam d 9 ukazatelů na potomka D8-4 + 8-4 + 9-4 = 100bajtů ■ List: d 12 klíčů + 12 ukazatelů na záznam Dl2-4 + 12-4 = 96bajtů ■ Počet záznamů: D8 + 9 ■ 12 = 116 záznamů PA152, Vlastislav Dohnal, Fl MUNI, 2009 Porovnaní: B+-strom ■ Kořen: d 12 klíčů, 13 ukazatelů na potomka D12-4 + 13-4 = 100 bajtů ■ List: d 12 klíčů + 12 ukazatelů na záznam D12- 4 + 12 -4 = 96 bajtů ■ Počet záznamů: D13 ■ 12 = 156 záznamů PA152, Vlastislav Dohnal, Fl MUNI, 2009 Porovnání: výsledek ■ Počet čtení z disku: D B-strom ■Pletení = 8/116, P2čtení= 108/116 D B+-strom ■P2čtení=156/156 ■ Ale: B-strom se 156 záznamy má 3 úrovně d 1 .úroveň - 8 klíčů, 2.úroveň - 9-8=72, 3.úroveň - 76 klíčů DP1čtení = 8/156,P2čtení = 72/156 a P3 čtení = 76 /156 PA152, Vlastislav Dohnal, Fl MUNI, 2009 63 Porovnání: závěr ■ B-stromy D+ Ve vyhledávání rychlejší ■ Ne vždy platí (viz předchozí příklad) D- Různé struktury vnitřního a listového uzlu D- Mazání je obtížnější na implementaci ■^ B+-stromy jsou preferovány! PA152, Vlastislav Dohnal, Fl MUNI, 2009 64 B+-strom ■ B+-strom jako soubor D viz Organizace souborů PV062 ■ Duplicitní klíče d Odkazy na záznamy -» odkazy na bloky (buckets) ■ tam je seznam záznamů se stejnou hodnotou ■ Klíče jsou variabilní délky (např. řetězce) d Ukládat celé -> nízká arita a další potíže d Používá se prefix (prefix compression) PA152, Vlastislav Dohnal, Fl MUNI, 2009 65