A Tutorial
.
Indexing structures in RDBMs
.
George J. Klir State University of New York (SUNY) Binghamton, New York 13902, USA
[email protected] Vilem Vychodil (Palacky University, Olomouc)
Palacky University, Olomouc, Czech Republic
!
prepared for International Centre for Information and Uncertainty, Palacky University, Olomouc
! !
! Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
1 / 31
Přehled seminářů
28. listopadu
5. prosince
12. prosince
Vychodil V. (DAMOL)
Vilém Vychodil Indexing structures in RDBMs
Vilém Vychodil Query execution algorithms in RDBMs
Ondřej Vaverka Survey of rank-aware approaches
Indexing structures in RDBMs
Nov 28, 2013
2 / 31
Přehled . Organizace dat v relační databázi:
1
pole, záznamy, soubory organizace dat do bloků, typy databázových souborů.
. B-stromy a jejich modifikace:
2
základní fakta vlastnosti vnitřních a listových uzlů, vkládání a mazání hodnot.
. Rozšiřitelné hashovací tabulky:
3
základní principy, hashovací funkce, sloty, stránky, vkládání a mazání hodnot.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
3 / 31
Fyzická implementace základních pojmů z RM vycházíme z pojmu (logická vrstva): relace nad relačním schématem relační schéma = konečná množina atributů a jejich typů (domén) n-tice = zobrazení přiřazující atributům hodnoty jejich typů relace = konečná množina n-tic nad daným schématem na fyzické vrstvě musí SŘBD (efektivně) řešit: jak kódovat jména atributů a jejich typy jak kódovat relační schémata jak kódovat n-tice nad relačními schématy jak reprezentovat relace
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
4 / 31
Pole, záznamy, soubory pole: sekvence bytů (s pevnou nebo pohyblivou velikostí) kóduje hodnoty atributů (tj. hodnoty daných typů) záznam: sekvence polí kóduje n-tice relací záznamy jsou ukládány do diskových bloků (stránek paměti) třeba udržovat hlavičku záznamu (informace o pořadí, jménu a typu položek) soubor ( jiný význam než v op. syst.): množina bloků obsahující záznamy stejného typu kóduje relaci nad daným schématem uvažujeme nesetříděný / setříděný Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
5 / 31
Pole typy kódování atributů daných typů: 1. hodnoty s pevnou velikostí kódu: 8B signed integer (little endian), 8B IEEE 754 double (binary64), 1B ASCII character, dvojice hodnot typu double (kódující bod v rovině), pravdivostní hodnoty, řetězce s omezenou délkou, znaky UTF-8, UTF-16, výčtové typy, .. .
. hodnoty s pohyblivou velikostí kódu:
2
řetězce bez omezené délky (styl kódování C a/nebo PASCAL), další objekty (obrázky, videa), .. .
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
6 / 31
Záznam struktura záznamu: zřetězení jednotlivých polí dodatečná informace (hlavička): (ukazatel na) schéma záznamu délka záznamu časové značky (timestamps) kvůli synchronizaci a souběžnému přístupu
typická organizace polí: pole s pevnou délkou jsou řazena jako první následují pole s pohyblivou délkou (délka je zaznamenána v hlavičce)
ukazatel na schéma a další informace
Vychodil V. (DAMOL)
délka záznamu
•
. ID
BIRTHDATE
Indexing structures in RDBMs
NAME
ADDRESS
Nov 28, 2013
7 / 31
Záznamy a přetečení bloku problém přetečení bloku záznam se nevejde do aktuálního bloku pokud je záznam menší než blok, je možné alokovat jej v jiném bloku (fragmentace) pokud je záznam větší než blok, je rozdělen do několika bloků
udržovaná informace: hlavička záznamu obsahuje příznak: záznam je celý / jedná se o fragment pokud je fragment, jsou zaznamenány další údaje: ukazatel na předchozí fragment ukazatel na další fragment
alternativa: velké objekty (BLOBy) se udržují ve skupině (souvislých) bloků pole záznamu pro daný BLOB obsahuje adresy (tabulku adres) bloků
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
8 / 31
Typy databázových souborů nesetříděné soubory: typicky: perzistentní halda rychlé operace: vkládání, mazání pomalé operace: restrikce, modifikace (update) setříděné soubory: soubor je udržován jako setříděný pomocí primárního indexu typicky: perzistentní vyhledávací strom rychlé operace: restrikce (a další relační operace) za pomocí indexu pomalé operace: přidávání, mazání a modifikace dat (vše ostatní) primární × sekundární indexy: sekundární indexy – pomocné indexy podporující často prováděné dotazy problémy s reindexací Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
9 / 31
B+ -stromy B-stromy: rodina vyvážených stromů (různé modifikace) vlastnosti: automaticky udržují potřebné množství úrovní indexů, kolik je potřeba pro data daného rozsahu spravují záznamy v blocích tak, že každý blok je nejvýš z poloviny prázdný implementační aspekty: perzistentní struktury uzly B-stromů mají velikost celého bloku (několika bloků) rozdíl oproti BVS – uzly typicky obsahují několik (desítek) klíčů Bayer R., McCreight, E.: Organization and Maintenance of Large Ordered Indexes. Acta Informatica 1 (3): 173–189 (1972)
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
10 / 31
Základní požadavky na B+ -stromy parametr: n (přirozené číslo) n určuje počet možných klíčů a ukazatelů v každém uzlu stromu počet klíčů je n počet ukazatelů je n + 1
v praxi se n určuje z velikosti bloku, záznamů a ukazatelů základní podmínky, které musejí být splněny: 1. vyhledávací klíče v listových uzlech jsou kopie hodnot z datového souboru . vyhledávací klíče v listových uzlech se nacházejí setříděné zleva-doprava 3. ukazatele v listech ukazují přímo na záznamy v datovém souboru 2
. ukazatele ve vnitřních uzlech ukazují na další uzly stromu 5. kořenový uzel má vždy aspoň dva ukazatele 4
(až na triviální případ, kdy indexujeme pouze jednu hodnotu, pak je kořen zároveň list) Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
11 / 31
Listové uzly B+ -stromů listové uzly: poslední ukazatel ukazuje na další listový uzel v řadě (hodnoty uspořádané podle klíčů lze pohodlně procházet) ostatní ukazatele ukazují na záznamy (zakódované n-tice) nejméně ⌊ n+1 2 ⌋ ukazatelů (kromě posledního) je využito (i-tý ukazatel ukazuje na záznam i-tého klíče) nevyužité ukazatele jsou napravo od využitých příklad: pro n = 3 . 43 23 31 •
•
Vychodil V. (DAMOL)
•
. 44 58 •
•
•
. 79 67 78 •
Indexing structures in RDBMs
•
•
•
•
Nov 28, 2013
12 / 31
Vnitřní uzly B+ -stromů vnitřní uzly: všech n + 1 ukazatelů může ukazovat na uzly stromu na nižších patrech nejméně ⌊ n+1 2 ⌋ ukazatelů je použito (s výjimkou kořene) pokud je použito j ukazatelů, v uzlu je zapsáno j − 1 klíčů s následujícím významem: pro ukazatele P1 , . . . , Pj a klíče K1 , . . . , Kj−1 platí: P1 ukazuje na uzel, kde jsou klíče ostře menší než K1 Pi (2 ≤ i < j) ukazuje na uzel, kde jsou klíče z intervalu [Ki−1 , Ki ) Pj ukazuje na uzel, kde jsou klíče větší nebo rovny Kj−1
nevyužité ukazatele jsou napravo od využitých . 43 23 31 •
k < 23 Vychodil V. (DAMOL)
23 ≤ k < 31
•
•
• 31 ≤ k < 43
Indexing structures in RDBMs
43 ≤ k Nov 28, 2013
13 / 31
Příklad B+ -stromu pro n = 3 .
13
•
•
7
•
2
•
3
•
23 31 43
•
•
5
•
7 11
•
•
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
14 / 31
Využití B+ -stromů v relačních databázích typické využití: 1. implementace primárního klíče (hustý index) . implementace řídkého indexu v setříděném souboru
2
vyhledávání jedné hodnoty v B+ -stromu: zobecnění principu vyhledávání z BVS vyhledávání hodnoty začíná v kořenu pokud jsme v listovém uzlu, vyhledáme konkrétní hodnotu (binární vyhledávání) pokud jsme ve vnitřním uzlu, sestoupíme o patro níž, které odpovídá intervalu hodnot, do kterého padne aktuální hodnota (binární vyhledávání) vyhledávání intervalů hodnot v B+ -stromu: nalezneme hodnotu odpovídající dolní mezi intervalu (nebo listový uzel, ve kterém by hodnota měla být) postupujeme zleva-doprava, dokud nenarazíme na horní mez intervalu Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
15 / 31
Modifikace B+ -stromů: Vkládání základní schéma: nalezneme listový uzel, do kterého bychom chtěli vložit hodnotu klíče (pokud je v listu místo, úloha je triviální) pokud v daném listovém uzlu není místo (uzel je zaplněný), potom rozdělíme daný uzel na dva uzly, které jsou z poloviny zaplněné vkládaný klíč a hodnota bude v jednom ze dvou vzniklých uzlů potřeba propagovat změnu směrem k rodičovskému uzlu (rozdělení listu znamená přidat jeden klíč do rodiče) pokud je rodičovský uzel plný, rekurzivně pokračujeme s jeho dělením
při pokusu vložit klíč do plného kořene je rozdělen kořen na dva (případ, kdy se zvýší výška stromu)
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
16 / 31
Příklad vložení hodnoty s klíčem 30 .
13
•
•
7
•
2
•
3
•
23 31 43
•
•
5
•
7 11
•
•
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
17 / 31
Příklad vložení hodnoty s klíčem 30 .
13
•
•
7
•
2
•
3
•
23 31 43
•
•
5
•
7 11
•
•
•
13 17 19
•
•
•
•
•
•
•
23 29 30
•
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
17 / 31
Příklad vložení hodnoty s klíčem 6 .
13
•
.. .
7
•
2
•
Vychodil V. (DAMOL)
3
•
•
5
•
•
7 11
•
•
•
Indexing structures in RDBMs
•
Nov 28, 2013
18 / 31
Příklad vložení hodnoty s klíčem 6 .
13
•
•
.. .
7
•
2
•
3
•
Vychodil V. (DAMOL)
•
5
•
•
6
•
7 11
•
•
Indexing structures in RDBMs
•
•
Nov 28, 2013
18 / 31
Příklad vložení hodnoty s klíčem 6 .
13
•
5
•
2
•
3
•
Vychodil V. (DAMOL)
•
.. .
7
•
5
•
•
•
6
•
7 11
•
•
Indexing structures in RDBMs
•
•
Nov 28, 2013
18 / 31
Příklad vložení hodnoty s klíčem 40 .
13
•
•
.. .
23 31 43
•
13 17 19
•
•
Vychodil V. (DAMOL)
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
Indexing structures in RDBMs
•
43 47
•
•
•
Nov 28, 2013
19 / 31
Příklad vložení hodnoty s klíčem 40 .
13
•
.. .
23 31 43
•
13 17 19
•
•
•
•
•
•
•
23 29
•
Vychodil V. (DAMOL)
•
•
31 37
•
•
•
40 41
•
Indexing structures in RDBMs
•
•
43 47
•
•
•
Nov 28, 2013
19 / 31
Příklad vložení hodnoty s klíčem 40 .
13
•
.. .
23 31
•
13 17 19
•
•
•
•
•
43
•
•
23 29
•
Vychodil V. (DAMOL)
•
•
31 37
•
•
•
•
40 41
•
Indexing structures in RDBMs
•
•
43 47
•
•
•
Nov 28, 2013
19 / 31
Příklad vložení hodnoty s klíčem 40 . 13 40 •
.. .
•
•
23 31
•
13 17 19
•
•
•
•
43
•
•
23 29
•
Vychodil V. (DAMOL)
•
•
31 37
•
•
•
•
40 41
•
Indexing structures in RDBMs
•
•
43 47
•
•
•
Nov 28, 2013
19 / 31
Modifikace B+ -stromů: Mazání konzervativní přístup: data se nemažou vůbec, pouze se označují, jako smazaná (NULL pointer) rychlé, ale databáze může časem bobtnat (operace typu VACUUM) progresivní přístup: vyhledáme listový uzel, ze kterého chceme mazat (pokud po výmazu zůstane aspoň z poloviny zaplněný, úloha je triviální) pokud po výmazu klíče počet ukazateů klesne pod povolenou mez, potom: pokud má levý nebo pravý sourozenec daného uzlu zaplněnu víc než polovinu uzlů, pak můžeme k aktuálnímu uzlu přidat hodnotu ze sourozence (a aktualizovat rodiče) pokud má levý i pravý sourozenec minimální počet ukazetelů, pak sloučíme aktuální uzel s některým jeho levým/pravým sourozencem, dále je třeba: aktualizovat rodičovský uzel (odstranění jednoho ukazatele) případně propagovat změnu dál do stromu
pokud by počet ukazatelů v kořenu klesl na 1, zmenšujeme výšku stromu Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
20 / 31
Příklad smazání hodnoty s klíčem 3 .
13
•
•
7
•
2
•
3
•
23 31 43
•
•
5
•
7 11
•
•
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
21 / 31
Příklad smazání hodnoty s klíčem 3 .
13
•
•
7
•
2
•
23 31 43
•
•
5
•
7 11
•
•
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
21 / 31
Příklad smazání hodnoty s klíčem 7 .
13
•
•
.. .
7
•
2
•
3
•
Vychodil V. (DAMOL)
•
5
•
7 11
•
•
•
•
Indexing structures in RDBMs
Nov 28, 2013
22 / 31
Příklad smazání hodnoty s klíčem 7 .
13
•
•
.. .
7
•
2
•
3
•
Vychodil V. (DAMOL)
•
5
•
11
•
•
•
Indexing structures in RDBMs
Nov 28, 2013
22 / 31
Příklad smazání hodnoty s klíčem 7 .
13
•
•
.. .
7
•
2
•
•
3
•
Vychodil V. (DAMOL)
5 11
•
•
•
•
Indexing structures in RDBMs
Nov 28, 2013
22 / 31
Příklad smazání hodnoty s klíčem 7 .
13
•
•
.. .
5
•
2
•
•
3
•
Vychodil V. (DAMOL)
5 11
•
•
•
•
Indexing structures in RDBMs
Nov 28, 2013
22 / 31
Příklad následného smazání hodnoty s klíčem 11 .
13
•
•
5
•
2
•
23 31 43
•
•
3
•
5 11
•
•
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
23 / 31
Příklad následného smazání hodnoty s klíčem 11 .
13
•
•
5
•
2
•
23 31 43
•
•
3
•
5
•
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
23 / 31
Příklad následného smazání hodnoty s klíčem 11 .
13
•
•
23 31 43
•
2
•
3
•
•
5
•
13 17 19
•
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
23 / 31
Příklad následného smazání hodnoty s klíčem 11 .
13
•
•
13
•
2
•
3
•
31 43
•
•
5
•
13 17 19
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
23 / 31
Příklad následného smazání hodnoty s klíčem 11 .
23
•
•
13
•
2
•
3
•
31 43
•
•
5
•
13 17 19
•
•
•
•
•
•
23 29
•
•
•
31 37 41
•
•
•
•
43 47
•
•
•
.
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
23 / 31
Efektivita B+ -stromů vyjádření efektivity: podstatné jsou diskové operace (načítání a ukládání bloků/stránek) ve srovnání s tím nepodstatné: reorganizace uzlů probíhající v paměti cena operací pro modifikaci stromu: pro velké hodnoty n (aspoň n ≥ 10) platí: výskyt operací rozdělení a slučování uzlů velmi řídký navíc: obvykle jsou operace omezeny na listy a jejich rodiče
cena vyhledávání hodnoty: počet diskových operací = výška stromu implementační optimalizace: první dvě patra stromu jsou v paměti řádová složitost vyhledávání/vkládání/mazání: O(log m) (kde m je velikost stromu – počet dvojic klíč/hodnota) Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
24 / 31
Rozšiřitelné hashovací tabulky rozšiřitelná (a perzistentní) verze hashovacích tabulek: funkce h – vrací pro každou hodnotu x vyhledávacího klíče hodnotu h(x) h(x) jsou celá čísla (vyjadřovaná v binárním tvaru) s dostatečným rozsahem (typicky čísla typu integer o velikosti 4 B nebo 8 B) význam: h(x) neurčuje index ( jako u hashovacích tabulek v paměti), ale: pomocí h(x) je vypočítán slot obsahující ukazatel na stránku se záznamy (ve stránce může být záznam s klíčem x) počet slotů dynamicky roste, jeho počet je mocnina 2
parametry algoritmu: h (hashovací funkce) i (aktuální délka binárního prefixu, který se používá na nalezení slotu) Fagin R., Nievergelt J., Pippenger N., Strong H. R.: Extendible hashing—a fast access method for dynamic files ACM Transactions on Database Systems 4 (3): 315–344 (1979) Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
25 / 31
Příklad rozšířitelné hashovací tabulky pro parametry: h vracející čísla typu uint32 i = 1 (počáteční hodnota i) 0
1
• . •
1
0001
1
1001 1100
význam čísla v hlavičce bloku: číslo i ≤ j udává, kolik bitů je použito pro rozlišení záznamů v rámci bloku Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
26 / 31
Vkládání hodnoty: Triviální případ
vložení klíče s hashem 0111 · · · : 0
1
• . •
1
0001
1
1001 1100
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
27 / 31
Vkládání hodnoty: Triviální případ
vložení klíče s hashem 0111 · · · : 0
1
• . •
1
Vychodil V. (DAMOL)
1
0001
1001
0111
1100
Indexing structures in RDBMs
Nov 28, 2013
27 / 31
Vkládání hodnoty: Zvětšení počtu slotů
vložení klíče s hashem 0101 · · · : 0
1
• . •
1
Vychodil V. (DAMOL)
1
0001
1001
0111
1100
Indexing structures in RDBMs
Nov 28, 2013
28 / 31
Vkládání hodnoty: Zvětšení počtu slotů
vložení klíče s hashem 0101 · · · : 00
01
10
11
•
• . •
•
1
Vychodil V. (DAMOL)
1
0001
1001
0111
1100
Indexing structures in RDBMs
Nov 28, 2013
28 / 31
Vkládání hodnoty: Zvětšení počtu slotů
vložení klíče s hashem 0101 · · · : 00
01
10
11
•
• . •
•
2
0001
1
2
0111
1001 1100
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
28 / 31
Vkládání hodnoty: Zvětšení počtu slotů
vložení klíče s hashem 0101 · · · : 00
01
10
11
•
• . •
•
2
0001
Vychodil V. (DAMOL)
1
2
0111
1001
0101
1100
Indexing structures in RDBMs
Nov 28, 2013
28 / 31
Vkládání hodnoty: Rozdělení bloků bez zvětšení počtu slotů
vložení klíče s hashem 1010 · · · : 00
01
10
11
•
• . •
•
2
0001
Vychodil V. (DAMOL)
1
2
0111
1001
0101
1100
Indexing structures in RDBMs
Nov 28, 2013
29 / 31
Vkládání hodnoty: Rozdělení bloků bez zvětšení počtu slotů
vložení klíče s hashem 1010 · · · :
2
0001
00
01
10
11
•
• . •
•
2
0111
2
1001
2
1100
0101
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
29 / 31
Vkládání hodnoty: Rozdělení bloků bez zvětšení počtu slotů
vložení klíče s hashem 1010 · · · :
2
0001
Vychodil V. (DAMOL)
00
01
10
11
•
• . •
•
2
2
0111
1001
0101
1010
Indexing structures in RDBMs
2
1100
Nov 28, 2013
29 / 31
Rozšířitelné hashovací tabulky: Vkládání a mazání vkládání nových záznamů: 1. triviální, pokud má stránka pro vkládání dost místa 2. pokud je stránka plná a j < i, pak: inkrementujeme j a rozdělíme blok na dva rozdělíme záznamy z výchozího bloku do dvou na základě nového j pokusíme se přidat nový záznam (někdy je třeba proces opakovat)
. pokud je stránka plná a j = i, pak inkrementujeme i a aplikujeme 2.
3
mazání záznamů: obvykle konzervativní výhody/nevýhody: může být rychlejší při vyhledávání než stromy má režii spojenou s reorganizací pole slotů a rozdělováním stránek narozdíl od stromů: nereprezentuje uspořádání Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
30 / 31
Použití zdroje Bayer R., McCreight, E.: Organization and maintenance of large ordered indexes Acta Informatica 1 (3): 173–189 (1972) Fagin R., Nievergelt J., Pippenger N., Strong H. R.: Extendible hashing—a fast access method for dynamic files ACM Transactions on Database Systems 4 (3): 315–344 (1979) Garcia-Molina H., Ullman J., Widom J.: Database Systems: The Complete Book Prentice Hall 2008, ISBN 978–0131873254 Lehman P., Yao S.: Efficient locking for concurrent operations on B-trees ACM Transactions on Database Systems 6 (4): 650–670 (1981)
Vychodil V. (DAMOL)
Indexing structures in RDBMs
Nov 28, 2013
31 / 31
