Kaixo, Habr! Artikuluaren itzulpena aurkezten dizuet
"Nola funtzionatzen du datu-base erlazional batek".

Erlazio datu-baseei dagokienez, ezin dut ezer falta dela pentsatu. Nonahi erabiltzen dira. Hainbat datu-base daude eskuragarri, SQLite txiki eta erabilgarritik Teradata indartsuraino. Baina datu-baseak nola funtzionatzen duen azaltzen duten artikulu gutxi batzuk daude. Zure burua bilatu dezakezu "nola dago erlazionatutako datu-basearen lana" erabiliz, emaitza gutxi dauden ikusteko. Gainera, artikulu hauek laburrak dira. Azken teknologia berrien bila bazabiltza (BigData, NoSQL edo JavaScript), nola funtzionatzen duten azaltzen duten artikulu sakonagoak aurkituko dituzu.

Erlazio datu-baseak zaharregiak eta aspertuegiak al dira unibertsitateko ikastaro, ikerketa-lan eta liburuetatik kanpo azaltzeko?

Garatzaile gisa, gorroto dut ulertzen ez dudan zerbait erabiltzea. Eta datu-baseak 40 urte baino gehiago erabiltzen badira, arrazoiren bat egon behar da. Urteetan zehar, ehunka ordu eman ditut egunero erabiltzen ditudan kutxa beltz bitxi hauek benetan ulertzeko. Datu-base erlazionalak oso interesgarria delako kontzeptu erabilgarri eta berrerabilgarrietan oinarrituta. Datu-base bat ulertzea interesatzen bazaizu, baina gai zabal honetan sakontzeko astirik edo gogorik izan ez baduzu, artikulu honekin gozatu beharko zenuke.

Artikulu honen izenburua esplizitua bada ere, artikulu honen helburua ez da datu-basea nola erabili ulertzea. Horregatik, dagoeneko jakin beharko zenuke konexio-eskaera sinple bat eta oinarrizko kontsultak idazten GURUZKOA; bestela agian ez duzu artikulu hau ulertu. Hori da jakin behar duzun gauza bakarra, gainerakoak azalduko ditut.

Informatikaren oinarri batzuekin hasiko naiz, hala nola, algoritmoen denbora-konplexutasuna (BigO). Badakit batzuek gorroto duzuela kontzeptu hau, baina hori gabe ezin izango dituzue datu-basearen barruko korapilatsuak ulertu. Gai handia denez, zentratuko naiz garrantzitsua iruditzen zaidana: datu-baseak nola prozesatzen duen SQL kontsulta. Besterik ez dut aurkeztuko datu-basearen oinarrizko kontzeptuakberaz, artikuluaren amaieran kaputxa azpian gertatzen denaren ideia bat izan dezazun.

Algoritmo eta datu-egitura asko biltzen dituen artikulu luze eta teknikoa denez, hartu denbora irakurtzeko. Kontzeptu batzuk ulertzeko zailak izan daitezke; saltatu ditzakezu eta oraindik ideia orokorra lortu.

Zuen artean jakintsuenentzat, artikulu hau 3 zatitan banatuta dago:

• Behe-mailako eta goi-mailako datu-basearen osagaien ikuspegi orokorra
• Kontsultak optimizatzeko prozesuaren ikuspegi orokorra
• Transakzioen eta Buffer Pool kudeaketaren ikuspegi orokorra

Itzuli Oinarrietara

Duela urte batzuk (galaxia urrun, urrun...), garatzaileek zehatz-mehatz jakin behar zuten kodetzen ari ziren eragiketa kopurua. Beren algoritmoak eta datu-egiturak bihotzez ezagutzen zituzten, ezin zutelako beren ordenagailu geldoen CPU eta memoria alferrik galdu.

Zati honetan, datu-basea ulertzeko ezinbestekoak diren kontzeptu horietako batzuk gogoraraziko ditut. Kontzeptua ere aurkeztuko dut datu-basearen indizea.

O(1) vs O(n2)

Gaur egun, garatzaile askori berdin zaie algoritmoen denbora-konplexutasunaz... eta arrazoi dute!

Baina datu askorekin ari zarenean (ez naiz milaka hitz egiten) edo milisegundotan borrokan ari zarenean, funtsezkoa bihurtzen da kontzeptu hau ulertzea. Eta imajina dezakezuenez, datu-baseek bi egoerei aurre egin behar diete! Ez dizut behar baino denbora gehiago igaroko kontua zabaltzeko. Horrek kostuetan oinarritutako optimizazioaren kontzeptua ulertzen lagunduko digu geroago (kostua oinarritutako optimizazioa).

kontzeptua

Algoritmoaren denbora konplexutasuna datu kopuru jakin baterako algoritmo bat exekutatzeko zenbat denbora beharko duen ikusteko erabiltzen da. Konplexutasun hori deskribatzeko, O handia idazkera matematikoa erabiltzen dugu. Notazio hau algoritmo batek sarrera kopuru jakin baterako zenbat eragiketa behar dituen deskribatzen duen funtzio batekin erabiltzen da.

Esate baterako, "algoritmo honek konplexutasuna O(funtzio_zenbait()) du" esaten dudanean, algoritmoak datu kopuru jakin bat prozesatzeko zenbait_funtzio(a_certain_amount_of_data) eragiketak behar dituela esan nahi du.

Kasu honetan, Ez da datu kopurua axola duena**, bestela ** nola handitzen den eragiketa kopurua datu-bolumena handitzean. Denboraren konplexutasunak ez du eragiketa kopuru zehatza ematen, baina exekuzio denbora kalkulatzeko modu ona da.

Grafiko honetan eragiketa kopurua ikus dezakezu algoritmoen denbora-konplexutasun mota desberdinetarako sarrera-datu kopuruaren aldean. Eskala logaritmiko bat erabili dut haiek bistaratzeko. Beste era batera esanda, datu kopurua azkar handitzen da 1 milioitik 1era. Hori ikus dezakegu:

• O(1) edo konplexutasun konstantea konstante geratzen da (bestela ez litzateke konplexutasun konstantea deituko).
• O(saioa hasi(n)) baxua izaten jarraitzen du milaka milioi daturekin ere.
• Zailtasunik txarrena - O(n2), non eragiketa kopurua azkar hazten den.
• Beste bi konplikazioak bezain azkar handitzen dira.

Примеры

Datu kopuru txikiarekin, O(1) eta O(n2) arteko aldea arbuiagarria da. Adibidez, demagun 2000 elementu prozesatu behar dituen algoritmo bat duzula.

• O(1) algoritmoak eragiketa 1 kostatuko dizu
• O(log(n)) algoritmoak 7 eragiketa balioko dizu
• O(n) algoritmoak 2 eragiketa balioko dizu
• O(n*log(n)) algoritmoak 14 eragiketa balioko dizu
• O(n2) algoritmoak 4 eragiketa balioko dizu

O(1) eta O(n2) arteko aldea handia dirudi (4 milioi eragiketa) baina gehienez 2 ms galduko dituzu, begiak keinu egiteko denbora besterik ez. Izan ere, prozesadore modernoek prozesatu dezakete ehunka milioi eragiketa segundoko. Horregatik, errendimendua eta optimizazioa ez dira arazo bat IT proiektu askotan.

Esan bezala, oraindik ere garrantzitsua da kontzeptu hau ezagutzea datu kopuru handiekin lan egitean. Oraingoan algoritmoak 1 elementu prozesatu behar baditu (ez da horrenbeste datu-base baterako):

• O(1) algoritmoak eragiketa 1 kostatuko dizu
• O(log(n)) algoritmoak 14 eragiketa balioko dizu
• O(n) algoritmoak 1 eragiketa balioko dizu
• O(n*log(n)) algoritmoak 14 eragiketa balioko dizu
• O(n2) algoritmoak 1 eragiketa balioko dizu

Ez dut matematikarik egin, baina esango nuke O(n2) algoritmoarekin kafe bat edateko astia duzula (bi ere!). Datu-bolumenari beste 0 bat gehitzen badiozu, siesta egiteko denbora izango duzu.

Goazen sakonago

Zure informaziorako:

• Hash-taularen bilaketa on batek elementu bat aurkitzen du O(1).
• Ondo orekatuta dagoen zuhaitz bat bilatuz gero, emaitzak O(log(n)) sortzen dira.
• Array batean bilaketak emaitzak O(n)-n sortzen ditu.
• Ordenatzeko algoritmo onenak O(n*log(n)) konplexutasuna dute.
• Ordenatzeko algoritmo txar batek O(n2) konplexutasuna du.

Oharra: hurrengo zatietan algoritmo eta datu-egitura hauek ikusiko ditugu.

Hainbat algoritmo-denboraren konplexutasun mota daude:

• batez besteko kasua
• kasurik onena
• eta kasurik txarrena

Denboraren konplexutasuna izaten da kasurik txarrena.

Algoritmoaren denbora-konplexutasunari buruz bakarrik ari nintzen, baina konplexutasunari ere aplikatzen zaio:

• algoritmoaren memoria-kontsumoa
• Disko I/O kontsumo-algoritmoa

Jakina, n2 baino konplikazio okerragoak daude, adibidez:

• n4: hau izugarria da! Aipatutako algoritmo batzuek konplexutasun hori dute.
• 3n: hau are okerragoa da! Artikulu honen erdian ikusiko dugun algoritmoetako batek konplexutasun hori du (eta, egia esan, datu-base askotan erabiltzen da).
• n faktoriala: ez duzu inoiz lortuko zure emaitzak datu kopuru txikiarekin ere.
• nn: Konplexutasun honekin topo egiten baduzu, zure buruari galdetu beharko zenioke ea hau den benetan zure jarduera-eremua...

Oharra: ez dizut eman O handiaren izendapenaren benetako definizioa, ideia bat besterik ez. Artikulu hau irakur dezakezu hemen Wikipedia definizio errealerako (asintotikorako).

MergeOrden

Zer egiten duzu bilduma bat ordenatu behar duzunean? Zer? Sort() funtzioari deitzen diozu... Ados, erantzun ona... Baina datu-base baterako, sort() funtzio honek nola funtzionatzen duen ulertu behar duzu.

Hainbat ordenatzeko algoritmo on daude, beraz, garrantzitsuenetan zentratuko naiz: batu ordenatu. Agian ez duzu ulertzen zergatik den erabilgarria datuak ordenatzeko momentu honetan, baina kontsultaren optimizazio zatia egin beharko zenuke. Gainera, merge sort ulertzeak deitutako datu-baseen batzeko eragiketa komunean ulertzen lagunduko digu gero batzeko batu (fusio elkartea).

Batu

Algoritmo erabilgarri asko bezala, merge sort trikimailu batean oinarritzen da: N/2 tamainako 2 ordenatutako array konbinatzeak N elementu ordenatutako array batean N eragiketa baino ez ditu kostatzen. Eragiketa honi batzea deitzen zaio.

Ikus dezagun zer esan nahi duen honek adibide sinple batekin:

Irudi honek erakusten du ordenatutako azken 8 elementuko matrizea eraikitzeko, behin bakarrik errepikatu behar duzula 2 4 elementuko arrayetan. Bi 4 elementuko matrizeak dagoeneko ordenatuta daudenez:

• 1) uneko bi elementuak bi matrizetan konparatzen dituzu (hasieran korrontea = lehena)
• 2) Ondoren, hartu txikiena 8 elementuen array batean jartzeko
• 3) eta mugitu elementu txikiena hartu duzun matrizeko hurrengo elementura
• eta errepikatu 1,2,3 arrayetako baten azken elementura iritsi arte.
• Ondoren, beste arrayaren gainerako elementuak hartzen dituzu 8 elementuen array batean jartzeko.

Honek funtzionatzen du 4 elementuko array biak ordenatuta daudelako eta, beraz, ez duzulako matrize horietan "atzera itzuli" beharrik.

Orain trikimailua ulertzen dugunean, hona hemen bateratzeko nire pseudokodea:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

Merge sort arazo bat arazo txikiagoetan zatitzen du eta, ondoren, problema txikienen emaitzak aurkitzen ditu jatorrizko problemaren emaitza lortzeko (oharra: algoritmo mota honi zatitu eta konkistatu deitzen zaio). Algoritmo hau ulertzen ez baduzu, ez kezkatu; Ikusi nuenean ez nuen ulertu. Lagun zaitzakete, algoritmo hau bi faseko algoritmo gisa ikusten dut:

• Zatiketa fasea, non matrizea matrize txikiagoetan banatzen den
• Sailkapen-fasea matrize txikiak konbinatzen dira (batasuna erabiliz) matrize handiagoa osatzeko.

Zatiketa fasea

Zatiketa-etapan, array-a array unitarioetan banatzen da 3 urratsetan. Urrats-kopuru formala log(N) da (N=8 geroztik, log(N) = 3).

Nola dakit hori?

Jenioa naiz! Hitz batean - matematika. Ideia da urrats bakoitzak jatorrizko arrayaren tamaina 2z banatzen duela. Urrats kopurua jatorrizko array bitan zati dezakezun kopurua da. Hau da logaritmo baten definizio zehatza (2. oinarria).

Sailkatzeko fasea

Ordenatzeko fasean, matrize unitarioekin (elementu bakarrean) hasten zara. Urrats bakoitzean bateratze-eragiketa bat baino gehiago aplikatzen dituzu eta kostu osoa N = 8 eragiketa da:

• Lehenengo etapan 4 batuketa dituzu, bakoitzak 2 eragiketa kostatzen dutenak
• Bigarren urratsean 2 eragiketa balio duten 4 batuketa dituzu
• Hirugarren urratsean 1 eragiketa kostatzen diren bateratze bat duzu

Log(N) urratsak daudenez, kostu osoa N * log(N) eragiketak.

Fusion sortaren abantailak

Zergatik da hain indartsua algoritmo hau?

Zeren:

• Memoria-aztarna murrizteko alda dezakezu, matrize berriak sortzeko, baina sarrerako array zuzenean aldatzeko.

Oharra: algoritmo mota honi deitzen zaio in-leku (memoria gehigarririk gabe ordenatzea).

• Diskoko espazioa eta memoria-kopuru txiki bat aldi berean erabiltzeko alda dezakezu diskoko I/O-ko gastu handirik sortu gabe. Ideia da une honetan prozesatzen ari diren zatiak soilik kargatzea memorian. Hau garrantzitsua da gigabyte anitzeko taula bat 100 megabyte-ko memoria-buffer batekin bakarrik ordenatu behar duzunean.

Oharra: algoritmo mota honi deitzen zaio kanpoko sailkapena.

• Hainbat prozesu/hariak/zerbitzarietan exekutatzeko alda dezakezu.

Adibidez, bateratze-ordena banatua osagai nagusietako bat da Hadoop (big datan egitura bat dena).

• Algoritmo honek beruna urre bihur dezake (benetan!).

Ordenatzeko algoritmo hau datu-base gehienetan (guztietan ez bada) erabiltzen da, baina ez da bakarra. Gehiago jakin nahi baduzu, hau irakur dezakezu ikerketa lana, datu-baseen ordenatzeko algoritmo arrunten alde onak eta txarrak aztertzen dituena.

Array, Zuhaitz eta Hash Taula

Denboraren konplexutasunaren eta ordenazioaren ideia ulertzen dugunean, 3 datu-egiturari buruz esan beharko nizuke. Hau garrantzitsua da haiek direlako datu-base modernoen oinarria dira. Kontzeptua ere aurkeztuko dut datu-basearen indizea.

array

Bi dimentsioko array bat datu-egitura sinpleena da. Taula bat array gisa har daiteke. Adibidez:

2 dimentsioko matrize hau errenkadak eta zutabeak dituen taula bat da:

• Lerro bakoitzak entitate bat adierazten du
• Zutabeek entitatea deskribatzen duten propietateak gordetzen dituzte.
• Zutabe bakoitzak mota jakin bateko datuak gordetzen ditu (zenbaki osoa, katea, data...).

Datuak gordetzeko eta bistaratzeko komenigarria da, baina, balio zehatz bat aurkitu behar duzunean, hori ez da egokia.

Adibidez, Erresuma Batuan lan egiten duten mutil guztiak aurkitu nahi badituzu, errenkada bakoitza begiratu beharko zenuke Erresuma Batukoa den ala ez zehazteko. N transakzio kostatuko zaizuNon N - lerro kopurua, hori ez da txarra, baina bide azkarragorik egon al daiteke? Orain zuhaitzak ezagutzeko garaia heldu zaigu.

Oharra: datu-base moderno gehienek matrize hedatuak eskaintzen dituzte taulak modu eraginkorrean gordetzeko: heap-organizedtables eta index-organizedtables. Baina horrek ez du aldatzen zutabe talde batean baldintza zehatz bat azkar aurkitzeko arazoa.

Datu-basearen zuhaitza eta indizea

Bilaketa-zuhaitz bitarra propietate berezi bat duen zuhaitz bitar bat da, nodo bakoitzean gakoak izan behar du:

• ezkerreko azpizuhaitzean gordetako gako guztiak baino handiagoa
• eskuineko azpizuhaitzean gordetako gako guztiak baino gutxiago

Ikus dezagun zer esan nahi duen honek bisualki

Idea

Zuhaitz honek N = 15 elementu ditu. Demagun 208 bila nabilela:

• 136 gakoa duen errotik hasten naiz. 136<208 geroztik, 136 nodoaren eskuineko azpizuhaira begiratzen dut.
• 398>208, beraz, 398 nodoaren ezkerreko azpizuhaitza ikusten ari naiz
• 250>208, beraz, 250 nodoaren ezkerreko azpizuhaitza ikusten ari naiz
• 200<208, beraz, 200 nodoaren eskuineko azpizuhaitza ikusten ari naiz. Baina 200k ez du eskuineko azpizuhaitzik, balioa ez da existitzen (existitzen bada, eskuineko azpizuhaiztian egongo baita 200).

Orain demagun 40 bila nabilela

• 136 gakoa duen errotik hasten naiz. 136 > 40 denez, 136 nodoaren ezkerreko azpizuhaitza begiratzen dut.
• 80 > 40, beraz, 80 nodoaren ezkerreko azpizuhaitza ikusten ari naiz
• 40= 40, nodoa existitzen da. Nodoaren barruan dagoen errenkada IDa berreskuratzen dut (argazkian agertzen ez dena) eta taulan bilatzen dut emandako errenkada IDa.
• Errenkada IDa ezagutzeak datuak taulan non dauden zehatz-mehatz jakin dezaket, berehala berreskuratu ahal izateko.

Azkenean, bi bilaketak zuhaitz barruko maila kopurua kostatuko zait. Batu-ordenari buruzko atala arretaz irakurtzen baduzu, log(N) mailak daudela ikusi beharko zenuke. Geratzen da, bilaketa-kostuen erregistroa (N), ez dago gaizki!

Itzuli gaitezen gure arazora

Baina hau oso abstraktua da, itzul gaitezen gure arazora. Zenbaki oso soil baten ordez, imajinatu aurreko taulako norbaiten herrialdea adierazten duen kate bat. Demagun taulako "herrialdea" eremua (3. zutabea) duen zuhaitz bat duzula:

• Erresuma Batuan nork lan egiten duen jakin nahi baduzu
• zuhaitzari begiratzen diozu Britainia Handia adierazten duen nodoa lortzeko
• "UKnode" barruan Erresuma Batuko langileen erregistroen kokapena aurkituko duzu.

Bilaketa honek log(N) eragiketak kostatuko ditu N eragiketen ordez matrizea zuzenean erabiltzen baduzu. Aurkeztu berri duzuna zen datu-basearen indizea.

Indize-zuhaitz bat eraiki dezakezu edozein eremu taldetarako (katea, zenbakia, 2 lerro, zenbakia eta katea, data...) baldin eta gakoak konparatzeko funtzio bat baduzu (hau da, eremu-taldeak), ezarri ahal izateko. ordena giltzen artean (hau da datu-baseko oinarrizko edozein motaren kasuan).

B+TreeIndex

Zuhaitz honek balio zehatz bat lortzeko ondo funtzionatzen duen arren, behar duzunean arazo HANDI bat dago bi balioen artean hainbat elementu lortu. Honek O(N) kostua izango du, zuhaitzeko nodo bakoitza begiratu eta bi balio horien artean dagoen egiaztatu beharko duzulako (adibidez, zuhaitzaren zeharkatze ordenatu batekin). Gainera, eragiketa hau ez da diskoko I/O errespetatzen, zuhaitz osoa irakurri behar baituzu. Eraginkortasunez exekutatzeko modu bat aurkitu behar dugu barruti eskaera. Arazo hau konpontzeko, datu-base modernoek B+Tree izeneko aurreko zuhaitzaren bertsio aldatua erabiltzen dute. B+Tree zuhaitz batean:

• nodo baxuenak bakarrik (hostoak) informazioa gordetzea (errenkaden kokapena erlazionatutako taulan)
• gainerako nodoak hemen daude bideratzeko nodo zuzenera bilaketan zehar.

Ikus dezakezunez, hemen nodo gehiago daude (bi aldiz). Izan ere, nodo osagarriak dituzu, "erabaki nodoak", nodo zuzena aurkitzen lagunduko dizutena (errenkaden kokapena erlazionatutako taulan gordetzen duena). Baina bilaketaren konplexutasuna O(log(N)) da oraindik (maila bat gehiago dago). Alde handia hori da beheko mailan dauden nodoak haien ondorengoei lotuta daude.

B+Tree honekin, 40 eta 100 arteko balioak bilatzen badituzu:

• Besterik gabe, 40 (edo 40 ondoko baliorik hurbilena 40 existitzen ez bada) bilatu behar duzu aurreko zuhaitzarekin egin zenuen bezala.
• Ondoren, bildu 40 oinordeko oinordeko zuzeneko loturak erabiliz 100era iritsi arte.

Demagun M ondorengoak aurkitzen dituzula eta zuhaitzak N nodo dituela. Nodo zehatz bat aurkitzeak log(N) kostatzen du aurreko zuhaitza bezala. Baina nodo hau lortzen duzunean, M oinordekoak lortuko dituzu M eragiketetan haien ondorengoen erreferentziak dituztenak. Bilaketa honek M+log(N) baino ez du balio aurreko zuhaitzeko N eragiketekin alderatuta eragiketak. Gainera, ez duzu zuhaitz osoa irakurri beharrik (M+log(N) nodoak bakarrik), eta horrek diskoaren erabilera gutxiago esan nahi du. M txikia bada (adibidez 200 errenkada) eta N handia (1 errenkada), alde HANDIA egongo da.

Baina hemen arazo berriak daude (berriz!). Datu-basean errenkada bat gehitzen edo ezabatzen baduzu (eta, beraz, lotutako B+Tree indizean):

• B+Tree baten barruan dauden nodoen arteko ordena mantendu behar duzu, bestela ezin izango dituzu sailkatu gabeko zuhaitz baten barruan nodoak aurkitu.
• ahalik eta maila kopuru minimoa mantendu behar duzu B+Tree-n, bestela O(log(N)) denboraren konplexutasuna O(N) bihurtzen da.

Beste era batera esanda, B+Tree-k autoordenatua eta orekatua izan behar du. Zorionez, hau posible da ezabatze eta txertatzeko eragiketa adimendunekin. Baina horrek kostua du: B+ zuhaitz batean sartzeak eta ezabatzeak O(log(N)) balio du. Horregatik entzun duzue batzuk indize gehiegi erabiltzea ez da ideia ona. Benetan, taula bateko errenkada bat txertatzea/eguneratzea/ezabatzea azkar moteltzen ari zaradatu-baseak taularen indizeak eguneratu behar dituelako indize bakoitzeko O(log(N)) eragiketa garestia erabiliz. Gainera, indizeak gehitzeak lan karga handiagoa dakar transakzio kudeatzailea (artikuluaren amaieran deskribatuko da).

Xehetasun gehiagorako, Wikipediako artikulua ikus dezakezu B+Zuhaitz. B+Tree datu-base batean inplementatzeko adibide bat nahi baduzu, begiratu Artikulu hau и Artikulu hau MySQL garatzaile nagusi batena. InnoDB-k (MySQL motorra) indizeak nola kudeatzen dituen aztertzen dute biek.

Oharra: irakurle batek esan zidan, maila baxuko optimizazioak direla eta, B+ zuhaitza guztiz orekatua egon behar zela.

Hashtable

Gure azken datu egitura garrantzitsua hash taula da. Hau oso erabilgarria da balioak azkar bilatu nahi dituzunean. Gainera, hash taula bat ulertzeak hash join izeneko datu-baseen batzeko eragiketa arrunt bat ulertzen lagunduko digu ( hash batu). Datu-egitura hau datu-baseak barneko gauza batzuk gordetzeko ere erabiltzen du (adibidez. blokeatu mahaia edo buffer igerilekua, bi kontzeptu hauek aurrerago ikusiko ditugu).

Hash taula bat elementu bat bere gakoaren bidez azkar aurkitzen duen datu-egitura da. Hash taula bat eraikitzeko, zehaztu behar duzu:

• gakoa zure elementuetarako
• hash funtzioa giltzetarako. Kalkulatutako gakoen hashek elementuen kokapena ematen dute (deitutakoak segmentuak ).
• teklak alderatzeko funtzioa. Segmentu zuzena aurkitu ondoren, segmentuaren barruan bilatzen ari zaren elementua aurkitu behar duzu konparazio hau erabiliz.

Adibide sinplea

Har dezagun adibide argi bat:

Hash taula honek 10 segmentu ditu. Alferra naizenez, 5 segmentu bakarrik irudikatu ditut, baina badakit burutsua zarela, beraz, beste 5ak zure kabuz irudikatzen utziko dizut. Hash funtzio bat erabili dut gakoaren 10 modulo. Beste era batera esanda, elementuaren gakoaren azken zifra baino ez dut gordetzen bere segmentua aurkitzeko:

• azken zifra 0 bada, elementua 0 segmentuan sartzen da,
• azken zifra 1 bada, elementua 1 segmentuan sartzen da,
• azken zifra 2 bada, elementua 2 eremuan sartzen da,
• ...

Erabili dudan konparazio funtzioa bi zenbaki osoen arteko berdintasuna besterik ez da.

Demagun 78 elementua lortu nahi duzula:

• Hash taulak 78ren hash kodea kalkulatzen du, hau da, 8.
• Hash taulak 8. segmentuari begiratzen dio, eta aurkitzen duen lehen elementua 78 da.
• 78. elementua itzultzen dizu
• Bilaketak 2 eragiketa baino ez ditu kostatzen (bat hash balioa kalkulatzeko eta bestea segmentuaren barruan elementua bilatzeko).

Orain demagun 59 elementua lortu nahi duzula:

• Hash taulak 59ren hash kodea kalkulatzen du, hau da, 9.
• Hash taulak 9. segmentuan bilatzen du, aurkitutako lehen elementua 99 da. 99!=59 denez, 99 elementua ez da baliozko elementua.
• Logika bera erabiliz, bigarren elementua (9), hirugarrena (79), ..., azkena (29) hartzen dira.
• Ez da aurkitu elementua.
• Bilaketak 7 operazio kostatu zituen.

Hash funtzio ona

Ikusten duzunez, bilatzen ari zaren balioaren arabera, kostua ez da berdina!

Orain gakoaren 1 moduluko hash funtzioa aldatzen badut (hau da, azken 000 digituak hartuz), bigarren bilaketak eragiketa bakarra kostatzen du 000 segmentuan elementurik ez dagoenez. Benetako erronka elementu kopuru txikia duten kuboak sortuko dituen hash funtzio on bat aurkitzea da.

Nire adibidean, hash funtzio on bat aurkitzea erraza da. Baina hau adibide sinple bat da, hash funtzio on bat aurkitzea zailagoa da gakoa denean:

• katea (adibidez - abizena)
• 2 lerro (adibidez - abizena eta izena)
• 2 lerro eta data (adibidez - abizena, izena eta jaioteguna)
• ...

Hash funtzio on batekin, hash-taulen bilaketak O(1) balio du.

Array vs hash taula

Zergatik ez erabili array bat?

Hmm, galdera ona.

• Hash taula izan daiteke partzialki memorian kargatuta, eta gainerako segmentuak diskoan gera daitezke.
• Array batekin memorian ondoko espazioa erabili behar duzu. Mahai handi bat kargatzen ari bazara oso zaila da espazio jarraitu nahikoa aurkitzea.
• Hash taula baterako, nahi duzun gakoa hauta dezakezu (adibidez, herrialdea eta pertsonaren abizena).

Informazio gehiagorako, honi buruzko artikulua irakur dezakezu JavaHashMap, hash taula baten ezarpen eraginkorra dena; ez duzu Java ulertu behar artikulu honetan lantzen diren kontzeptuak ulertzeko.

Iturria: www.habr.com