TI/Bazy danych

TI/ Co widać w Google?

Odpowiedź wyszukiwarki (np. google.pl) dociera do nas zwykle w kilka sekund, na pewno więc nie są w tym czasie przeszukiwane wszystkie komputery Internetu. Całe wyszukiwanie odbywa się na dyskach jednego systemu, na których znajduje się indeksowana baza danych o stronach WWW, udostępniana użytkownikom za pośrednictwem wyszukiwarki internetowej.

Indeks, czyli jak szybko szukać?

indeks w bibliotece

książki :-)

Jeśli w książce telefonicznej mamy np. [math]N=1024[/math] adresów posortowanych tylko według nazwisk, i szukamy znanego numeru telefonu, to w najgorszym razie musimy przejrzeć każdą pozycję, czyli wykonać [math]N=1024[/math] operacji porównania szukanego numeru z numerem przypisanym dla danego nazwiska.

Jeśli szukamy nazwiska, możemy użyć np. algorytmu przeszukiwania binarnego; wtedy złożoność jest rzędu [math]\log_2(N)[/math], czyli w najgorszym razie wykonujemy 10 porównań. Dla miliona wystarczy już tylko 20 porównań — przeszukiwanie działać będzie 50 tysięcy razy szybciej. Dla miliarda (1 000 000 000) — tylko 30 operacji, czyli kilkadziesiąt milionów razy szybciej.

Bazy danych

...to zbiory indeksowanych — albo indeksowalnych — informacji.

Co to jest indeks? Nic nowego, pojęcia znane z biblioteki. Zamiast układać książki w kolejności alfabetycznej według nazwisk autorów, nowe książki kładziemy po kolei na wolnych półkach i przypisujemy im kolejne numery (sygnatury). Za to w kolejności alfabetycznej układamy fiszki — małe karteczki, na których poza nawiskiem autora i tytułem jest jeszcze numer (sygnatura — czyli indeks). Gdy znajdziemy fiszkę interesującej książki odczytujemy sygnaturę i wiemy już dokładnie jak dotrzeć do książki — książka o sygnaturze 123456 będzie pomiędzy 123455 a 123457.

Gdyby nie było indeksu, a książki nie byłyby układane w kolejności alfabetycznej, aby znaleźć książkę o znanym tytule musielibyśmy przejrzeć po kolei wszystkie książki — a przynajmniej ich grzbiety. Dla biblioteki w której jest milion książek wymagałoby to spojrzenia na milion grzbietów. Milion w najgorszym razie, jeśli szukana książka byłaby na samym końcu — w obliczeniach najlepiej brać pod uwagę taki "najgorszy przypadek".

Dla książek — lub fiszek — uporządkowanych alfabetycznie, można to zrobić dużo szybciej. W ilu spojrzeniach (czyli porównaniach ze znanym wzorcem)? Policzmy: najpierw patrzymy na sygnaturę książki znajdującej się na środku. Jeśli jej sygnatura jest większa od szukanej, to szukana książka znajduje się na lewo. Jeśli mniejsza, to na prawo. W każdym przypadku do przeszukania pozostaje już tylko pół miliona sygnatur. Po sprawdzeniu środkowej z tego pół miliona pozostaje 250 000. W 20 porównaniach dochodzimy do końca. Łatwo sprawdzić, że wzór na ilość porównań potrzebny do znalezienia tym sposobem numeru na uporządkowanej liście będzie postaci [math]log_2 N[/math], gdzie [math]N[/math] jest długością przeszukiwanej listy.

Czyli zamiast miliona porównań mamy 20 — czyli czas wyszukiwania zmniejsza się ok. 50 tysięcy razy. Dla większych list (czyli większych zbiorów danych) zysk jest niewyobrażalnie większy — rośnie wykładniczo.

210 = 1024
220 = 1 048 576 > 106 (milion)
230 = 1 073 741 824 > 109 (miliard)
240 = 1 099 511 627 776 > 1012 (bilion)
240 = 1 1125 899 906 842 624 > 1015 (biliard)
250 = 1 152 921 504 606 846 976 > 1018 (trylion) 
2100 = 1 267 650 600 228 229 401 496 703 205 376 > 1030 (kwintylion)
2200 = 1 606 938 044 258 990 275 541 962 092 341 162 602 522 202 993 782 792 835 301 376 > 1060 (decylion)

liczba sekund od Wielkiego Wybuchu: ~ 1017
liczba protonów we Wszechświecie ~ 1080

Monopole wyszukiwarek

W ubiegłym wieku konkurowało ze sobą wiele wyszukiwarek. Obecnie google.com właściwie wyparł wszelką konkurencję. Pozycję tę uzyskał dzięki świetnej technologii przeszukiwania bazy danych oraz jej tworzenia i uaktualniania, czyli indeksowania Internetu. Możemy to uznać za wygodne uproszczenie ("nie muszę się zastanawiać, której wyszukiwarki użyć"), ale z drugiej strony na każdy powstający monopol powinniśmy patrzeć ostrożnie.

Coraz częściej słyszymy stwierdzenie "nie znalazłem tego w Internecie", co ma niemalże podawać w wątpliwość możliwość istnienia takiego "nieznajdowalnego" bytu (nazwy, nazwiska, pojęcia...). A z kolei "nie znalazłem w Internecie" w praktyce oznacza "google nie znalazł". Ale google tak naprawdę nie szuka w Internecie, tylko w swojej bazie danych! Więc jeśli zarządzające nią osoby zdecydują się usunąć zapisy związane z jakimś pojęciem czy osobą, skazują je na częściowy niebyt... jak w powieściach science fiction.

Ta uwaga nie powinna bynajmniej być odczytywana jako sugestia, że firma zarządzająca aktualnie serwisem google czy jakimkolwiek innym dopuszcza się takich praktyk. Ale warto być świadomym, że jest to technicznie możliwe.