PA152: Efektivní využívání DB
4. Indexování
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2014 2
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, 2014 3
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, 2014 4
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, 2014 5
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, 2014 6
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, 2014 7
Index a ukazatele
 Ukazatele v indexech
Ukazatel na záznam
 Adresa bloku + offset záznamu
Ukazatel na blok
 Adresa bloku
 identifikace souboru + offset v souboru
 lépe: identifikace souboru + číslo bloku
Soubor je spojitý a uspořádaný
 Ukazatele na bloky se nemusí ukládat
 tzv. implicitní odkazy – lze je „spočítat“
 např. číslo bloku lze určit z pořadí položky v indexu
PA152, Vlastislav Dohnal, FI MUNI, 2014 8
Implicitní ukazatele na blok
 Blok o velikosti 8KiB
 Hledáme „K3“
Prohledání indexu
 K3 je ve třetí položce
  třetí blok (B3)
Offset v souboru
 (3-1)·8192=24 576
K1B1
K3B3
K4B4
K2B2
B1
B2
B3
B4
Soubor
Index 0
16384
8192
24576
32768
PA152, Vlastislav Dohnal, FI MUNI, 2014 9
Duplicitní 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, 2014 10
 Duplicity v primárním indexu
20
30
30
30
20
30
30
30
20
30
30
30
40
45
Duplicitní 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, 2014 11
 Klíče v primárním indexu jsou unikátní
 uspořádaný soubor
20
30
30
30
45
Duplicitní 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, 2014 12
 Odkazy na bloky
Neřeší duplicitní klíče v indexu
 Vyhledávání záznamů!!!
Najdi hodnotu „20“
20
30
30
30
40
Duplicitní 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, 2014 13
 Odkaz na blok, ale:
V indexu je vždy nový klíč
20
30
30
30
40
Duplicitní 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, 2014 14
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, 2014 15
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, 2014 16
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, 2014 17
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, 2014 18
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, 2014 19
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, 2014 20
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, 2014 21
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, 2014 22
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, 2014 23
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, 2014 24
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, 2014 25
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, 2014 26
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, 2014 27
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, 2014 28
Sekundární index
 Vždy odkazy na záznamy!
Vyhledávací klíč
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, 2014 29
Sekundární index: duplicitní 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, 2014 30
Sekundární index: duplicitní 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, 2014 31
Sekundární index: duplicitní 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, 2014 32
Sekundární index: duplicitní klíče
 Výhoda nepřímého odkazu na záznam při
dotazování
Spojení podmínek bez čtení záznamů
 Příklad:
Relace
 zaměstnanec(jméno, oddělení, místnost)
Indexy:
 Jméno – primární index
 Oddělení – sekundární index
 Místnost – sekundární index
PA152, Vlastislav Dohnal, FI MUNI, 2014 33
Sekundární index: duplicitní klíče
 Dotaz: zaměstnanci hraček v místnosti G243
 Průnik kyblíků
 Máme seznam ukazatelů na správné zaměstnance
 Technika používaná v text information retrieval
Hračky G243
Soubor
(zaměstnanec)Index (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, 2014 34
Document 1 Word List for Doc1
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, 2014 35
Term docID
ambitious 1
brutus 1
brutus 3
capitol 2
caesar 1
caesar 2
Term Posting list of docIDs
ambitious 1
brutus 1, 3
capitol 1
caesar 1, 2
Relační
pohled
Invertovaný
soubor
PA152, Vlastislav Dohnal, FI MUNI, 2014 36
Konvenční indexy: shrnutí
 Základní dělení
 Řídké vs. Husté
 Vkládání / mazání
 Duplicitní 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, 2014 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 vyslovení „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, 2014 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
… odkazy na záznamy v souboru …
PA152, Vlastislav Dohnal, FI MUNI, 2014 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, 2014 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, 2014 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, 2014 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í
 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, 2014 43
PA152, Vlastislav Dohnal, FI MUNI, 2014 44
B+-strom: n=4
 Vložení klíče 32
Bez reorganizace
3
5
11
30
31
30
10032
PA152, Vlastislav Dohnal, FI MUNI, 2014 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, 2014 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
180
160
179
160
PA152, Vlastislav Dohnal, FI MUNI, 2014 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
New root node
PA152, Vlastislav Dohnal, FI MUNI, 2014 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, 2014 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, 2014 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, 2014 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, 2014 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, 2014 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
25
25New root
30
40
PA152, Vlastislav Dohnal, FI MUNI, 2014 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, 2014 55
B+-strom vs. index-sekvenční soubor
 Kapacita bloku (4 KiB)
 Klíč = 4 bajty, ukazatel = 4 bajty
 Ří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:
 Řídký index: každý blok  až 1024 bloků souboru
 B+-strom: jeden blok  až 512 bloků souboru
 Index o dvou úrovních: (1. úroveň = právě 1 blok)
 Řídký index : až 1 048 576 bloků souboru
 B+-strom: až 262 144 bloků souboru
PA152, Vlastislav Dohnal, FI MUNI, 2014 56
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)
 Konvenční index nikoli! (lineární složitost)
 Kvůli přetokovým oblastem
 LRU není pro B+-strom vhodný!
 B+-strom je vhodnější organizace.
PA152, Vlastislav Dohnal, FI MUNI, 2014 57
B-strom (pozor bez +)
 Idea: nereplikovat 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, 2014 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
No!
PA152, Vlastislav Dohnal, FI MUNI, 2014 59
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
(klíčů a
odkazů)
n/2 -1
(klíčů a
odkazů)
Vnitřní uzel
(kořen)
n
(potomků)
2
(potomků)
n-1
(klíčů a
odkazů)
1
(klíčů a
odkazů)
List
(ne kořen)
n-1
(záznamů)
(n-1)/2
(záznamů)
n-1
(odkazů na
záznamy)
(n-1)/2
(odkazů na
záznamy)
List
(kořen)
n-1
(záznamů)
0
(záznamů)
n-1
(odkazů na
záznamy)
0
(odkazů na
záznamy)
PA152, Vlastislav Dohnal, FI MUNI, 2014 60
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, 2014 61
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, 2014 62
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, 2014 63
Porovnání: výsledek
 Počet čtení z disku:
B-strom
 P1 čtení = 341 / 175 445 = 0,2%
 P2 čtení = 1 - P1 čtení = 99,8%
B+-strom
 P2 čtení = 100%
PA152, Vlastislav Dohnal, FI MUNI, 2014 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, 2014 65
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, proměnlivá arita, …
Používá se prefix (prefix compression)