wyk9

Indeksy
Wykład 9
Prowadzący: dr Paweł Drozda
Pamięć fizyczna
o�Pamięć operacyjna zorganizowana
w bloki
o�Pamięć zewnętrzna zorganizowana
w pliki
o�Dane z BD przechowywane w pamięci
zewnętrznej:
Rozmiar danych
Koszt przechowywania
Odporność na awarie
dr Paweł Drozda
Dostęp do danych
o�Dane są zestawione w rekordy (proste,
złożone, stała/zmienna długość)
o�Operacje na danych
Buforowanie danych z plików do bloków
Operacje w blokach (pamięć operacyjna)
Po modyfikacjach zapis do pliku
dr Paweł Drozda
Rodzaje organizacji plików
o� Pliki nieuporządkowane (unordered
files, heap files)
o� Pliki uporządkowane (ordered files)
o� Pliki haszowe (hash files)
dr Paweł Drozda
Plik nieuporządkowany
o�Nagłówek pliku zawierający wskaznik
do bloku danych
o�Blok danych zawiera wskaznik do
bloku następnego I poprzedniego
o�Rekordy wstawiane na koniec pliku
dr Paweł Drozda
Plik nieuporządkowany - operacje
o� Dodawanie do ostatniego bloku pliku
o� Wyszukanie przeszukanie liniowe wszystkich
bloków (do momentu natrafienia na szukaną
wartość)
o� Wyszukanie z przedziałem wartości
przeszukanie całego pliku
o� Usuwanie przeszukanie liniowe wszystkich
bloków, konieczność okresowej reorganizacji
pliku
o� Sortowanie trudne (na ogół odbywa się w
pamięci operacyjnej fragmentami)
dr Paweł Drozda
Plik nieuporządkowany - cechy
o�Aatwe, efektywne wstawianie
o�Efektywne pozostałe operacje przy
małych plikach
o�Właściwy do odczytu wszystkich
rekordów
o�Potrzeba wspomagania (np. Indeksy)
dr Paweł Drozda
Plik uporządkowany
o�Rekordy uporządkowane według pola
porządkującego Adam &
Adrian
Anna
Bartosz
Bernard
Bogumiła
Pankracy
Paulina
&
Roman
dr Paweł Drozda
Plik uporządkowany - operacje
o� Dodawanie Wyszukanie miejsca wstawienia,
przepisanie rekordów po wstawionym
o� Wyszukanie binarne
o� Wyszukanie z przedziałem wartości
znalezienie początku oraz przejście przez
rekordy z przedziału
o� Usuwanie - Wyszukanie miejsca usunięcia,
przepisanie rekordów po usuniętym
o� Modyfikacja gdy modyfikowany atrybut
porządkujący usunięcie + wstawienie rekordu
dr Paweł Drozda
Plik uporządkowany - cechy
o� Efektywny odczyt rekordów w kolejności
pola porządkującego
o� Proste znalezienie następnego rekordu
o� Binarne wyszukanie w oparciu o pole
porządkujące
o� Nieprzydatne, gdy nie używa się pola
porządkującego przy wyszukiwaniu
o� Kosztowne wstawianie, usuwanie i
modyfikacja
dr Paweł Drozda
Plik haszowy
o�Porządek rekordów w pliku określony
na podstawie tzw. pola haszowego
o�Koncepcja zdefiniowanie funkcji
haszowej (ang. hash function)
argument - wartość pola haszowego
wartość funkcji adres bloku dla rekordu
o�Haszowanie
Wewnętrzne
zewnętrzne
dr Paweł Drozda
Haszowanie wewnętrzne
o�Dana tablica rekordów o M szczelinach
których adresy odpowiadają indeksom
tablicy haszowej
o�Funkcja: H(K) ą� {0,1,& ,M-1}
o�Najczęściej spotykana H(K) = K mod M
dr Paweł Drozda
Haszowanie wewnętrzne - przykład
szczelina
nrindeksu nazwisko adres
0 127000 Maliniak Świerkowa 6
123001 Kowal Akacjowa 1
1 123001 Kowal Akacjowa 1
127000 Maliniak Świerkowa 6
2 666002 Nowak Różana 4/78
666002 Nowak Różana 4/78
Funkcja haszująca:
H(nrindeksu) = nrindeksu mod 1000
dr Paweł Drozda
Haszowanie wewnętrzne - operacje
o�Kolizje gdy ta sama szczelina dla
dwóch wartości pola haszowego
o�Trzy rodzaje rozwiązania kolizji
Adresowanie otwarte
Aańcuchowanie
Haszowanie wielokrotne
o�Dla każdej metody różne algorytmy
wstawiania, szukania, usuwania
rekordów
dr Paweł Drozda
Haszowanie zewnętrzne
o�Podobnie jak wewnętrzne używa
funkcji haszowej
o�Odwołuje się bezpośrednio do
przestrzeni dyskowej
o�Rzadziej kolizje niż w wewnętrznym
w jednej szczelinie przechowywanych
więcej rekordów
dr Paweł Drozda
Pliki haszowe - cechy
o�Ważna definicja funkcji haszowej,
aby rozkładała rekordy równomiernie
o�Zakładany jest stały obszar
przestrzeni haszowej co po jakimś
czasie powoduje częste kolizje
o�Nieefektywny odczyt w kolejności
pola haszowego funkcja haszująca
burzy porządek tego pola
dr Paweł Drozda
Indeks - wprowadzenie
o� Problem jak efektywnie wyszukiwać
rekordów z zadanego zakresu wartości
wybranego pola?
o� Stworzenie pliku zdefiniowanego na atrybucie
po którym dokonywane jest wyszukanie
o� Zawartość pliku rekordy odpowiadające
wartościom pierwszych rekordów w
poszczególnych blokach pliku danych

dr Paweł Drozda
Indeks
o�Stworzony plik nazywamy indeksem
o�Cechy indeksu:
Przyśpiesza dostęp do danych
Zakładany na atrybutach relacji
(atrybuty indeksowe)
Rekord indeksu zawiera dwa pola:
o�Klucz (odnosi się do atrybutu indeksowego)
o�Wskaznik do bloku mającego ten sam klucz
dr Paweł Drozda
Indeks - SQL
o�CREATE INDEX nazwaindeksu ON
nazwatabeli(pole1,pole2,& ,polen);
o�tworzenie indeksu z pól od 1 do n dla
tabeli nazwatabeli
dr Paweł Drozda
Typy rekordów indeksu
o�Rekord danych (o wartości klucza k)
o�Para - rid identyfikator
rekordu danych o wartości klucza k
o�Para - rid-list lista
identyfikatorów rekordów danych o
wartości klucza k
o�Para - bitmapa jest
wektorem 0,1 reprezentującym zbiór
rekordów danych
dr Paweł Drozda
Rodzaje indeksów
o�Atrybut indeksowy
Podstawowy założony na atrybucie
porządkującym unikalnym
Zgrupowany założony na atrybucie
porządkującym nieunikalnym
Wtórny założony na atrybucie
nieporządkującym
dr Paweł Drozda
Rodzaje indeksów
o�Wskazania do pliku danych:
Gęsty posiada rekord indeksu dla
każdego rekordu indeksowanego pliku
danych
Rzadki tylko dla wybranych rekordów
pliku danych
o�Liczba poziomów:
Jednopoziomowe indeks dla danych
Wielopoziomowe indeks do indeksu
dr Paweł Drozda
Indeks podstawowy przykład
Adams
Wartość
wskaznik &
indeksowana
do bloku
Agor
Adams
Basior
& &
Basior
Berent
& &
Gawron
Gawron
& &
&
Kawar
Gnied
& &
Kawar
&
Kozak
dr Paweł Drozda
Pole
porządkujące
unikalne
Indeks zgrupowany przykład
1
Wartość
wskaznik 1
indeksowana
do bloku
2
1
2
2
2
3
3
4
5
3
&
3
10
3
&
4
&
dr Paweł Drozda 11
Indeks wtórny - przykład
65
Wartość wskaznik
1
indeksowana do bloku
17
1
2 5
6
3
2
4
5
7
6
3
&
34
23
4
dr Paweł Drozda 11
Indeks o kluczu złożonym
indeks
indeks
2800; Kozak
Kozak 2800 Wiązowa
Gordon;4200 3600; Malec
Gordon 4200 Akacjowa
Kozak;2800 4200; Gordon
Wasiak 4900 Tęczowa
Malec;3600 4900; Wasiak
Malec 3600 Słoneczna
Wasiak;4900
Atrybut wiodący - Atrybut wiodący -
nazwisko zarobki
dr Paweł Drozda
Indeks wielopoziomowy ISAM
(Index Sequential Access Method)
o� ISAM
Poziom pierwszy indeks cylindrów adres indeksu ścieżki>
Poziom drugi indeks ścieżki ścieżki>
Struktura związana ze sprzętem
Indeks statyczny (po usunięciu puste obszary,
bloki nadmiarowe dla wstawianych rekordów,
modyfikacja degeneruje indeks)
o� VSAM Virtual Sequential Access Method
Rozwinięcie ISAM
Niezależne od sprzętu
dr Paweł Drozda
Indeks wielopoziomowy
Indeks pierwszego
1
poziomu
3
1
4
4
7
8
Indeks drugiego
8
poziomu
10
9
18
25
1
10
10
32
15
32
38
51
44
18
22
51
58
25
67
26
dr Paweł Drozda
Indeks dynamiczny
o�Najczęściej stosowane indeksy
drzewiaste
korzeń
Poziom 0
A
węzeł
B
Poziom 1
D
C
Poziom 2
H
E F G
liść
Poziom 3
I J K
dr Paweł Drozda
Indeks B+ drzewo
o� Zrównoważona struktura drzewiasta
każdy liść na tym samym poziomie
Węzły wspomagają wyszukiwanie
Liście wskazują na rekordy danych
Liście stanowią listę dwukierunkową
o� Wstawianie i usuwanie rekordów
pozostawiają indeks zrównoważony
o� Wyszukanie rekordu przejście od korzenia
do liścia (długość ścieżki od korzenia do
liścia wysokość drzewa indeksu)
dr Paweł Drozda
Struktura indeksu B+ drzewa
7
X>7
X<=7
5 10 15
1 4 6 7 8 10 12 13 17 18
Przestrzeń dyskowa
dr Paweł Drozda
Węzeł wewnętrzny
o� Struktura
, K1< K2<& < Kn
Pi wskaznik do poddrzewa
Ki wartość klucza indeksu
o� Lewy wskaznik klucza Ki odnosi się do
poddrzewa z wartościami mniejszymi bądz
równymi kluczowi, prawy do wartości
większych
o� p rząd indeksu = maksymalna liczba
wskazników w węzle
dr Paweł Drozda
Liść
o�Struktura
,& ,, Pnext> ,
K1< K2<& < Kn
o�Pprev wskaznik do poprzedniego
liścia
o�Pnext wskaznik do następnego liścia
dr Paweł Drozda
Obliczanie rzędu indeksu p
o� Dane
rozmiar klucza - V
rozmiar wskaznika do bloku - P
rozmiar bloku - B
liczba rekordów w pliku danych - r
liczba bloków pliku - b
o� Rząd indeksu p spełnia nierówność:
(p*P)+(p-1)V<=B
h =�
o� min wysokość indeksu rzadkiego:
��log bł�
p
h =�
o� min wysokość indeksu gęstego:
��log rł�
p
dr Paweł Drozda
Rząd indeksu - przykład
r=30000, B=1024B, R=100B, V=9B, P=6B
indeks wtórny, rekordy nie są dzielone
między bloki
liczba rekordów w bloku rbl = B/R =10
liczba bloków b=r/rbl = 3000
Rząd indeksu p<=(V+B)/(P+V), p=68
min wysokość indeksu
h=log6830000=3
dr Paweł Drozda
Rząd indeksu koszt wyszukania
o�bez indeksu:
średnio liczba bloków danych/2=1500
o�z B+ drzewem: wysokość drzewa + 1=4
odczytanie korzenia,
odczytanie węzła,
odczytanie liścia,
odczytanie bloku rekordów zawierającego
szukany rekord
dr Paweł Drozda

Wyszukiwarka

Podobne podstrony:
IB wyk9
wyk9
Wyk9 term
wyk9

więcej podobnych podstron