PA152: Efektivní využívání DB
4. Indexování
Vlastislav Dohnal
PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 13
◼ Odkaz na blok, ale:
V indexu je vždy nový klíč
◼ Následuje mazání a vkládání v prim. indexu, což přeskočíme.
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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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
34
30
50
40
60
10
30
40
60
25
PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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:
Další je opakování, proto přeskočíme.
PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 43
PA152, Vlastislav Dohnal, FI MUNI, 2019 44
B+-strom: n=4
◼ Vložení klíče 32
Bez reorganizace
3
5
11
30
31
30
10032
PA152, Vlastislav Dohnal, FI MUNI, 2019 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
Následují varianty mazání, což je opakování, proto přeskočíme.
PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 54
B+-strom: mazání
◼ Praxe:
Často nejsou přesuny mezi sousedy
implementovány
◼ Více vložení než mazaní (náhodně) má zaplnění
65-69% i bez přesunů
Příliš složité a nemá velké efekty
PA152, Vlastislav Dohnal, FI MUNI, 2019 55
B+-strom vs. sekundární index
◼ Kapacita bloku (4 KiB)
Klíč = 4 bajty, ukazatel = 4 bajty
Víceúrovňový index
◼ řídký: 512 klíčů a odkazů v bloku
◼ hustý: 512 odkazů na záznamy
B+-strom
◼ vnitřní uzel: 512 potomků
◼ list: 511 odkazů na záznamy
◼ Porovnání – počet záznamů relace:
Index o dvou úrovních: (1. úroveň == 1 blok)
◼ Sek. index: až 1 048 576 záznamů (512h)
◼ B+-strom: až 262 144 záznamů (512h-1 . 511)
◼ Prim. index+soubor: 512h+1 záznamů
PA152, Vlastislav Dohnal, FI MUNI, 2019 56
B+-strom vs. konvenční index
◼ 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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, 2019 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
◼ P1 čtení = 0 / 261 632 = 0%
◼ P2 čtení = 100%
PA152, Vlastislav Dohnal, FI MUNI, 2019 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, 2019 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)