PA152: Efektivní využívání DB
3. Ukládání dat
Vlastislav Dohnal
"a1 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Poděkování
b Zdrojem materiálů tohoto předmětu jsou:
D Přednášky CS245, CS345, CS345
b Hector Garcia-Molina, Jeffrey D. Ullman, Jennifer
Widom
b Stanford University, California
D Přednášky dřívější verze PA152 (podzim 2008)
b Pavel Rychlý
b Fakulta informatiky, Masarykova Univerzita
PA152, Vlastislav Dohnal, FI MUNI, 2011
2
Osnova
■ Ukládání dat
■ Záznamy
■ Organizace bloků
■ Příklady
PA152, Vlastislav Dohnal, FI MUNI, 2011
3
Uložení dat
■ Co chceme ukládat?
□ jméno
□ plat
□ datum
□ obrázek
■ Jak ukládat?
□ bajty -— posloupnost bajtů
PA152, Vlastislav Dohnal, Fl MUNI, 2011
Typy datových elementů
■ Celá čísla
□ Podle rozsahu: 2 bajty, 4 bajty
□ Např. 35 v 16 bitech
00000000 I  I00100011
□ Obvykle přímý kód nebo inverzní kód
■ Reálná čísla
□ Plovoucí čárka
■ n bitů rozděleno na mantisu a exponent (dle IEEE 754)
□ Pevná čárka
■ Kódování každých 9 cifer (základ 10) do 4 bajtů
■ Uložení jako řetězec
PA152, Vlastislav Dohnal, FI MUNI, 2011
5
Typy datových elementu
■ Znaky
□ Nejčastěji v ASCII kódování - 1 bajt
□ Více bajtové znaky
■ UCS-2 - kódování UTF-8 do 16 bitU
□ Znaky s kódy 0 až 65535
■ UTF-8 - kódování variabilní délky
□ Znak mUže zabírat 1 až 3 bajty
PA152, Vlastislav Dohnal, Fl MUNI, 2011
I ^^^^^^^^^^^^^^^^^^^^^^^^^
Typy datových elementů
■
■
Pravdivostní hodnota (boolean)
□ Obvykle jako celé číslo
n True   Illll llll
n False  IGGGG GGGG
□ Méně než 1 bajt nemá velký význam
Bitové pole
□ Délka + bity
■ Tj. zaokrouhleno na celé bajty
PA152, Vlastislav Dohnal, FI MUNI, 2011
7
"■' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Typy datových elementů
■ Datum
□ počet dní od „počátku" (např. 1.1.1970)
□ řetězec YYYYMMDD (8 znaků)
■ YYYYDDD (7 znaků)
■ Proč ne YYMMDD?
■ Čas
□ počet sekund od půlnoci
■ počet milisekund nebo mikrosekund
□ řetězec HHMMSSFF
□ časové zóny - čas uložen v UTC
■ Ukládání - konverze z daného pásma do UTC
PA152, Vlastislav Dohnal, Fl MUNI, 2011
Typy datových elementů
■ Výčtový typ
□ Očíslování hodnot -— integer
□ red — 1, green — 2, blue — 3, yellow — 4, ...
PA152, Vlastislav Dohnal, Fl MUNI, 2011
Typy datových elementu
■ Řetězce
□ Pevná délka
■ Omezení velikosti
□ Kratší řetězce doplněny mezerami
□ Delší oříznuty
□ Proměnlivá délka
■ Uložená délka, pak řetězec
■ Ukončení nulou
□ nutnost číst celý
□ nelze uložit nulu v textu
□ Problém znakové sady (kódování)
PA152, Vlastislav Dohnal, Fl MUNl, 2011
10
Uložení datových elementů
■ Každý element „má" svůj typ
□ interpretace bitů
□ velikost
□ speciální hodnota „neznámá" (NULL)
■ Většinou pevná délka
□ každý typ má svoji bitovou reprezentaci
■ Proměnlivá délka
□ velikost na začátku hodnoty
PA152, Vlastislav Dohnal, FI MUNI, 2011
11
Osnova
■ Ukládání dat
■ Záznamy
■ Organizace bloků
■ Příklady
PA152, Vlastislav Dohnal, FI MUNI, 2011
12
BJ ^^^^^^^^^^^
Souvislosti
Datové elementy Záznamy
Bloky Soubory
■
■
Paměť
PA152, Vlastislav Dohnal, FI MUNI, 2011
13
Záznam (record)
m Seznam souvisejících datových elementů
n Resp. jejich hodnot n Fields, Attributes
m Např.
n Zaměstnanec
m Jméno - Novák
m Plat - 1234
m datum_přijetí - 1.1.2000
PA152, Vlastislav Dohnal, FI MUNI, 2011
14
v ^^^^^^^^^^^^^^^^^^^^^^^^
Schéma záznamu
■ Popisuje strukturu záznamu
■ Uložené informace
□ Počet atributů
□ Typ / název každého atributu
□ Pořadí atributu
PA152, Vlastislav Dohnal, FI MUNI, 2011
15
Typy záznamů
■ Pevný formát
□ Schéma společné pro všechny záznamy
■ Je uloženo mimo záznamy (tzv. data dictionary)
■ Proměnlivý formát
□ Každý záznam obsahuje svoje schéma
□ Vhodné pro:
■ „řídké" záznamy (hodně NULL)
■ opakování stejných atributů
■ vyvíjející se formát
□ změny schématu během života db
PA152, Vlastislav Dohnal, FI MUNI, 2011
16
Typy záznamu
■ Pevná délka
□ Každý záznam má stejnou délku (počet bajtU)
■ Proměnlivá délka
□ Ušetření paměti
□ Složitější implementace
□ Možnost pro uložení velkých dat (obrázky, ...)
PA152, Vlastislav Dohnal, FI MUNI, 2011
17
Příklad - pevný formát i délka
■ Zaměstnanec
1) id - 2 byte integer
2) jméno - 10 znaků
3) oddělení - 2 byte code
r schéma
55
—i—i—i-1-1-1-1-1-r
nov á k
02
>
83
d l o u h ý
01
záznamy
■ Zarovnání na „vhodnou" délku
□ Rychlejší přístup k paměti zarovnané na 4 (8) bajtů
PA152, Vlastislav Dohnal, FI MUNI, 2011
Příklad - proměnlivý formát i délka
■ Zaměstnanec:
2	5	I	i 46	4	S	4	„iii C ECH
CD ^ ľ   C (JI
"o — c
O +j O) U CO _J
Kódy identifikující názvy atributů mohou být přímo textové řetězce, tzv. tagy.
□ Nazýváno „Tagged fields"
PA152, Vlastislav Dohnal, FI MUNI, 2011
19
Příklad - opakující se atribut
■ Zaměstnanec má děti
3	Jméno: Jan Novák	Dítě: Tomáš	Dítě: Pavel
□ Vhodné v případě polí (arrays) atp.
■ Opakování atributu neznamená proměnlivou délku ani schéma
□ Lze určit maximální počet opakování
■ Nevyužité místo vyplnit NULL
Novák	Potápění	Šachy	—
PA152, Vlastislav Dohnal, FI MUNI, 2011
20
„Mezivarianta"
■ Mezi pevným a variabilním formátem
■ Přidání „typu záznamu"
record type       record length tells me what to expect
(i.e. points to schema)
27
PA152, Vlastislav Dohnal, Fl MUNI, 2011
21
Hlavička záznamu
■ Ukládá další informace o záznamu
□ Nesouvisející s hodnotami atributů
□ Čas vytvoření / změny / čtení záznamu
□ Délka záznamu
□ Počet atributů / ukazatel na schéma
□ Pole pro NULL hodnoty
■ Jeden bit pro každý atribut
□ OID (Object Identifier) - „ID" záznamu □...
PA152, Vlastislav Dohnal, FI MUNI, 2011
22
Další problémy
■ Komprese
□ Zvýšení rychlosti (méně čtu)
□ Uvnitř záznamu (hodnoty zvlášť)
□ Více záznamU
■ Efektivnější (lze vytvořit slovník)
■ Složitější
■ Kódování (šifrování)
□ Co potom s indexy?
□ Jak řešit rozsahové dotazy? □...
PA152, Vlastislav Dohnal, Fl MUNl, 2011
23
Uložení objektu
■ Současné komerční DB podporují objekty
□ Rozšíření relačních DBMS □OODBMS
■ Objekt má atributy
□ Jednoduché typy -— uložit jako záznam
□ Kolekce — vytvořit novou relaci a tam uložit
■ Referencovat pomocí OID
PA152, Vlastislav Dohnal, FI MUNI, 2011
24
Uložení relace
■ Řádkové
□ Zatím uvažovaná varianta
■ Sloupcové
□ Hodnoty stejného atributu pohromadě
■ Příklad řádkového uložení:
□ Order(id, cust, prod, store, price, date, qty)
idl	custl	prodl	storel	price 1	datel	qty1
id2	cust2	prod2	store2	price2	date2	qty2
id3	cust3	prod3	store3	price3	date3	qty3
PA152, Vlastislav Dohnal, FI MUNI, 2011
25
Sloupcové uložení
■ Relace
□ Order(id, cust, prod, store, price, date, qty)
idl	custl
id2	cust2
id3	cust3
id4	cust4
...	...
	
idl	prodl
id2	prod2
id3	prod3
id4	prod4
...	...
	
Id mohou ale nemusí být uloženy, lze využít pořadí hodnot
PA152, Vlastislav Dohnal, FI MUNI, 2011
26
Porovnání
■ Výhody sloupcového uložení
□ Kompaktnější uložení (nezarovnávání na bajty)
□ Efektivní čtení (např. pro data mining)
■ Zpracovávání mála atributů, ale všech hodnot
■ Výhody řádkového uložení
□ Aktualizace / vkládání je rychlejší
□ Efektivnější při přístupu k celým záznamům
Mike Stonebreaker, Elizabeth O'Neil, Pat O'Neil, Xuedong Chen, et al.: C-Store: A Column-oriented DBMS, VLDB Conference, 2005. http://www.cs.umb.edu/~poneil/vldb05_cstore.pdf
PA152, Vlastislav Dohnal, FI MUNI, 2011 27
Osnova
■ Ukládání dat
■ Záznamy
■ Organizace bloků
■ Příklady
PA152, Vlastislav Dohnal, Fl MUNI, 2011
2K
Uložení záznamů do bloků
■ Záznamy
□ Pevné délky
□ Proměnné délky
■ Bloky pevné velikosti
soubor
PA152, Vlastislav Dohnal, FI MUNI, 2011
29
Uložení záznamů do bloků
■ Techniky
□ Oddělování záznamů
■ Separating records
□ Rozdělování / nerozdělování záznamů
■ Spanned vs. unspanned
□ Uspořádání záznamů
■ Sequencing
□ Odkazy na záznamy
■ Indirection
PA152, Vlastislav Dohnal, FI MUNI, 2011
.in
Oddělování záznamů
		R2		R3
■ Záznamy pevné délky
□ Žádný oddělovač
□ Pamatovat počet a ukazatel na první záznam
■ Oddělovač
■ Ukládání délek záznamU (nebo počátkU)
□ V rámci záznamu
□ V hlavičce bloku
PA152, Vlastislav Dohnal, FI MUNI, 2011
.31
Míchání (shlukování) záznamů
■ Záznamy různých relací v jednom bloku
□ Některá data jsou vyžadována současně
□ Uložit je společně -— zrychlené čtení
□ Složitější implementace
PA152, Vlastislav Dohnal, Fl MUNI, 2011
32
Příklad
■ Relace: zákazník (zid, jméno, adresa)
vklady (zid, vkl_id, výše_vkladu)
■ Vhodné pro dotaz Q1:
□ SELECT jméno, adresa, výše_vkladu FROM vklady, zákazník
WHERE vklady.zid = zákazník.zid AND zákazník.zid = 2354
(2354, 'Petr Malý', 'Brno')		
	(2354, 999ooi, ioo)	
	(2354, 999oio, i5oo)	
PA152, Vlastislav Dohnal, FI MUNI, 2011
33
Příklad pokr.
■ Dotaz Q2:
□ SELECT * FROM zákazník
■ Shlukování nevhodné pro Q2
□ Záleží na četnosti jednotlivých dotazů
PA152, Vlastislav Dohnal, FI MUNI, 2011
34
Míchání (shlukování) záznamů
■ Řešení:
□ Nemíchat v rámci bloku
□ Ukládat bloky blízko sebe
■ Stejný válec disku
PA152, Vlastislav Dohnal, Fl MUNI, 2011
.35
Rozdělování / nerozdělování záznamů
■ Nerozdělování
□ každý záznam součástí jednoho bloku
□ jednodušší, ale může plýtvat místem
blok 1
blok 2
R3	R4	R5	1
■ Rozdělování
□ Záznam „přetéká" mezi bloky
□ Nutné, pokud je záznam větší než blok!
blok 1 blok 2
R1
R2
R3(a)
R3(b)	R4	R5	R6	R7(a)
■ ■ ■
■ ■ ■
PA152, Vlastislav Dohnal, FI MUNI, 2011
36
Příklad
■ Nerozdělování záznamů
□ 106 záznamů, každý 2 050 bajtů (pevná délka)
□ Velikost bloku 4 096 bajtů
blok 1
blok 2
2050 bajtů nevyužito 2046   2050 bajtů   nevyužito 2046
□ Celkem alokováno: 106 * 4096B
□ Celkem využito: 106 * 2050B
□ Využití paměti: 50,05%
PA152, Vlastislav Dohnal, FI MUNI, 2011
37
Rozdělování záznamů
■
Záznam „přetéká" mezi bloky
□ Musíme udržovat pořadí bloků
■ Lze používat ukazatele
blok 1
R1
R2
R3(a)
■
R3(b)	R4	R5	R6	R7(a)
Záznam je rozdělen na „fragmenty"
□ Bitový příznak, zda je fragmentován
□ Ukazatel na další / předchozí fragment
■ ■ ■
PA152, Vlastislav Dohnal, FI MUNI, 2011
38
Rozdělování záznamů
■ Velký atribut
□ The Oversized-Attribute Storage Technique
■
TOAST or "the best thing since sliced bread"** ■ Rozdělení záznamu (viz předchozí)
□ Resp. dlouhých hodnot ve velkém atributu
□ Komprese
□ Rozdělení do více záznamů (interně)
** [cit. dokumentace PostgreSQL]
PA152, Vlastislav Dohnal, FI MUNI, 2011
39
"d ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Rozdělování záznamU
■ Velká data (LOB)
□ Bez ohledu na typ: binární i textová
□ Uloženo zvlášť - posloupnost blokU
□ DB neindexuje, neumí uvnitř vyhledávat
** [cit. dokumentace PostgreSQL]
PA152, Vlastislav Dohnal, FI MUNI, 2011
40
Uspořádání záznamů
■ Záznamy jsou v souboru (a bloku) uspořádány
□ Podle hodnoty nějakého klíče
□ Např. sekvenční soubor
■ Důvod:
□ Efektivní čtení záznamů v daném pořadí
□ Např. pro merge-join, order by, ...
PA152, Vlastislav Dohnal, FI MUNI, 2011
41
Uspořádání záznamů
■ Uložené za sebou
R1	R2	R3	■ ■ ■
■
Zřetězený seznam
R1
R2
R3
PA152, Vlastislav Dohnal, Fl MUNI, 2011
42
Uspořádání záznamů
■ Přetoková oblast
□ Záznamy jsou uložené za sebou
■ nutné reorganizace při aktualizaci
□ -— přetoková oblast
blok
hlavička
Rl
R2
R3
R4
R5
PA152, Vlastislav Dohnal, FI MUNI, 2011
43
Odkazy na záznamy
■ Potřeba kvUli:
□ Rozdělování záznamU
□ Odkazování blokU / záznamU (viz indexy)
□ Zřetězování blokU (viz indexy)
□ OODBMS: objekty ukazují na jiné objekty
■ Adresa záznamu
□ V paměti: 4 (8) bajtový ukazatel
□ V úložišti: sekvence bajtU popisující
■ ID disku, stopu, povrch, blok, offset v bloku
PA152, Vlastislav Dohnal, FI MUNI, 2011
44
Odkazy na záznamy (2)
■
■
■
Fyzická adresa záznamu
□ Adresa v úložišti, nevhodné pro přímé použití
■ Např. realokace bloku nebo záznamu
Záznam (i blok) je identifikován svým ID
□ ID (logická adresa): libovolná posloupnost bitů
Adresace je nepřímá
□ Převodní tabulka (map table): ID    fyz. adresa
rec ID r
ID I fyz. adresa
adresa a
PA152, Vlastislav Dohnal, Fl MUNI, 2011
45
"■' ^^^^^^^^^^^^^^^^^^^^^^^^
Odkazy na záznamy (3)
■ Nepřímá adresace
□ Nevýhoda: zvýšené náklady
■ prUchod map table
□ Výhoda: velká flexibilita
■ Mazání záznamU, vkládání
■ Optimalizace uložení blokU
PA152, Vlastislav Dohnal, FI MUNI, 2011
46
Odkazy na záznamy (4)
■ Vhodná varianta je kombinace:
□ Fyz. adresa záznamu = fyz. adr. bloku + offset
■ Offset je pořadí záznamu v bloku
□ V hlavičce je obvykle seznam odkazů na záznamy.
□ Výhoda:
■ Lze přesouvat záznamy v bloku beze změny fyz. adresy
■ Lze přesunout záznam do jiného bloku
□ V původním místě udělám odkaz na nový blok + offset
Lze zrušit map table
■
PA152, Vlastislav Dohnal, FI MUNI, 2011
47
Odkazy na záznamy (5)
■ Používaná varianta
□ Adresa záznamu =
ID souboru + číslo bloku + offset v bloku
□ Uložení bloku určuje systém souborů (file system)
File ID, _^ / File System\ Physical
Block #
Block ID
PA152, Vlastislav Dohnal, FI MUNI, 2011
48
Odkazy na záznamy (6)
■
Nepřímý odkaz v bloku
□ Fyz. adresa záznamu = fyz. adr. bloku + offset
hlavička
blok
		\	\	/	
	'A				
					
					
Rl /			^R2		
r volné místo
PA152, Vlastislav Dohnal, FI MUNI, 2011
49
Hlavička bloku
■ Informace přítomná v každém bloku
□ File ID (or RELATION ID or DB ID)
□ ID bloku (tohoto)
□ Adresář záznamU (odkazy na data záznamU)
□ Ukazatel na volné místo (začátek, konec)
□ Typ bloku
■ např. záznamy typu 4, přetoková oblast, TOAST table, ...
□ Ukazatel na další blok (např. pro indexy)
□ Čas modifikace (popř. verze)
PA152, Vlastislav Dohnal, FI MUNI, 2011
50
Modifikace záznamů
■ Vkládání
□ Obvykle snadné
■ Mazání
□ Správa volného místa
■ Změna
□ Stejná velikost
■ ok
□ Jiná velikost
■ problém stejný jako při vkládání / mazání
PA152, Vlastislav Dohnal, FI MUNI, 2011
51
Mazání záznamU
■ Problém s odkazy na smazané záznamy
□ Musí být neplatné
□ Nesmí odkazovat na jiná nová data
□ Tzv. dangling pointers
R1			■
			
smazaný záznam
PA152, Vlastislav Dohnal, FI MUNI, 2011
52
Mazání záznamů (2)
■ Adresa záznamu je offset v bloku
□ Ihned uvolni místo
□ Posuň ostatní záznamy, aby volné místo bylo souvislé
□ V adresáři záznamů nastav ukazatel na null
blok
} volné místo
PA152, Vlastislav Dohnal, Fl MUNI, 2011
Mazání záznamů (3)
■ Adresa záznamu je fyzická adresa
blok _Hl
nelze znovu využit x    volné místo
□ Označ jako smazané
Vytvořením značky (tombstone) Stačí 1 bit, ale obvykle několik bajtů (zarovnání)
□ Oznámit volné místo
■ Zřetězení volných míst
PA152, Vlastislav Dohnal, FI MUNI, 2011
54
BJ ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Mazání záznamů (4)
■ Nepřímá adresace
□ Map table
□ Smazaný záznam uvolní místo v bloku
□ Náhrobek je v map table
Map Table
ID	LOC
	
77BB	
	
Tuto položku nelze již znovu využít.
PA152, Vlastislav Dohnal, Fl MUNI, 2011
SS
Mazání záznamů (5)
■ Uložení ID záznamu přímo v záznamu
□ Při čtení záznamu kontrolujeme ID na shodu
PA152, Vlastislav Dohnal, FI MUNI, 2011
56
"a1 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Vkládání záznamů
■ Neuspořádané záznamy
□ Vkládáme na konec (poslední blok, popř. nový)
□ Vkládáme do volného místa v existujícím bloku
■ Může být problematické v případě proměnlivé délky záznamu
PA152, Vlastislav Dohnal, FI MUNI, 2011
57
Vkládání záznamU (2)
■ Uspořádané záznamy
□ Nemožné, pokud není nepřímá adresace a nepoužívají se offsety
□ Najdi místo v „blízkém" bloku — reorganizuj
■ Přesunutí posledního záznamu do následujícího bloku — nutné přidat příznak do pUvodního bloku
□ Ulož do přetokového bloku
■ Odkaz na přetokový blok je součástí hlavičky bloku
PA152, Vlastislav Dohnal, FI MUNI, 2011
58
"a1 ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Aktualizace záznamU
■ Zvětšení délky záznamu
□ Nemusí se vytvářet náhrobky
□ Posunout následující záznamy
□ Vytvořit přetokový blok □...
■ Zmenšení délky záznamu
□ dtto
□ Zrušení uvolněných přetokových blokU
PA152, Vlastislav Dohnal, FI MUNI, 2011
59
Správa vyrovnávací paměti
■ Různé strategie
□ LRU, FIFO, pinned blocks, toss-immediate, ...
■ Problém odkazování na záznamy v paměti
□ Prohazování odkazů (swizzling)
PA152, Vlastislav Dohnal, FI MUNI, 2011
Rn
Správa vyrovnávací paměti
■ LRU
□ Při každém přístupu aktualizovat čas přístupu
□ -— může být časově náročné
■ FIFO
□ Uloží se čas načtení a ten se dále nemění
□ — nevhodné pro stále používané bloky
■ Např. kořen B+ stromu
■ Pinned blocks
□ Bloky trvale v paměti (připíchnuté)
PA152, Vlastislav Dohnal, FI MUNI, 2011
61
Správa vyrovnávací paměti
■ Hodiny („Clock") - aproximace LRU
ručka otáčí, dokud nenalezne blok ĽU [0 t0 s nulou.
□ Pak načte požadovaný blok a nastaví 1
□ Ručka při otáčení snižuje číslo (až na nulu).
■ Lze implementovat i pinned blocks
□ Efektivní
□ Ručka ukazuje na poslední
000
načtený blok. □ Pro načtení nového bloku se
PA152, Vlastislav Dohnal, Fl MUNI, 2011
62
Správa vyrovnávací paměti
■ LRU a výpočet spojení dvou relací:
□ Vnořené cykly:
buffers
For each ts in s do For each tr in r do Spoj tr and ts
buffers buffers
buffers
r1
s1
r2
s2
r3
s1
r2
3
r3 U
^3
r2
3
r3 s1
r1
6
Načtení 1. záznamu Načtení 2. záznamu Zpracovávání r z s a zpracovávání r   z s
□ LRU nevhodný: přepisují se bloky relace s
■ Nutné použít pinned blocks pro relaci s
r
PA152, Vlastislav Dohnal, FI MUNI, 2011
63
Prohazování odkazů
■
■
Změna odkazů při načtení bloku do paměti
□ a zpět (při ukládání na disk)
Odkaz pak ukazuje do paměti a ne na disk
Paměť
blok 1
Disk
blok 1
blok 2
PA152, Vlastislav Dohnal, FI MUNI, 2011
64
Prohazování odkazů (2)
■
Po načtení bloku 2 je provedena změna odkazu
Paměť
blok l
blok 2
Disk
blok l
blok 2
PA152, Vlastislav Dohnal, FI MUNI, 2011
R5
"d ^^^^^^^^^^^^^^^^^^^^^^^^^^^
Prohazování odkazU (3)
■ Kdy:
□ Automaticky - ihned po načtení
□ Na žádost - při prvním použití
□ Nikdy - vždy se používá překladová tabulka
■ Implementace:
□ DB adresa je měněna na paměťovou adresu
■ Buduje se Translation table
□ dvojice (paměť. adresa, disková adresa) pro každý záznam
□ Ukazatel má příznak, zda byl prohozen či ne
PA152, Vlastislav Dohnal, FI MUNI, 2011
"■' ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Vlastní implementace
Flexibilita - Využití místa
Složitost - Výkonnost
■ Otázka náročnosti operací:
□ Načtení záznamu s daným klíčem
■ Načtení následujícího záznamu
□ Vložení / smazání / aktualizace záznamU
□ Čtení celého souboru
□ Reorganizace souboru
PA152, Vlastislav Dohnal, FI MUNI, 2011
67
Osnova
■ Ukládání dat
■ Záznamy
■ Organizace bloků
■ Příklady
PA152, Vlastislav Dohnal, FI MUNI, 2011
68
Specializované implementace
■ BigTable
□ Distribuované úložiště n-tic od Google
□ Škálovatelost do petabajtů (1PB=1000TB)
F. Chang, J. Dean, S. Ghemawat, et al.:
Bigtable: A Distributed Storage System for Structured Data,
Seventh Symposium on Operating System Design and
Implementation (OSDI), 2006.
http://labs.google.com/papers/bigtable-osdi06.pdf
■ HBase
□ Distribuované úložiště n-tic
□ Open-source Apache projekt Hadoop
http://hadoop.apache.org/
PA152, Vlastislav Dohnal, FI MUNI, 2011
69