PA152: Efektivní využívání DB
4. Indexování
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 7
Index a ukazatele
 Ukazatele v indexech
Ukazatel na záznam
 Adresa bloku + číslo (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, 2016 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=16 384
K1B1
K3B3
K4B4
K2B2
B1
B2
B3
B4
Soubor
Index 0
16384
8192
24576
32768
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 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, 2016 11
 Klíče v primárním indexu jsou unikátní
vždy musí být sekv. 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, 2016 12
 Odkazy na bloky
Duplicitní klíče lze eliminovat
 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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
 U implicitních indexů 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, 2016 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, 2016 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, 2016 27
Sekundární index
 Soubor je uspořádaný podle jiného klíče
tj. vybudovaný na jiném klíči než je primární
soubor
 Volba typu:
Hustý nebo řídký?
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 29
Sekundární index: duplicitní klíče
 Replikace v indexu
Zvýšení
 Prostorových
nároků
 Přístupového
času
(access time)
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, 2016 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, 2016 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, 2016 32
Sekundární index: duplicitní klíče
 Výhoda seznam odkazů na záznam při
dotazování
 Spojení různých 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, 2016 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
 „Full-text“ index nad dokumenty
 Textové dokumenty rozděleny na slova
 Vytvoř invertovaný soubor
pro všechny dokumenty
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 43
PA152, Vlastislav Dohnal, FI MUNI, 2016 44
B+-strom: n=4
 Vložení klíče 32
Bez reorganizace
3
5
11
30
31
30
10032
PA152, Vlastislav Dohnal, FI MUNI, 2016 45
B+-strom: n=4
 Vložení klíče 7
Štěpení listu
30
31
30
100
7
3
5
11
3
5
11
7
11
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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, 2016 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 511 odkazů na
bloky
 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ž 511 bloků souboru
 Index o dvou úrovních: (1. úroveň = právě 1 blok)
 Řídký index : až 1 048 576 bloků souboru
 B+-strom: až 261 632 bloků souboru
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 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, 2016 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! Not
present!
PA152, Vlastislav Dohnal, FI MUNI, 2016 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, 2016 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, 2016 61
Porovnání: B-strom
 Kořen:
341 klíčů + 341 ukazatelů na záznam
342 ukazatelů na potomky
 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, 2016 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, 2016 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, 2016 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, 2016 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)