PA152: Efektivní využívání DB
4. Indexování
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2009 2
Poděkování
 Zdrojem materiálů tohoto předmětu jsou:
Přednášky CS245, CS345, CS345
 Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
 Stanford University, California
PA152, Vlastislav Dohnal, FI MUNI, 2009 3
Indexování
 Důvod: rychlejší přístup k záznamům
než sekvenční průchod souborů
 Varianty:
Konvenční indexy
B-stromy
Hašování
? záznamklíč
soubor
klíč
……
PA152, Vlastislav Dohnal, FI MUNI, 2009 4
Základní pojmy
 Sekvenční soubor
 Index-sekvenční soubor
 Vyhledávací klíč
 Primární klíč
 Index
 Primární index
 Sekundární index
 Hustý index
 Řídký index
 Víceúrovňový index
PA152, Vlastislav Dohnal, FI MUNI, 2009 5
Soubor
Sekvenční soubor
20
10
40
30
60
50
80
70
100
90
Index-sekvenční soubor
20
10
40
30
60
50
80
70
100
90
10
30
50
70
90
PA152, Vlastislav Dohnal, FI MUNI, 2009 6
Index
 Položka indexu:
klíč, odkaz na záznam/blok
20
10
40
30
60
50
80
70
Řídký index
10
30
50
70
Hustý index
10
20
30
40
50
60
70
80
PA152, Vlastislav Dohnal, FI MUNI, 2009 7
Index (2)
 Víceúrovňový index
 Lze mít indexy vyšších úrovní husté?
2. úroveň
10
50
1. úroveň
10
20
30
40
50
60
70
80
20
10
40
30
60
50
80
70
Soubor
PA152, Vlastislav Dohnal, FI MUNI, 2009 8
Index (3)
 Ukazatele v indexech
Ukazatel na záznam
 Adresa bloku + offset záznamu
Ukazatel na blok
 Adresa bloku
 Obvykle kratší
Soubor je spojitý a uspořádaný
 Ukazatele na bloky se nemusí ukládat
 tzv. implicitní odkazy
 „Lze je spočítat“
PA152, Vlastislav Dohnal, FI MUNI, 2009 9
Výpočet ukazatele na blok
 Blok o velikosti 1KB
 Hledáme K3
 přístup do bloku B3
Offset v souboru:
(3-1)·1024=2048
K1B1
K3B3
K4B4
K2B2
B1
B2
B3
B4
Soubor
Index
PA152, Vlastislav Dohnal, FI MUNI, 2009 10
Duplikátní klíče
 Vytvoření indexu
hustý index?
řídký index?
10
10
20
10
30
20
30
30
45
40
Soubor
PA152, Vlastislav Dohnal, FI MUNI, 2009 11
 Duplicity v indexu
20
30
30
30
20
30
30
30
20
30
30
30
40
45
Duplikátní klíče: hustý index
10
10
20
10
30
20
30
30
45
40
Soubor
10
10
10
20
10
10
10
20
PA152, Vlastislav Dohnal, FI MUNI, 2009 12
 Klíče v indexu jsou unikátní
20
30
30
30
45
Duplikátní klíče: hustý index (2)
10
10
20
10
30
20
30
30
45
40
Soubor
10
10
10
20
10
20
30
40
PA152, Vlastislav Dohnal, FI MUNI, 2009 13
 Odkazy na bloky
 Vyhledávání záznamů!!!
Např. klíč 20
20
30
30
30
40
Duplikátní klíče: řídký index
10
10
20
10
30
20
30
30
45
40
Soubor
10
10
10
20
10
10
20
30
PA152, Vlastislav Dohnal, FI MUNI, 2009 14
 V indexu je vždy nový klíč
20
30
30
30
40
Duplikátní klíče: řídký index (2)
10
10
20
10
30
20
30
30
45
40
Soubor
10
10
10
20
10
20
30
30
Zrušit
tuto
položku?
PA152, Vlastislav Dohnal, FI MUNI, 2009 15
Mazání v indexech
 Řídký index
Smazání záznamu s klíčem 40
20
10
40
30
60
50
80
70
10
30
50
70
PA152, Vlastislav Dohnal, FI MUNI, 2009 16
Mazání v indexech: výsledek
 Řídký index
Po smazání záznamu s klíčem 40
20
10
40
30
60
50
80
70
10
30
50
70
PA152, Vlastislav Dohnal, FI MUNI, 2009 17
Mazání v indexech
 Řídký index
Smazání záznamu s klíčem 30
20
10
40
30
60
50
80
70
10
30
50
70
PA152, Vlastislav Dohnal, FI MUNI, 2009 18
Mazání v indexech: výsledek
 Řídký index
Po smazání záznamu s klíčem 30
 Aktualizace indexu
20
10
40
60
50
80
70
10
40
50
70
PA152, Vlastislav Dohnal, FI MUNI, 2009 19
Mazání v indexech
 Řídký index
Smazání záznamů s 30 a 40
20
10
40
30
60
50
80
70
10
30
50
70
PA152, Vlastislav Dohnal, FI MUNI, 2009 20
Mazání v indexech: výsledek
 Řídký index
Po smazání záznamů s 30 a 40
 Aktualizace indexu
20
10
40
30
60
50
80
70
10
50
70
PA152, Vlastislav Dohnal, FI MUNI, 2009 21
Mazání v indexech
 Hustý index – vždy aktualizace indexu
Smazání záznamu s klíčem 30
20
10
40
30
60
50
80
70
10
20
30
40
50
60
70
80
PA152, Vlastislav Dohnal, FI MUNI, 2009 22
Mazání v indexech: výsledek
 Hustý index
Po smazání záznamu s klíčem 30
20
10
40
60
50
80
70
10
20
40
50
60
70
80
PA152, Vlastislav Dohnal, FI MUNI, 2009 23
Vkládání v indexech
 Řídký index
Vložení záznamu s klíčem 34
 Volné místo
 bez reorganizace 20
10
34
30
50
40
60
10
30
40
60
PA152, Vlastislav Dohnal, FI MUNI, 2009 24
Vkládání v indexech
 Řídký index
Vložení záznamu s klíčem 15
 Volné místo není
 reorganizace 20
10
30
50
40
60
10
30
40
60
PA152, Vlastislav Dohnal, FI MUNI, 2009 25
Vkládání v indexech
 Řídký index
Vložení záznamu s klíčem 15
 Volné místo není
 reorganizace
 Řešení pomocí
přesunu do
sousedního bloku
Alternativa: vytvoř nový blok
15
10
30
20
50
40
60
10
20
40
60
PA152, Vlastislav Dohnal, FI MUNI, 2009 26
Vkládání v indexech
 Řídký index
Vložení záznamu s klíčem 25
 Volné místo není
 reorganizace
 Řešení pomocí
přetokových bloků
 Reorganizace je provedena později
20
10
30
50
40
60
10
30
40
60
25
PA152, Vlastislav Dohnal, FI MUNI, 2009 27
Vkládání v indexech
 Hustý index
Vložení záznamu
 Vždy i do indexu
 V souboru stejné problémy jako u řídkého indexu
PA152, Vlastislav Dohnal, FI 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:
Hustý nebo řídký?
PA152, Vlastislav Dohnal, FI MUNI, 2009 29
Sekundární index
 Vždy odkazy na záznamy!
Klíč pro uspořádání
50
30
70
20
40
80
10
100
60
90
Hustý index
10
20
30
40
50
60
70
...
10
50
90
...
Řídký pro
vyšší úrovně
PA152, Vlastislav Dohnal, FI MUNI, 2009 30
Duplikátní klíče: sekundární index
 Replikace v indexu
Zvýšení
 Přístupového
času
(access time)
 Diskových
nároků
10
20
40
20
40
10
40
10
40
30
10
10
10
20
20
30
40
40
40
40
...
PA152, Vlastislav Dohnal, FI MUNI, 2009 31
Duplikátní klíče: sekundární index 2
 Indexová položka má seznam ukazatelů
Problém variabilní délky položky
10
20
40
20
40
10
40
10
40
30
10
40
30
20
PA152, Vlastislav Dohnal, FI MUNI, 2009 32
Duplikátní klíče: sekundární index 3
 Variabilita přesunuta do „kyblíků“
10
20
40
20
40
10
40
10
40
30
10
20
30
40
50
60
...
buckets
PA152, Vlastislav Dohnal, FI MUNI, 2009 33
Duplikátní klíče: sekundární index 4
 Vhodnost nepřímého odkazu na záznam
Tj. „kyblíků“
 Příklad:
Relace
 zaměstnanec(jméno, oddělení, místnost)
Indexy:
 Jméno – primární
 Oddělení – sekundární
 Místnost – sekundární
PA152, Vlastislav Dohnal, FI MUNI, 2009 34
Duplikátní klíče: sekundární index 5
 Dotaz: zaměstnanci hraček v místnosti DV243
 Průnik kyblíků
 Máme seznam ukazatelů na správné zaměstnance
 Technika používaná v information retrieval
Hračky DV243
SouborOddělení (index) Místnost (index)
Příklad: Information Retrieval
 Textové dokumenty rozděleny na slova:
 Najdi dokumenty obsahující Brutus i Caesar
Načti posting lists pro Brutus a Caesar
Vytvoř jejich průnik
PA152, Vlastislav Dohnal, FI MUNI, 2009 35
Term docID
ambitious 2
be 2
brutus 1
brutus 2
capitol 1
caesar 1
caesar 2
Term Posting list
ambitious 2
be 2
brutus 1, 2
capitol 1
caesar 1, 2
PA152, Vlastislav Dohnal, FI MUNI, 2009 36
Konvenční indexy: shrnutí
 Základní dělení
 Řídké vs. Husté
 Vkládání / mazání
 Duplikátní klíče
 Sekundární indexy
 Výhody
 Jednoduché
 Index je sekvenční soubor  vhodné pro „full scan“
 Nevýhody
 Aktualizace drahé
 Ztráta „sekvenčnosti“ a vyváženosti
 kvůli přetokovým oblastem
PA152, Vlastislav Dohnal, FI MUNI, 2009 37
B-stromy
 Jiný typ indexu
 Sekvenční uspořádání není nutné
 Garance I/O pro přístup (vyváženost)
 Více variant
 B-strom, B+-strom, B*-strom, …
 Obvykle se při vylovení „ B-strom“ myslí „ B+-strom“!
 Původ
 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, FI MUNI, 2009 38
B+-strom
 Příklad n=4
100
120
150
180
30
3
5
11
30
35
100
101
110
120
130
150
156
179
180
200
… záznamy v souboru …
PA152, Vlastislav Dohnal, FI MUNI, 2009 39
B+-strom
 Vnitřní uzel pro n=4
57
81
95
Klíče
k < 57
Klíče
57 ≤ k < 81
Klíče
81 ≤ k < 95
Klíče
95 ≤ k
PA152, Vlastislav Dohnal, FI MUNI, 2009 40
B+-strom
 Listový uzel pro n=4
57
81
95
Odkaz z nelistového uzlu
Odkaz na
následující list
Odkazy na záznamy:
PA152, Vlastislav Dohnal, FI MUNI, 2009 41
B+-strom
 Parametr n (arita stromu) ovlivňuje:
Tvar uzlu:
Minimální naplnění
Listový uzel
 Vždy na stejné úrovni
 pi odkazuje na záznam s klíčem Ki (data)
 pn odkazuje na další list (zřetězení listů)
Nelistový uzel
 pi odkazuje na uzel, kde jsou klíče K: Ki-1 ≤ K < Ki
K1
p1 K2
p2 Kn-1
pnp3 …
PA152, Vlastislav Dohnal, FI MUNI, 2009 42
B+-strom
 Podmínky naplnění
Max
ukazatelů
Min
ukazatelů
Max klíčů Min klíčů
Vnitřní uzel
(ne kořen)
n
(potomků)
n/2
(potomků)
n-1 n/2 -1
Vnitřní uzel
(kořen)
n
(potomků)
2
(potomků)
n-1 1
List
(ne kořen)
n-1
(záznamů)
(n-1)/2
(záznamů)
n-1
(záznamů)
(n-1)/2
(záznamů)
List
(kořen)
n-1
(záznamů)
0
(záznamů)
n-1
(záznamů)
0
(záznamů)
B+-strom: vkládání
 Růst od listu ke kořenu
 Nalézt listový uzel a vložit klíč
 Včetně odkazu na záznam
 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, FI MUNI, 2009 43
PA152, Vlastislav Dohnal, FI MUNI, 2009 44
B+-strom: n=4
 Vložení klíče 32
Bez reorganizace
3
5
11
30
31
30
10032
PA152, Vlastislav Dohnal, FI MUNI, 2009 45
B+-strom: n=4
 Vložení klíče 7
Štěpení listu
3
5
11
30
31
30
100
3
5
7
7
PA152, Vlastislav Dohnal, FI MUNI, 2009 46
B+-strom: n=4
 Vložení klíče 160
Štěpení vnitřního uzlu
100
120
150
180
150
156
179
180
200
160
180
160
179
PA152, Vlastislav Dohnal, FI MUNI, 2009 47
B+-strom: n=4
 Vložení klíče 45
Nový kořen
10
20
30
1
2
3
10
12
20
25
30
32
40
40
45
40
30
Nový kořen
PA152, Vlastislav Dohnal, FI MUNI, 2009 48
B+-strom: štěpení listu
n=3, vkládáme 6
5 6 7
7
1 3
5
5 6 7
5 7
1 3
5 6 7
5 7
5
1 3
6
1.
2.
3.
PA152, Vlastislav Dohnal, FI MUNI, 2009 49
B+-strom: štěpení vnitřního uzlu
5 6 7
5 7
1 3
41.
2.
3.
4 5 6
5 7
1 3 7
4
5 74
4 5 6
4
1 3 7
7
5
5
4 7
4 5 61 3 7
4.
n=3, vkládáme 4
PA152, Vlastislav Dohnal, FI MUNI, 2009 50
B+-strom: mazání
 Nalézt listový uzel a smazat klíč
 Včetně odkazu na záznam
 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, FI MUNI, 2009 51
B+-strom: n=5
 Mazání klíče 50
Přesun do souseda a smaž uzel
10
40
100
10
20
30
40
50
40
PA152, Vlastislav Dohnal, FI MUNI, 2009 52
B+-strom: n=5
 Mazání klíče 50
Přesuny mezi sousedy (bez mazání uzlu)
10
40
100
10
20
30
35
40
50
35
35
PA152, Vlastislav Dohnal, FI MUNI, 2009 53
B+-strom: n=5
 Mazání klíče 37
Přesuny mezi sousedy pro vnitřní uzly
40
45
30
37
25
26
20
22
10
14
1
3
10
20
30
40
40
30
25
25nový kořen
PA152, Vlastislav Dohnal, FI MUNI, 2009 54
B+-strom: mazání
 Praxe:
Často nejsou přesuny mezi sousedy
implementovány
Příliš složité a nemá velké efekty
PA152, Vlastislav Dohnal, FI MUNI, 2009 55
B+-strom vs. index-sekvenční soubor
 Kapacita bloku (512 bajtů)
 Klíč = 4 bajty, ukazatel = 4 bajty
 Statický index – implicitní indexy, 127 klíčů
 B+-strom – 63 klíčů, tj. 64 potomků
 Počet datových bloků v indexu:
 První úroveň: statický ≤ 127, B+-strom ≤ 64
 Druhá úroveň : statický ≤ 16129, B+-strom ≤ 4096
 Závěr:
 B+-strom potřebuje více místa
 B+-strom má složitější zamykání
 Statický index vyžaduje reorganizace
PA152, Vlastislav Dohnal, FI MUNI, 2009 56
B+-strom vs. index-sekvenční soubor
 Závěr (pokračování):
DB neví kdy reorganizovat!
 B+-strom provádí pouze malé lokální reorganizace
 Statický index provádí velké reorganizace
Buffer manager
 B+-strom má fixní nároky (log hloubka)
 Statický index nikoli!
 Kvůli přetokovým oblastem
 LRU není pro B+-strom vhodný!
 B+-strom je vhodnější organizace.
PA152, Vlastislav Dohnal, FI MUNI, 2009 57
B-strom (pozor bez +)
 Neduplikovat klíče
 odkazy na záznamy i ve vnitřních uzlech
Podmínky pro klíče v podstromech jsou jiné
K1 P1 K2 P2 K3 P3
Odkazy na: …
Uzel s klíči
k < K1
Uzel s klíči
K1 < k < K2
Uzel s klíči
K2 < k < K3
Uzel s klíči
K3 < k
Záznam
s klíčem K1
Záznam
s klíčem K2
Záznam
s klíčem K3
PA152, Vlastislav Dohnal, FI MUNI, 2009 58
B-strom: příklad
 Zřetězení listů již nelze využít
n=3
65
125
145
165
85
105
25
45
10
20
30
40
110
120
90
100
70
80
170
180
50
60
130
140
150
160
PA152, Vlastislav Dohnal, FI MUNI, 2009 59
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/2 n-1 n/2-1
Vnitřní uzel
(kořen)
n 2 n-1 1
List
(ne kořen)
n-1
(záznamů)
(n-1)/2
(záznamů)
n-1 (n-1)/2
List
(kořen)
n-1
(záznamů)
0
(záznamů)
n-1 0
PA152, Vlastislav Dohnal, FI MUNI, 2009 60
Porovnání B-stromu a B+-stromu
 Velikosti
Blok = 100 bajtů
Ukazatel = 4 bajty
Klíč = 4 bajty
 Uvažujme vždy plný dvouúrovňový strom
1 kořen a pak listy
Každý uzel v jednom bloku
PA152, Vlastislav Dohnal, FI MUNI, 2009 61
Porovnání: B-strom
 Kořen:
8 klíčů + 8 ukazatelů na záznam
9 ukazatelů na potomka
8·4 + 8·4 + 9·4 = 100 bajtů
 List:
12 klíčů + 12 ukazatelů na záznam
12 · 4 + 12 · 4 = 96 bajtů
 Počet záznamů:
8 + 9 · 12 = 116 záznamů
PA152, Vlastislav Dohnal, FI MUNI, 2009 62
Porovnání: B+-strom
 Kořen:
12 klíčů, 13 ukazatelů na potomka
12·4 + 13·4 = 100 bajtů
 List:
12 klíčů + 12 ukazatelů na záznam
12 · 4 + 12 · 4 = 96 bajtů
 Počet záznamů:
13 · 12 = 156 záznamů
PA152, Vlastislav Dohnal, FI MUNI, 2009 63
Porovnání: výsledek
 Počet čtení z disku:
B-strom
 P1 čtení = 8 / 116, P2 čtení = 108 / 116
B+-strom
 P2 čtení = 156 / 156
 Ale: B-strom se 156 záznamy má 3 úrovně
1.úroveň – 8 klíčů, 2.úroveň - 9·8=72,
3.úroveň – 76 klíčů
P1 čtení = 8 / 156, P2 čtení = 72 / 156
P3 čtení = 76 / 156
PA152, Vlastislav Dohnal, FI MUNI, 2009 64
Porovnání: závěr
 B-stromy
 Ve vyhledávání rychlejší
 Ne vždy platí (viz předchozí příklad)
 Různé struktury vnitřního a listového uzlu
 Mazání je obtížnější na implementaci
 B+-stromy jsou preferovány!
PA152, Vlastislav Dohnal, FI MUNI, 2009 65
B+-strom
 B+-strom jako soubor
viz Organizace souborů PV062
 Duplicitní klíče
Odkazy na záznamy  odkazy na kyblíky (buckets)
 Tj. bloky, kde jsou seznamy záznamů se stejnou
hodnotou
 Klíče jsou variabilní délky (např. řetězce)
Ukládat celé  nízká arita a další potíže
Používá se prefix (prefix compression)