Tekst źródłowy strony TI/Bazy danych


==[[%22Technologia_informacyjna%22|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ć?===


[[Plik:Gottingen-SUB-index.03.JPG|indeks w bibliotece|thumb|right]]
[[Plik:Bemowo_library_books.jpg|książki :-)|thumb|left]]


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 [[wikipedia:Przeszukiwanie_binarne|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ń &mdash; przeszukiwanie działać będzie 50 tysięcy razy szybciej. Dla miliarda (1 000 000 000) &mdash; tylko 30 operacji, czyli kilkadziesiąt milionów razy szybciej.


==Bazy danych==

...to zbiory indeksowanych &mdash; albo indeksowalnych &mdash; 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 &mdash; małe karteczki, na których poza nawiskiem autora i
tytułem jest jeszcze numer (sygnatura &mdash; czyli indeks). Gdy
znajdziemy fiszkę interesującej książki odczytujemy sygnaturę i wiemy
już dokładnie jak dotrzeć do książki &mdash; książka o sygnaturze
123456 będzie pomiędzy 123455 a 123457.

[[Grafika:LA2-katalogkort.jpg|thumb|300px|<figure id="fig:LA2-katalogkort" />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 &mdash; 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 &mdash; w obliczeniach najlepiej
brać pod uwagę taki "najgorszy przypadek".

Dla książek &mdash; lub fiszek &mdash; 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 &mdash; 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 &mdash; rośnie
wykładniczo.


 2<sup>10</sup>    = 1024


 2<sup>20</sup> = 1 048 576 > 10<sup>6</sup> (milion)


 2<sup>30</sup> = 1 073 741 824 > 10<sup>9</sup> (miliard)


 2<sup>40</sup> = 1 099 511 627 776 > 10<sup>12</sup> (bilion)


 2<sup>40</sup> = 1 1125 899 906 842 624 > 10<sup>15</sup> (biliard)


 2<sup>50</sup> = 1 152 921 504 606 846 976 > 10<sup>18</sup> (trylion) <!-- trylionów stron indeksuje google w 2018  -->


 2<sup>100</sup> = 1 267 650 600 228 229 401 496 703 205 376 > 10<sup>30</sup> (kwintylion)


 2<sup>200</sup> = 1 606 938 044 258 990 275 541 962 092 341 162 602 522 202 993 782 792 835 301 376 > 10<sup>60</sup> (decylion)



 liczba sekund od Wielkiego Wybuchu: ~ 10<sup>17</sup>


 liczba protonów we Wszechświecie ~ 10<sup>80</sup>



===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.

<!--Pouczającym doświadczeniem jest wyszukanie w polskim google [http://www.google.pl/search?q=Tiananmen Tiananmen] (fonetycznie zapisanej nazwy placu Niebiańskiego Spokoju) Tiananmen i porównanie wyników z tymi zwracanymi przez chińską wersję [http://www.google.cn/search?q=Tiananmen wyszukiwarki].-->
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.