Z Brain-wiki
Skocz do: nawigacja, szukaj

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. N=1024 adresów posortowanych tylko według nazwisk, i szukamy znanego numeru telefonu, to w najgorszym razie musimy przejrzeć każdą pozycję, czyli wykonać N=1024 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 \log_2(N), 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.

Karta z katalogu audycji Radia Szwedzkiego używanego do 2005 r.

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 log_2N, gdzie N 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.


2^{10}=1024

2^{20}=1 048 576 \approx 10^{6} (milion)

2^{30}=1 073 741 824 \approx 10^{9} (miliard)

2^{40}=1 099 511 627 776 \approx 10^{12} (bilion)

2^{40}=1 1125 899 906 842 624 \approx 10^{15} (biliard)

2^{50}=1 152 921 504 606 846 976 \approx 10^{18} (trylion) 30 trylionów stron indeksuje google w 2018

2^{100}=1267650600228229401496703205376 \approx 10^{30}

2^{200} = 160693 ... 782792835301376 \approx 10^{60}

2^{200} = 2037035 ... 381299763336706183397376 \approx 10^{90}

liczba protonów we Wszechświecie \approx 10^{80}

sekund od WIelkiego Wybuchu: \approx 10^{17}

Monopole wyszukiwarek

Kilkanaście lat temu konkurowało ze sobą co najmniej kilka 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.