PA152: Efektivní využívání DB
4. Indexování
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 7
Index
 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, 2012 8
Index a ukazatele
 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, 2012 9
Implicitní ukazatele na blok
 Blok o velikosti 4KB
 Hledáme K3
Prohledání indexu
 K3 je ve třetí položce
  třetí blok (B3)
Offset v souboru
 (3-1)·4096=8192
K1B1
K3B3
K4B4
K2B2
B1
B2
B3
B4
Soubor
Index
PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 12
 Klíče v indexu jsou unikátní
 uspořádaný soubor
20
30
30
30
45
Duplikátní klíče: hustý index
10
10
20
10
30
20
30
30
45
40
Soubor
10
10
10
20
10
20
30
40
PA152, Vlastislav Dohnal, FI MUNI, 2012 13
 Odkazy na bloky
Neřeší duplicitní klíče v indexu
 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, 2012 14
 Odkaz na blok, ale:
V indexu je vždy nový klíč
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
20
30
30
Zrušit
tuto
položku?
PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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, 2012 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
 Pozor na případné porušení spojitosti a
uspořádanosti bloků souboru
15
10
30
20
50
40
60
10
20
40
60
PA152, Vlastislav Dohnal, FI MUNI, 2012 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, 2012 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, 2012 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, 2012 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, 2012 30
Sekundární index: duplikátní klíče
 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, 2012 31
Sekundární index: duplikátní klíče
 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, 2012 32
Sekundární index: duplikátní klíče
 Variabilita přesunuta do „kyblíků“
10
20
40
20
40
10
40
10
40
30
10
20
30
40
50
60
...
buckets
index blocks
file blocks
PA152, Vlastislav Dohnal, FI MUNI, 2012 33
Sekundární index: duplikátní klíče
 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, 2012 34
Sekundární index: duplikátní klíče
 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 text information retrieval
Hračky DV243
SouborIndex (oddělení) Index (místnost)
Příklad: Text Information Retrieval
 Tzv. „full-text“ index nad dokumenty
 Textové dokumenty rozděleny na slova
 Vytvoř invertovaný soubor
pro všechny dokumenty
PA152, Vlastislav Dohnal, FI MUNI, 2012 35
Document Word List
Caesar and Brutus
are ambitious.
•Caesar
•Brutus
•ambitious
1. Split to words
2. Stemming
3. Ignore ones in stop-list
Příklad: Text Information Retrieval
 Invertovaný soubor
 Najdi dokumenty obsahující Brutus i Caesar
Načti posting lists pro Brutus a Caesar
Vytvoř jejich průnik
PA152, Vlastislav Dohnal, FI MUNI, 2012 36
Term docID
ambitious 2
brutus 1
brutus 2
capitol 1
caesar 1
caesar 2
Term Posting list of docIDs
ambitious 2
brutus 1, 2
capitol 1
caesar 1, 2
PA152, Vlastislav Dohnal, FI MUNI, 2012 37
Konvenční indexy: shrnutí
 Základní dělení
 Řídké vs. Husté
 Vkládání / mazání
 Duplikátní klíče
 Zejména u sekundárních indexů
 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, 2012 38
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, 2012 39
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, 2012 40
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, 2012 41
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, 2012 42
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, 2012 43
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í
 Princip: Růst od listu ke kořenu
 Postup: 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, 2012 44
PA152, Vlastislav Dohnal, FI MUNI, 2012 45
B+-strom: n=4
 Vložení klíče 32
Bez reorganizace
3
5
11
30
31
30
10032
PA152, Vlastislav Dohnal, FI MUNI, 2012 46
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, 2012 47
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, 2012 48
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, 2012 49
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, 2012 50
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, 2012 51
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, 2012 52
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, 2012 53
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, 2012 54
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, 2012 55
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, 2012 56
B+-strom vs. index-sekvenční soubor
 Kapacita bloku (4 KiB)
 Klíč = 4 bajty, ukazatel = 4 bajty
 Statický řídký index a sekvenční soubor
 implicitní indexy, tj. pouze klíče  1024 klíčů
 B+-strom jako soubor
 vnitřní uzel: 512 potomků, list již obsahuje záznamy
 Porovnání – počet datových bloků v indexu:
 Index o jedné úrovni:
 Statický ≤ 1024 bloků souboru
 B+-strom ≤ 512 bloků souboru
 Index o dvou úrovních:
 Statický ≤ 1 048 576 bloků souboru
 B+-strom ≤ 262 144 bloků souboru
PA152, Vlastislav Dohnal, FI MUNI, 2012 57
B+-strom vs. index-sekvenční soubor
 Závěr (pokračování):
 B+-strom má větší režii (potřebuje více místa)
 Je plně dynamický
 B+-strom má složitější zamykání
 Statický index vyžaduje reorganizace
 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, 2012 58
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, 2012 59
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, 2012 60
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, 2012 61
Porovnání B-stromu a B+-stromu
 Velikosti
Blok = 4KiB
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, 2012 62
Porovnání: B-strom
 Kořen:
341 klíčů + 341 ukazatelů na záznam
342 ukazatelů na potomka
341·8 + 342·4 = 4096 bajtů
 List:
512 klíčů + 512 ukazatelů na záznam
512 · 8 = 4096 bajtů
 Počet záznamů:
341 + 342 · 512 = 175 445 záznamů
PA152, Vlastislav Dohnal, FI MUNI, 2012 63
Porovnání: B+-strom
 Kořen:
511 klíčů, 512 ukazatelů na potomka
511·4 + 512·4 = 4092 bajtů
 List:
511 klíčů + 511 ukazatelů na záznam
511 · 8 + 4 = 4092 bajtů
 Počet záznamů:
512 · 511 = 261 632 záznamů
PA152, Vlastislav Dohnal, FI MUNI, 2012 64
Porovnání: výsledek
 Počet čtení z disku:
B-strom
 P1 čtení = 341 / 175 445 = 0,2%, P2 čtení = 1 - P1 čtení
B+-strom
 P2 čtení = 100%
PA152, Vlastislav Dohnal, FI MUNI, 2012 65
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, 2012 66
B+-strom
 B+-strom jako soubor
viz Organizace souborů PV062
 Duplicitní klíče
Odkazy z listů = 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)