Hledání v datech

Doc. Dr. Vladimír Homola, Ph.D.

Geo - data se vyznačují značným množstvím, klíč logického záznamu se může konstruovat z datových polí více souborů ap. Hledání v takových datech je kritickým momentem zpracování. Proto efektivita zpracování dat přímo závisí na efektivitě hledání v datech.

Hledáním rozumíme dodání takového záznamu ze souboru (souborů) dat, který splňuje dané kriterium. Tímto kriteriem může být jakýkoliv logický výraz, vyhodnotitelný pro každý záznam. Záznam, pro nějž po vyhodnocení odevzdá tento logický výraz hodnotu logické 1, dané kriterium splňuje.

Jako kriterium efektivity různých metod hledání se používá průměrný počet vyhodnocení kriteria, jehož splnění je vyžadováno. Toto vyhodnocení vždy pracuje s hodnotami polí záznamu, proto jedno vyhodnocení je přímo spojeno s jedním vyzdvižením dat záznamu (všech nebo jen některých; velmi často jsou rychlosti v obou případech stejné!). Protože vyzdvižení dat záznamu je spojeno s přístupem k mediu - a to je časově velmi náročná operace - potvrzuje to jen tvrzení o hledání v datech jako o kritickém místě procesu zpracování dat.

V dalším bude symbolem N označován počet všech záznamů, symbolem Zi počet kroků nutný pro vyhledání a vyhodnocení i-tého záznamu, symbolem Zp průměrný počet nutných vyhodnocení, Z (= Zp . N) počet všech vyhodnocení.

Sekvenční hledání

Při sekvenčním hledání se probírají záznamy postupně od začátku jeden za druhým tak dlouho, dokud není nalezen záznam vyhovující vyhledávacímu kriteriu.

Nechť pi je pravděpodobnost, že i-tý záznam bude nalezen v jednom kroku. Sekvenční hledání se používá tam, kde nejsou známy bližší podrobnosti o způsobu uložení; proto musíme předpokládat rovnoměrné rozložení, kde ovšem je pi = 1/N. Je tedy

Zp = zp1 + ... + zN.pN
Zp = 1/N . (z1 + ... + zN)

Při sekvenčním hledání je zi = i, tedy

Zp = 1/N . (1 + ... + N) = (N + 1)/2

Při sekvenčním hledání je tedy k nalezení požadovaného záznamu nutno prohlédnout průměrně polovinu souboru.

Sériové hledání

Sériové hledání se uplatňuje v souborech se sériovým způsobem uložení. Záznamy jsou tedy řazeny v uspořádané posloupnosti (sérii) hodnot klíčů. V metodách sériového hledání je vždy vyhledávacím kriteriem hodnota klíče, podle kterého je soubor řazen.

Sériové hledání s pravidelnými skoky

Tato metoda (myšleně) rozděluje soubor na bloky o shodném počtu záznamů. Nejprve je (sekvenčně) nalezen blok, ve kterém se záznam nachází, a poté (sekvenčně) hledaný záznam.

Nechť je tedy počet bloků m, počet záznamů v každém bloku s. Je tedy N = m . s. Nechť j označuje číslo bloku, j je z <1,m>; dále označme h číslo záznamu v bloku, h je z <1,s>. Pro dosažení j-tého bloku je zapotřebí j kroků, pro dosažení h-tého záznamu je zapotřebí 0 až s-1 kroků (nula proto, že hledaný záznam může být prvním v bloku a už tedy netřeba hledat dále; s-1 proto, že s-tý už je první v dalším bloku). Je pak

Z = s . (1 + ... + m) + m . (1 + ... + s-1)
Z = s . m.(m+1)/2 + m . (s-1).s/2

Protože je s = N/m, je

Z = N . (N + m2) / (m)

a tedy

Zp = Z/N = (N + m2) / (m) = f (m)

Pro kontrolu: je zřejmé, že uvedená metoda je pro jednozáznamový blok totožná se shora popsaným sekvenčním hledáním: prohledávají se postupně všechny záznamy počínaje prvním, a to po jednom. Je-li m = 1, je

Zp = (N + 12) / (1) = (N + 1) / 2

což je shoda s výsledkem odvozeným pro sekvenční hledání.

Dále pro všechna m>1 je

(N + m2) / (m) < (N + 1) / 2

z čehož plyne, že průměrný počet kroků při sériovém hledání s pravidelnými kroky je vždy lepší než sekvenční hledání. Už např. pro m=2 je průměrný počet kroků zhruba poloviční.

Protože průměrný počet kroků je funkcí m, lze zjistit, pro jaké m0 má tato funkce minimum (tj. pro jaké velikosti bloků je hledání optimální). Musí být

df / dm = 0

a protože

Zp = f (m) = (N + m2) / (m)

je po provedení derivace a zjištění m0

m0 = Ö(N)

a tedy po dosazení rovněž

Zp = Ö(N)

Např. pro soubor o 10 000 záznamech je optimální délka bloku 100 a průměrný počet kroků pro nalezení hledaného záznamu rovněž 100. Pro srovnání: při sekvenčním hledání to je 5 000!

Sériové hledání půlením intervalu

Metoda je někdy označována také jako binární hledání, je logicky totožná se stejně označovanou metodou numerické matematiky. Protože jde o sériové hledání, lze aplikovat pouze na soubory se sériovým uložením, tedy seřazené podle hodnot klíče. Metoda je popsána pro vzestupné řazení, pro sestupné postačí zaměnit relace.

Princip metody je následující:

Existuje záznam, který rozděluje soubor na dvě, co do počtu prvků (až na jeden) stejné části. Všechny záznamy před tímto záznamem mají hodnoty klíče menší nebo rovnu, za tímto záznamem větší nebo rovnu. Vybere se tedy tento "prostřední" záznam a jeho klíč se porovná s hledaným klíčem. Jsou-li totožné, je záznam nalezen. Je-li prostřední klíč větší než hledaný, hledá se stejným způsobem v první polovině souboru. Je-li prostřední klíč menší než hledaný, hledá se stejným způsobem ve druhé polovině souboru.

Metoda končí ve dvou případech: hledaný záznam je nalezen, nebo není co půlit - v tom případě hledaný klíč nemá žádný záznam souboru.

Pro odvození průměrného počtu kroků uvažme toto: existuje jediný záznam dosažitelný právě jedním krokem (prostřední); existují dva záznamy, dosažitelné právě dvěma kroky (prostřední v dolní a hodní polovině souboru); čtyři dosažitelné třemi kroky ... obecně 2(j-1) dosažitelné j kroky.

Počet kroků, kterými je každý prvek dosažitelný, determinuje rozklad množiny záznamů na třídy. Do třídy j patří 2(j-1) záznamů. Součet kroků pro každou třídu je tedy

Zj = j . 2(j-1)

Uvažujme nejprve, že ideální počet záznamů souboru je

N = 2k - 1

(tj. pro každé půlení existuje přesně prostřední prvek) a označme

a = log2 (N-1)

Pak pro celkový počet kroků je (matematické odvození je vynecháno)

Z = 2a . (a-1) + 1

a tedy - protože Zp = Z/N -

Zp = (N+1)/N . log2 (N+1) - 1

tj. přibližně

Zp = log2 (N)

Tento vztah byl odvozen pro ideální binární hledání (N = 2k - 1), což je v praxi málokdy splněno. Porušení této podmínky však - zvláště pro větší počet záznamů - nevede k podstatnému zhoršení rychlosti vyhledávání.

Tato metoda je tedy ze všech zatím uvedených nejrychlejší.

Přímý přístup k datům

Pod přímým přístupem k datům se rozumí přímé čtení záznamu ze známé adresy. V těchto metodách je tedy Zp=1, každý požadovaný záznam se přečte hned napoprvé.

Metody přímého přístupu k datům evidentně vyžadují znalost adresy pro každý záznam. To neznamená, že v každém okamžiku jsou známy adresy všech záznamů najednou. Znamená to, že v okamžiku potřeby daného záznamu existuje možnost adresu zjistit.

U těchto metod se obdobně jako u metod sériového hledání předpokládá existence klíče a vzestupné nebo sestupné uspořádání jeho hodnot.

Přímé adresování

Při této metodě je adresou přímo klíč nebo jeho lineární transformace.

Příklad: Nechť každý z 13 vrtů v terénu má číselný kód od 1 do 13 (vrty jsou tedy "očíslovány"). Nechť délka záznamu obsahující údaje o každém vrtu je 67. Klíčem vrtu je jeho číslo -v- a z něj lze odvodit adresu záznamu výrazem A = (v-1) * 67.

Metoda přímého adresování je vhodná v případě, že

Nepřímé adresování

Nejčastěji však data v souborech nesplňují ani přibližně požadavky odůvodňující přímé adresování. Je to např. tehdy, když

V uvedených a podobných případech je nutno mít k disposici funkci, která transformuje hodnotu klíče na adresu. Adresa není tedy určena přímo, ale zprostředkovaně klíčem; proto se tyto metody nazývají metody nepřímého adresování, a protože používají (již při výkladu metod zápisu zmíněnou) Hash - funkci, nazývají se také Hash - metodami.

Zpravidla není možno sestrojit funkci A = A (k) tak, aby to bylo prosté zobrazení (celé) množiny klíčů na rovnoměrně rozložené adresy v množině použitelných adres. Na druhé straně by funkce A neměla být (z časových důvodů při jejím vyhodnocování) příliš složitá. Proto se užívají takové funkce, které některé adresy ponechávají neobsazené a jiné adresy jsou obrazem většího počtu klíčů.

Nechť funkce A (k) zobrazuje množinu klíčů na M různých adres. Pro uložení celého je však zapotřebí N různých adres. Paměť může být tím rovnoměrněji rozdělena, čím větší je poměr M/N. Ve skutečnosti se však pro uložení všech N záznamů nevyužije všech M adres. Některé zůstávají nevyužité, některé jsou použity vícekrát. Je-li počet adres použitých alespoň jednou označen L, pak se hodnota l = L/M označuje jako koeficient zaplnění (loading factor).

Použijme termín skupina záznamů pro ty záznamy, jejichž klíč je transformován na stejnou adresu. Rozměr skupiny záznamů je počet záznamů skupiny (ideální je samozřejmě rozměr všech skupin rovný jedné). Zvolí-li se při vytváření souboru velký rozměr skupiny, zmenší se pravděpodobnost nutnosti zápisu do zóny přeplnění (a tím zkrátí čas hledání v této oblasti), ale zvětší se čas při hledání ve skupině. Zvolí-li se naopak při vytváření souboru malý rozměr skupiny, zvýší se pravděpodobnost nutnosti zápisu do zóny přeplnění a tím se zvětší doba hledání v této zóně.

Je zřejmé, že základem optimální volby rozměru skupiny záznamů je kvalifikovaný odhad množiny skutečných klíčů, které budou do souboru skutečně zapisovány. Protože tento odhad se liší od aplikace k aplikaci, bývá u obecných systémů rozměr skupiny i velikost oblasti přeplnění volitelným parametrem souboru.

Funkcí A = A (k) existuje celá řada a z hlediska zaměření tohoto článku nemá smysl je zde uvádět. Účinnost vyhledávacích metod na nich založených ovlivňují následující parametry:

Hledání v datech s indexy

Tyto metody hledání mohou být aplikovány pouze na soubory dat, ke kterým byly vytvořeny indexové tabulky (viz odstavec o metodách uložení s indexy). Protože indexové tabulky jsou vytvářeny na základě hodnot klíčů, je možno hledat záznam pouze podle kriteria, kterým je hodnota klíče.

Poznámka: Protože vlastní data jsou uložena sekvenčně, je principielně možno ke každému stávajícímu sekvenčnímu souboru vybudovat indexovou tabulku založenou na nějakém klíči, popř. vybudovat více indexových tabulek s různými přístupovými klíči postupně v čase.

Při této metodě se hledání ve vlastním souboru dat převádí na hledání dané hodnoty klíče v indexové tabulce. Po nalezení záznamu indexové tabulky je z pole adresy získána adresa datového záznamu v souboru dat, a tento záznam se pak přímo získá jediným čtením.

Pro hodnocení metod hledání v datech s indexy platí vše, co bylo uvedeno dříve, ovšem aplikováno na soubor indexů. Organizace uložení v souboru indexů tedy určuje efektivitu používání souborů s indexy. Protože z dosud hodnocených metod hledání je nejméně efektivní sekvenční metoda, téměř nikdy se nepoužívá ani sekvenční organizace uložení, ani sekvenční hledání.

Velmi často se pro indexová tabulky používá uložení s odkazy. Záznam pak má 6 polí: čtyři pole s odkazy (na předchůdce, následovníka, a na levého a pravého souseda), jedno pole pro hodnotu klíče a jedno pro hodnotu adresy záznamu. Indexová tabulka pak má tvar stromu (z teorie grafů). Každý záznam je pak jedním uzlem v tomto grafu, hrany grafu jsou obrazem odkazů. Výhodou je možnost ukládat v každém uzlu ne kompletní hodnoty klíče, ale jen část hodnoty klíče náležející dané úrovni uzlu v grafu.

Poznámka: Právě takovým způsobem jsou organizovány indexové soubory v relačním databázovém systému Microsoft Fox, jednom z nejvýkonnějších databázových systémů v prostředí počítačů třídy IBM/PC.

 

Rev: 6 / 2005