1 Systemy zarządzania bazami danych 3. IndeksyOryginał: Hector Garcia-Molina 3. Indeksy

2 Indeksowanie i haszowaniewartość Indeksy konwencjonalne B-drzewa i B+drzewa Haszowanie rekord(y) ? wartość Oryginał: Hector Garcia-Molina 3. Indeksy

3 Plik uporządkowany 20 10 40 30 60 50 80 70 100 90 Oryginał: Hector Garcia-Molina 3. Indeksy

4 Plik uporządkowany Indeks gęsty 10 20 30 40 50 60 70 80 90 100 10 20110 120 100 90 Oryginał: Hector Garcia-Molina 3. Indeksy

5 Indeks rzadki Plik uporządkowany 10 20 30 40 50 60 70 80 90 100 10 30110 130 150 60 50 80 70 170 190 210 230 100 90 Oryginał: Hector Garcia-Molina 3. Indeksy

6 Rzadki indeks Plik uporządkowany 2. poziomu 10 20 30 40 50 60 70 80 90170 250 10 30 50 70 40 30 90 110 130 150 330 410 490 570 60 50 80 70 170 190 210 230 100 90 Oryginał: Hector Garcia-Molina 3. Indeksy

7 Pytanko Czy ma sens gęsty indeks drugiego poziomu?Oryginał: Hector Garcia-Molina 3. Indeksy

8 Wskaźniki do rekordów Wskaźnik do bloku (w indeksie rzadkim) jest mniejszy niż wskaźnik do rekordu WdB WdR Jeśli plik jest fizycznie ciągły, możemy wyliczać wskaźniki (i ich nie zapisywać) Oryginał: Hector Garcia-Molina 3. Indeksy

9 K1 K2 K3 K4 R1 R2 Załóżmy, że bloki mają 1KB R3 R4 rekordu o kluczu K3szukamy w bloku o offsecie (3-1)1024 = 2048 bajtów K2 K3 R3 K4 R4 Oryginał: Hector Garcia-Molina 3. Indeksy

10 Kompromis: indeks gęsty czy rzadki?Mniej miejsca na indeks Więcej indeksu mieści się w RAM Gęsty Możemy sprawdzić, czy jest taki rekord bez zaglądania do pliku Możliwe użycie strategii „tylko-indeks” Oryginał: Hector Garcia-Molina 3. Indeksy

11 Pojęcia Uporządkowany plik indeksowyKlucz wyszukiwania (nie zawsze klucz!) Indeks główny (na polu porządkującym) Indeks niegłówny (drugorzędny) Indeks gęsty lub rzadki Indeks pogrupowany lub niepogrupowany Indeks wewnętrzny lub zewnętrzny Indeks wielopoziomowy Oryginał: Hector Garcia-Molina 3. Indeksy

12 Powtarzalne klucze 10 20 10 30 20 30 45 40 Oryginał: Hector Garcia-Molina 3. Indeksy

13 Powtarzalne klucze Czy indeks gęsty to jedyna możliwość? 10 10 20 1030 20 30 20 20 20 30 30 30 30 30 30 30 30 45 40 45 40 Oryginał: Hector Garcia-Molina 3. Indeksy

14 Powtarzalne klucze Indeks gęsty, czy lepszy pomysł? 10 10 20 20 30 3040 30 20 30 45 40 Oryginał: Hector Garcia-Molina 3. Indeksy

15 Powtarzalne klucze A może jednak rzadki? Oto pierwszy pomysł:Starannie szukaj 20 i 30 10 10 10 20 20 10 30 30 20 30 45 40 Oryginał: Hector Garcia-Molina 3. Indeksy

16 Powtarzalne klucze Rzadki: tylko pierwszy nowy klucz z bloku Może10 Może ma być 40? 10 20 30 20 10 30 30 20 30 45 40 Oryginał: Hector Garcia-Molina 3. Indeksy

17 Powtarzalne klucze, indeks głównyIndeks może wskazywać tylko pierwsze wystąpienie każdej wartości klucza Plik Indeks a a a . b Oryginał: Hector Garcia-Molina 3. Indeksy

18 Usuwanie z indeksu rzadkiego20 10 10 30 50 40 30 70 60 50 90 110 130 80 70 150 Oryginał: Hector Garcia-Molina 3. Indeksy

19 Usuwanie z indeksu rzadkiegousuń rekord 40 20 10 10 30 50 40 30 70 60 50 90 110 130 80 70 150 Oryginał: Hector Garcia-Molina 3. Indeksy

20 Usuwanie z indeksu rzadkiegousuń rekord 30 20 10 10 40 30 50 40 30 70 60 50 90 110 130 80 70 150 Oryginał: Hector Garcia-Molina 3. Indeksy

21 Usuwanie z indeksu rzadkiegousuń rekordy 30 i 40 20 10 10 50 70 30 50 40 30 70 60 50 90 110 130 80 70 150 Oryginał: Hector Garcia-Molina 3. Indeksy

22 Usuwanie z indeksu gęstego20 10 10 20 30 40 30 40 60 50 50 60 70 80 70 80 Oryginał: Hector Garcia-Molina 3. Indeksy

23 Usuwanie z indeksu gęstegousuń rekord 30 20 10 10 20 40 40 30 30 40 40 60 50 50 60 70 80 70 80 Oryginał: Hector Garcia-Molina 3. Indeksy

24 Wstawienie, indeks rzadki20 10 10 30 40 30 60 50 40 60 Oryginał: Hector Garcia-Molina 3. Indeksy

25 Wstawienie, indeks rzadkiwstaw rekord 34 20 10 10 30 40 30 34 dziś mamy szczęście! wolne miejsce jest tam gdzie go potrzebujemy 60 50 40 60 Oryginał: Hector Garcia-Molina 3. Indeksy

26 Wstawienie, indeks rzadkiwstaw rekord 15 20 10 15 20 30 10 30 40 30 60 50 40 Tu: natychmiastowa reorganizacja Inne opcje: Dodać blok nadmiarowy Poprawić indeks 60 Oryginał: Hector Garcia-Molina 3. Indeksy

27 Wstawienie, indeks rzadkiwstaw rekord 25 20 10 25 Lista bloków nadmiarowych (reorganizacji później...) 10 30 40 30 60 50 40 60 Oryginał: Hector Garcia-Molina 3. Indeksy

28 Wstawienie, indeks gęstyPodobnie Zwykle jednak bardziej kosztowne Oryginał: Hector Garcia-Molina 3. Indeksy

29 Indeksy drugorzędne 50 30 70 20 40 80 10 100 60 90 Oryginał: Hector Garcia-Molina 3. Indeksy

30 Indeksy drugorzędne Chyba nie zadziała? Indeks rzadki 30 50 20 70 80100 70 20 90 ... 40 80 10 100 60 90 Oryginał: Hector Garcia-Molina 3. Indeksy

31 Indeksy drugorzędne Indeks gęsty rzadki wyższy poziom 30 50 20 70 8010 20 30 40 50 60 70 ... 50 30 10 50 90 ... rzadki wyższy poziom 70 20 40 80 10 100 60 90 Oryginał: Hector Garcia-Molina 3. Indeksy

32 Indeksy drugorzędne Najniższy poziom musi być gęstyWszystkie pozostałe są rzadkie Wskaźniki są wskaźnikami na rekordy Nie: wskaźniki blokowe Nie: wyliczane Oryginał: Hector Garcia-Molina 3. Indeksy

33 Klucze powtarzalne i indeks drugorzędny10 20 40 20 40 10 40 10 40 30 Oryginał: Hector Garcia-Molina 3. Indeksy

34 Klucze powtarzalne i indeks drugorzędnyPierwszy pomysł... 10 20 10 20 Problem: Nadmierny narzut miejsce na dysku czas wyszukiwania 40 20 20 30 40 40 10 40 10 40 ... 40 30 Oryginał: Hector Garcia-Molina 3. Indeksy

35 Klucze powtarzalne i indeks drugorzędnyInny pomysł... 10 20 10 Problem: Indeks zawiera rekordy rozmiaru zmiennego 40 20 20 40 10 30 40 40 10 40 30 Oryginał: Hector Garcia-Molina 3. Indeksy

36 Klucze powtarzalne i indeks drugorzędny10 20  10 20 30 40 40 20 40 10 50 60 ... 40 10  Trzeci pomysł: lista rekordów o tej samej wartości klucza? 40 30   Problemy: Dodatkowe pole w rekordzie Liniowe przeszukiwanie listy rekordów Oryginał: Hector Garcia-Molina 3. Indeksy

37 Klucze powtarzalne i indeks drugorzędny10 20 10 20 30 40 40 20 50 60 ... 40 10 40 10 40 30 kubełki Oryginał: Hector Garcia-Molina 3. Indeksy

38 Pomysł z kubełkami jest dobryPo pierwsze rekordy indeksy stałej długości Przykładowy schemat Indeksy Rekordy Name: główny EMP (name,dept,floor,...) Dept: drugorzędny Floor: drugorzędny Oryginał: Hector Garcia-Molina 3. Indeksy

39  Oblicz przecięcie obu kubełków, żeby znaleźć pasujących pracownikówZnajdź pracowników z działu Toy i 2. piętra: (‘Toy’ = Dept) ^ (floor = 2 ) Indeks na Dept Plik EMP Indeks na floor Toy 2  Oblicz przecięcie obu kubełków, żeby znaleźć pasujących pracowników Oryginał: Hector Garcia-Molina 3. Indeksy

40 Ten pomysł jest stosowany do wydobywania informacji z tekstu (IR)Dokumenty Listy odwrócone cat dog ...the cat is fat ... ...was raining cats and dogs... ...Fido the dog ... Oryginał: Hector Garcia-Molina 3. Indeksy

41 Zapytania IR (Information Retrieval)Znajdź dokumenty zawierające “cat” i “dog” Znajdź dokumenty zawierające “cat” lub “dog” Znajdź dokumenty zawierające “cat” ale bez “dog” Znajdź dokumenty zawierające “cat” w tytule Znajdź dokumenty zawierające “cat” i “dog” w odległości co najwyżej 5 słów Oryginał: Hector Garcia-Molina 3. Indeksy

42 Więcej danych na liście odwróconejmiejsce nr znaku wskaźnik d1 cat Tytuł 5 Autor 10 Streszczenie 57 d2 d3 dog Tytuł 100 Tytuł 12 Oryginał: Hector Garcia-Molina 3. Indeksy

43 Hasło = pozycja listy odwróconejReprezentuje wystąpienie słowa w dokumencie Długość listy: 1 Słowa rzadkie (liczba haseł) lub błędy ortograficzne 106 Słowa często używane Rozmiar hasła: bitów (po kompresji) Oryginał: Hector Garcia-Molina 3. Indeksy

44 Zagadnienia IR Słowa ignorowane Skracanie słów Wyrazy bliskoznaczneFleksja (zwłaszcza w polskim: liczne pułapki) Po normalizacji słów okazało się że najczęściej w Panu Tadeuszu występuje słowo „oda” (od) Błędy ortograficzne Pełne teksty czy Streszczenia Model wektorowy Oryginał: Hector Garcia-Molina 3. Indeksy

45 Model przestrzeni wektorowejs1 s2 s3 s4 s5 s6 s7 … Dokument= < …> Zapytanie = < …> Koniunkcja= … = punktacja Oryginał: Hector Garcia-Molina 3. Indeksy

46 Usprawnienia IR Model wektorowy przypomina listy bitmapoweRóżne sposoby ważenia punktacji i normalizacji, np. Dopasowanie słowa częstego nie jest tak znaczące (wartościowe) jak słowa rzadkiego Implementacja: Google, Altavista, ... Oryginał: Hector Garcia-Molina 3. Indeksy

47 Indeksy konwencjonalneZalety Proste Indeks jest plikiem uporządkowanym wygodnym przy pełnych przeglądach Wady Wstawienia są kosztowe lub Tracimy fizyczne uporządkowanie lub równowagę Oryginał: Hector Garcia-Molina 3. Indeksy

48 Przykład gnicia indeksu konwencjonalnegociągła alokacja wolne miejsce 10 39 31 35 36 32 38 34 33 Bloki nadmiarowe (nieciągłe) 20 30 40 50 60 70 80 90 Oryginał: Hector Garcia-Molina 3. Indeksy

49 Lekarstwo Nowy rodzaj indeksuRezygnujemy z ciągłej alokacji stron indeksu Staramy się by się sam równoważył Rodzaje drzew równoważących się: AVL, czerwono-czarne, B-drzewa W bazach danych B-drzewa, w właściwie B+drzewa Oryginał: Hector Garcia-Molina 3. Indeksy

50 Przykład B+drzewa n=3 Korzeń 100 120 150 180 30 3 5 11 120 130 180 20035 100 101 110 150 156 179 Oryginał: Hector Garcia-Molina 3. Indeksy

51 Przykładowy węzeł wewnętrzny57 81 95 do kluczy do kluczy do kluczy do kluczy <  k<81 81k<95 95 Oryginał: Hector Garcia-Molina 3. Indeksy

52 Przykładowy liść Z pewnego nie-liścia do następnego w kolejności57 81 95 Do rekordu o kluczu 57 o kluczu 81 o kluczu 85 Oryginał: Hector Garcia-Molina 3. Indeksy

53 Rozmiar węzłów Rozmiar stały n wartości kluczy n+1 wskaźnikówjeśli klucze stałego rozmiaru... n wartości kluczy n+1 wskaźników Liść: n wskaźników na rekordy i fastryga Nie-liść: n+1 wskaźników na niższy poziom Oryginał: Hector Garcia-Molina 3. Indeksy

54 Węzły nie mogą być zbyt pusteZapełnienie co najmniej 50% Teoretycznie... Praktycznie w zasadzie tak, ale nie do końca Zapełnienie co najmniej Nie-liść: (n+1)/2 wskaźników Liść: (n+1)/2 wskaźników na dane Oryginał: Hector Garcia-Molina 3. Indeksy

55 Liczy się nawet gdy NULLZapełniony Minimalny Nie-liść Liść 120 150 180 30 3 5 11 30 35 Liczy się nawet gdy NULL Oryginał: Hector Garcia-Molina 3. Indeksy

56 Reguły B+drzew Wszystkie liście są na tym samym poziomie (drzewo zrównoważone) Wskaźniki w liściach wskazują rekordy (z wyjątkiem fastrygi) Oryginał: Hector Garcia-Molina 3. Indeksy

57 3. Liczba wskaźników i kluczyStopień drzewa = n Max Max Min Min wsk. klu. wsk.dane klu. Nie-liść (nie-korzeń) n+1 n (n+1)/2 (n+1)/2- 1 Liść (nie-korzeń) n+1 n (n+1)/2 (n+1)/2 Korzeń n+1 n 1 1 Oryginał: Hector Garcia-Molina 3. Indeksy

58 Wstawienie do B+drzewa(a) Przypadek najłatwiejszy Gdy w liściu jest wolne miejsce (b) Przepełnienie liścia (c) Przepełnienie węzła wewnętrznego (d) Nowy korzeń Oryginał: Hector Garcia-Molina 3. Indeksy

59 (a) Wstaw klucz = 32 n=3 100 30 3 5 11 30 31 32 Oryginał: Hector Garcia-Molina 3. Indeksy

60 (b) Wstaw klucz = 7 n=3 100 30 7 3 5 11 30 31 3 5 7 Oryginał: Hector Garcia-Molina 3. Indeksy

61 (c) Wstaw klucz = 160 n=3 100 160 120 150 180 180 150 156 179 180 200 160 179 Oryginał: Hector Garcia-Molina 3. Indeksy

62 (d) Wstaw 45 – nowy korzeń n=3 30 Nowy korzeń 10 20 30 40 1 2 3 10 1225 30 32 40 40 45 Oryginał: Hector Garcia-Molina 3. Indeksy

63 Usunięcie z B+drzewa Przypadek najłatwiejszyScal się z sąsiadem (bliźniakiem) Poprzerzucaj klucze Przypadki (b) lub (c) w nie-liściu Oryginał: Hector Garcia-Molina 3. Indeksy

64 n=4 (b) Scalenie z sąsiadem Usuń 50 10 40 100 40 10 20 30 40 50Oryginał: Hector Garcia-Molina 3. Indeksy

65 n=4 (c) Poprzerzucaj klucze Usuń 50 10 40 100 35 10 20 30 35 40 50Oryginał: Hector Garcia-Molina 3. Indeksy

66 n=4 (d) Scalenie nie-liści Usuń 37 25 25 10 20 30 40 40 30 25 26 1 3Nowy korzeń 10 20 30 40 40 30 25 26 1 3 10 14 20 22 30 37 40 45 Oryginał: Hector Garcia-Molina 3. Indeksy

67 Usunięcia z B+drzew w praktyceZwykle nie dokonuje się scalania Jest zbyt kosztowne i nie warto tego robić I tak trzeba co jakiś czas przebudować indeksy ze względu na błędy w SZBD Oryginał: Hector Garcia-Molina 3. Indeksy

68 B+drzewa a indeksy konwencjonalneNa podstawie [1] Held i Stonebraker “B-Trees Re-examined”, Communications of ACM, Feb. 1978 Oryginał: Hector Garcia-Molina 3. Indeksy

69 Wnioski z [1] W B+drzewach trudniej obsługiwać współbieżnośćB+drzewa zużywają więcej przestrzeni Założenia analizy blok = 512 bajtów klucz = wskaźnik = 4 bajty 4 rekordy w bloku Oryginał: Hector Garcia-Molina 3. Indeksy

70 1 blok indeksu statycznegodanych 127 kluczy (127+1)4 = 512 bajtów -> wskaźniki wyliczane (offsety) do 127 bloków k1 k2 k2 k3 k3 Oryginał: Hector Garcia-Molina 3. Indeksy

71 1 blok B+drzewa k1 k2 63 klucze ... k63 63x(4+4)+8 = 512 bajtówdanych 63 klucze 63x(4+4)+8 = 512 bajtów -> wskaźniki są konieczne do 63 bo B+drzewo nie jest ciągłe bloków k2 ... k2 k63 k3 - next Oryginał: Hector Garcia-Molina 3. Indeksy

72 Porównanie rozmiarów [1]Indeks statyczny B+drzewo liczba liczba bloków wysokość bloków wysokość 2 -> > 128 -> 16, > 16,130 -> 2,048, > 250, 250,048 -> 15,752, Oryginał: Hector Garcia-Molina 3. Indeksy

73 Statyczne indeksy lepszeWyniki analizy [1] W przypadku pliku 8000-blokowego po wstawieniach po wyszukiwaniach  Oszczedzamy tyle czasu, że starczy go na ręczną reorganizację Wniosek z [1] Statyczne indeksy lepsze Oryginał: Hector Garcia-Molina 3. Indeksy

74 DBA nie wie, kiedy reorganizować [2] M. Stonebraker, “Retrospective on a database system,” TODS, June 1980 Wniosek z [2] B+drzewa są lepsze! DBA nie wie, kiedy reorganizować DBA nie wie, jak bardzo zapełnić strony indeksu po reorganizacji Oryginał: Hector Garcia-Molina 3. Indeksy

75 Wnioski z [2] B+drzewa są lepsze Zarządzanie buforamiB+drzewo ma stałą wymaganą wielkość bufora (liczbę bloków) Indeks statyczny musi być może doczytać kilka stron nadmiarowych (co wymaga większej i zmiennej liczby niezbędnych buforów) Oryginał: Hector Garcia-Molina 3. Indeksy

76 Zarządzanie buforami Czy LRU to dobra strategia zarządzania buforami?Oczywiście nie! Korzeń musi być przyszpilony w pamięci... I być może nizsze poziomy też Czyli MRU! Oryginał: Hector Garcia-Molina 3. Indeksy

77 Najlepszy stopień B+drzewa?… n to liczba kluczy w węzle Oryginał: Hector Garcia-Molina 3. Indeksy

78 Przykładowe założenia(1) Czas potrzebny na odczyt węzła z dysku ( n) ms (2) Gdy węzeł jest w pamieci, korzystamy z wyszukiwania binarnego (a + b LOG2 n) ms Dla pewnych stałych a,b; Zakładamy, że a << 70 (3) Założmy, że B+drzewo jest zapełnione liczba węzłów do przejrzenia to LOGnN gdzie N = liczba rekordów Oryginał: Hector Garcia-Molina 3. Indeksy

79 Minimalizujemy funkcję: f(n) = czas poszukiwania rekordunopt n Oryginał: Hector Garcia-Molina 3. Indeksy

80  Znajdź nopt => pochodna f’(n) = 0nopt = kilkaset W praktyce koszt odczytu bloku nie zależy od n, bo węzeł = blok Ignorujemy koszt CPU Minimalizujemy więc LOGnN Czyli? Upychamy w bloku tyle kluczy, ile wlezie I tak wychodzi kilkaset Oryginał: Hector Garcia-Molina 3. Indeksy

81 A gdyby zwykłe Bdrzewo? [ bez + ]Unikamy duplikacji kluczy Wskaźniki do rekordów są też w węzłach wewnętrznych Oryginał: Hector Garcia-Molina 3. Indeksy

82 K1 W1 K2 W2 K3 W3 do rekordu do rekordu do rekordu do K1 z K2 z K3do kluczy do kluczy do kluczy do kluczy < K K1K3 K1 W1 K2 W2 K3 W3 Oryginał: Hector Garcia-Molina 3. Indeksy

83 Przykład Bdrzewa n=2 Fastryga jest teraz bezużyteczna! 65 125 25 4585 105 145 165 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150 160 170 180 Oryginał: Hector Garcia-Molina 3. Indeksy

84 Uwaga o wstawieniach Wstawiamy rekord z kluczem 25 Potem: 10 20 30 n=3liść 10 20 – 25 30 Potem: Oryginał: Hector Garcia-Molina 3. Indeksy

85 Statystyka Bdrzew MAX MIN Wsk. Wsk. Klu. Wsk. Wsk. Kluczewęz. rek. węz rek. Nie-liść Nie-korzeń n+1 n n (n+1)/2 (n+1)/2-1 (n+1)/2-1 Liść Nie-korzeń 1 n n (n+1)/2 (n+1)/2 Korzeń Nie-liść n+1 n n Liść 1 n n Oryginał: Hector Garcia-Molina 3. Indeksy

86 Wady i zalety  Bdrzewa pozwalają na szybsze wyszukiwanie niż B+drzewa  W Bdrzewach liście i nie-liście są różnych rozmiarów  W Bdrzewach usuwanie trudniejsze  B+drzewa lepsze! Oryginał: Hector Garcia-Molina 3. Indeksy

87 Ale... Jeśli bloki są stałego rozmiaru (a tak jest w przypadku wielu dysków): To wyszukiwanie w B+drzewach jest w istocie lepsze. Oryginał: Hector Garcia-Molina 3. Indeksy

88 Przykład Wskaźnik: 4 bajty Klucz 4 bajtyBlok 100 bajtów (dla prostoty) Pełne dwupoziomowe drzewo Oryginał: Hector Garcia-Molina 3. Indeksy

89 Korzeń ma 8 kluczy + 8 wskaźników na rekordy + 9 wskaźników na synów Bdrzewo: Korzeń ma 8 kluczy + 8 wskaźników na rekordy wskaźników na synów = 8x4 + 8x4 + 9x4 = 100 bajtów Każdy z 9 synów: 12 wsk. na rek. +12 kluczy = 12x(4+4) + 4 = 100 bajtów 2-poziomowe Bdrzewo ma maksymalnie 12x9 + 8 = 116 rekordów Oryginał: Hector Garcia-Molina 3. Indeksy

90 Korzeń ma 12 kluczy + 0 wskaźników na rekordy + 13 wskaźników na synów B+drzewo: Korzeń ma 12 kluczy + 0 wskaźników na rekordy + 13 wskaźników na synów = 12x4 + 0x4 + 13x4 = 100 bajtów Każdy z 13 synów: 12 wsk. na rek. +12 kluczy = 12x(4+4) + 4 = 100 bajtów 2-poziomowe B+drzewo ma maksymalnie 13x12 = 156 rekordów Oryginał: Hector Garcia-Molina 3. Indeksy

91 Zatem? B+ B Wniosek W przypadku bloków stałego rozmiaru,8 rekordów ooooooooooooo ooooooooo 156 rekordów rekordów Razem = 116 B+ B Wniosek W przypadku bloków stałego rozmiaru, B+drzewa są lepsze, bo są bardziej krzaczaste Oryginał: Hector Garcia-Molina 3. Indeksy