Mhoro, Habr! Ndinokupa kutariswa kweshanduro yechinyorwa
"Databhesi rehukama rinoshanda sei".

Kana zvasvika kune hukama dhatabhesi ini handigone kubatsira asi kufunga kuti chimwe chinhu chisipo. Dzinoshandiswa kwese kwese. Kune akawanda akasiyana dhatabhesi aripo, kubva kudiki uye anobatsira SQLite kune ine simba Teradata. Asi pane zvinyorwa zvishoma zvinotsanangura kuti dhatabhesi inoshanda sei. Unogona kuzvitsvaga uchishandisa "howdoesarelationaldatabasework" kuti uone kuti mishoma mhinduro iripo. Uyezve, zvinyorwa izvi zvipfupi. Kana iwe uchitsvaga yazvino buzzy tekinoroji (BigData, NoSQL kana JavaScript), unowana zvimwe zvakadzama zvinyorwa zvinotsanangura mabatiro avanoita.

Madhatabheti ehukama asakara uye anofinha kuti atsanangurwe kunze kwekosi dzeyunivhesiti, mapepa ekutsvagisa uye mabhuku?

Semugadziri, ndinovenga kushandisa chinhu chandisinganzwisise. Uye kana dhatabhesi yakashandiswa kweanopfuura makore makumi mana, panofanira kunge paine chikonzero. Kwemakore, ndakapedza mazana emaawa kuti ndinyatsonzwisisa aya mabhokisi matema asinganzwisisike andinoshandisa mazuva ese. Relational Databases zvinonakidza chaizvo nekuti ivo zvichibva papfungwa dzinobatsira uye dzinogona kushandiswazve. Kana iwe uchifarira kunzwisisa dhatabhesi, asi usati wambove nenguva kana chido chekunyura mune iyi nyaya yakafara, unofanirwa kunakidzwa nechinyorwa ichi.

Kunyangwe musoro wechinyorwa ichi wakajeka, chinangwa chechinyorwa ichi hachisi chekunzwisisa mashandisirwo edhatabhesi. Saka, iwe unofanirwa kutoziva kunyora nyore chikumbiro chekubatanidza uye mibvunzo yakakosha MHOSVA; zvimwe ungasanzwisisa chinyorwa ichi. Ndizvo chete zvaunofanira kuziva, ndichatsanangura zvimwe.

Ini ndichatanga nezvimwe zvekutanga zvesainzi yekombuta, senge nguva yakaoma yealgorithms (BigO). Ndinoziva kuti vamwe venyu vanovenga pfungwa iyi, asi pasina iyo haungakwanise kunzwisisa kuomesesa mukati medhatabhesi. Sezvo iyi iri musoro mukuru, Ndichatarisa zvandinofunga zvakakosha: kuti database inoita sei SQL kubvunza. Ndichangosuma basic database conceptskuitira kuti pakupera kwechinyorwa iwe une pfungwa yezviri kuitika pasi pehodhi.

Sezvo ichi chiri chinyorwa chakareba uye chehunyanzvi chinosanganisira akawanda algorithms uye data zvimiro, tora nguva yako kuti uverenge mazviri. Dzimwe pfungwa dzingave dzakaoma kunzwisisa; unogona kuvasvetuka uye uchiri kuwana pfungwa yakajairika.

Kune ruzivo rwakanyanya pakati penyu, chinyorwa ichi chakakamurwa kuita zvikamu zvitatu:

• Kutarisisa kwepasi-chikamu uye chepamusoro-chikamu chedatabase zvikamu
• Mhedziso yeQuery Optimization process
• Mhedziso yeTransaction uye Buffer Pool Management

Back to Basics

Makore apfuura (mugwara renzou kure, kure...), vagadziri vaifanira kuziva chaizvo nhamba yemashandiro avaikodha. Ivo vaiziva maalgorithms avo uye data zvimiro nemoyo nekuti vaisakwanisa kutambisa iyo CPU uye ndangariro yemakomputa avo anononoka.

Muchikamu chino, ini ndichakuyeuchidza nezve mamwe aya mazano sezvo akakosha kuti unzwisise dhatabhesi. Ndichasumawo pfungwa database index.

O(1) vs O(n2)

Mazuva ano, vagadziri vazhinji havana hanya nenguva yakaoma yealgorithms ... uye ivo vakarurama!

Asi kana iwe uchibata nedata rakawanda (ini handisi kutaura zviuru) kana iwe uchinetsekana mumamilliseconds, zvinova zvakakosha kuti unzwisise pfungwa iyi. Uye sezvaungafungidzira, dhatabhesi dzinofanirwa kubata nemamiriro ese ari maviri! Ini handichaita kuti iwe upedze imwe nguva yakawanda kupfuura inodiwa kuti unzwisise pfungwa yacho. Izvi zvichatibatsira kunzwisisa pfungwa yemutengo-based optimization gare gare (mutengo inobva optimization).

Concept

Nguva yakaoma yealgorithm inoshandiswa kuona kuti algorithm ichatora nguva yakareba sei kuti ipedze kune yakapihwa huwandu hwe data. Kutsanangura kuomarara uku, tinoshandisa hombe O mathematical notation. Ichi chinyorwa chinoshandiswa nechiito chinotsanangura kuti maoperation mangani anodiwa neagorithm panhamba yakapihwa yezvinopinza.

Semuyenzaniso, kana ndichiti "iyi algorithm ine kuomarara O(some_function())", zvinoreva kuti algorithm inoda some_function(a_certain_amount_of_data) mashandiro ekugadzirisa yakati data.

saka Haisi iyo nhamba yedata yakakosha **, zvimwe ** iyo nhamba yekushanda inowedzera sei nekuwedzera data data. Nguva yakaoma haipe nhamba chaiyo yekushanda, asi inzira yakanaka yekufungidzira nguva yekuuraya.

Mune ino girafu iwe unogona kuona huwandu hwekushanda maringe nehuwandu hwe data yekuisa yemhando dzakasiyana dzealgorithm nguva yakaoma. Ndakashandisa logarithmic scale kuvaratidza. Mune mamwe mazwi, huwandu hwe data hunokurumidza kuwedzera kubva pa1 kusvika kubhiriyoni 1. Tinogona kuona kuti:

• O (1) kana kuramba kuoma kunoramba kuripo (zvikasadaro hazvizonzi zvinogara zvichinetsa).
• O(danda(n)) inoramba yakaderera kunyangwe nemabhiriyoni e data.
• Kuoma kwakanyanya - O(n2), uko nhamba yekushanda inokura nekukurumidza.
• Mamwe matambudziko maviri anowedzera nekukurumidza.

mienzaniso

Nehuwandu hudiki hwe data, musiyano uripo pakati peO(1) neO(n2) haugoneki. Semuenzaniso, ngatiti iwe une algorithm inoda kugadzirisa 2000 zvinhu.

• Iyo O (1) algorithm ichakubhadhara iwe 1 oparesheni
• Iyo O(log(n)) algorithm ichakubhadharira 7 mashandiro
• Iyo O (n) algorithm ichakubhadhara iwe zviuru zviviri zvekushanda
• Iyo O(n*log(n)) algorithm ichakudyira zviuru gumi nezvina maoperation
• Iyo O(n2) algorithm ichakubhadhara iwe zviuru zvina zvemabasa

Musiyano uripo pakati peO(1) neO(n2) unoratidzika kunge wakakura (4 miriyoni maoperation) asi ucharasikirwa nepamusoro pe2 ms, inguva yekubwaira maziso ako. Chokwadi, ma processors emazuva ano anogona kugadzirisa mazana emamiriyoni ekushanda pasekondi. Ichi ndicho chikonzero kuita uye optimization isiri nyaya mumapurojekiti mazhinji eIT.

Sezvandakataura, zvichiri kukosha kuziva iyi pfungwa kana uchishanda nehuwandu hukuru hwe data. Kana panguva ino iyo algorithm inofanirwa kugadzirisa zviuru zvezvinhu (zvisiri izvo zvakanyanya kune dhatabhesi):

• Iyo O (1) algorithm ichakubhadhara iwe 1 oparesheni
• Iyo O(log(n)) algorithm ichakubhadharira 14 mashandiro
• Iyo O (n) algorithm ichakubhadhara iwe chiuru chekushanda
• Iyo O(n*log(n)) algorithm ichakubhadharira zviuru gumi nezvina maoperation.
• Iyo O(n2) algorithm ichakubhadhara 1 mashandiro.

Ini handina kuita masvomhu, asi ndingati neO(n2) algorithm une nguva yekunwa kofi (kunyangwe maviri!). Kana iwe ukawedzera imwe 0 kune vhoriyamu yedata, iwe uchave nenguva yekurara.

Ngatipindei zvakadzama

For reference:

• Iyo yakanaka hash tafura yekutarisa inowana chinhu muO (1).
• Kutsvaga muti wakanyatsogadzikana kunoburitsa mibairo muO(log(n)).
• Kutsvaga muunganidzwa kunoburitsa mibairo muO(n).
• Iwo akanakisa ekuronga algorithms ane kuomarara O(n*log(n)).
• Iyo yakaipa yekuronga algorithm ine yakaoma O(n2).

Ongorora: Muzvikamu zvinotevera tichaona aya algorithms uye data zvimiro.

Kune akati wandei marudzi ealgorithm nguva yakaoma:

• avhareji kesi mamiriro
• best case scenario
• uye yakaipisisa mamiriro ezvinhu

Nguva yakaoma kazhinji ndiyo yakaipisisa mamiriro ezvinhu.

Ini ndaingotaura nezve nguva yakaoma yealgorithm, asi kuomarara kunoshandawo kune:

• ndangariro kushandiswa kwealgorithm
• disk I / O kushandiswa kwegorgorithm

Ehe, kune matambudziko akaipisisa kupfuura n2, semuenzaniso:

• n4: izvi zvakaipa! Mamwe eakataurwa algorithms ane iyi yakaoma.
• 3n: izvi zvakatoipa! Imwe yealgorithms yatichaona pakati pechinyorwa ichi ine iyi yakaoma (uye inonyatso shandiswa mune dzakawanda dhatabhesi).
• factorial n: haufe wakawana mibairo yako kunyangwe uine hushoma hwe data.
• nn: Kana ukasangana nekuoma uku, unofanirwa kuzvibvunza kana iri iro chairo ndima yako yekuita ...

Cherechedza: Handina kukupa tsanangudzo chaiyo yezita guru reO, pfungwa chete. Unogona kuverenga chinyorwa ichi pa Wikipedia kune chaiyo (asymptotic) tsananguro.

MergeSort

Unoitei kana iwe uchida kuronga muunganidzwa? Chii? Iwe unodaidza rudzi () basa ... Ok, mhinduro yakanaka ... Asi kune dhatabhesi, unofanirwa kunzwisisa kuti iyi sort() inoshanda sei.

Kune akati wandei akanaka ekuronga algorithms, saka ini ndichatarisa pane zvakanyanya kukosha: merge sort. Iwe unogona kusanzwisisa kuti nei kuronga data kuchibatsira izvozvi, asi iwe unofanirwa mushure memubvunzo wekugadzirisa chikamu. Uyezve, kunzwisisa kubatanidza mhando kunozotibatsira gare gare kunzwisisa iyo yakajairwa dhatabhesi yejoinha mashandiro anonzi famba Join (kubatana kwekubatana).

Batanidza

Kufanana nemaalgorithms mazhinji anobatsira, kusanganisa rudzi kunovimba nehunyengeri: kusanganisa 2 akarongedzerwa arrays ehukuru N/2 muN-element yakarongwa array inongodhura N mashandiro. Kuvhiya uku kunonzi kubatanidza.

Ngationei kuti izvi zvinorevei nemuenzaniso wakapfava:

Ichi chiverengero chinoratidza kuti kuvaka yekupedzisira yakarongedzwa 8-element array, iwe unongoda kudzokorora kamwe pamusoro peiyo 2 4-element arrays. Sezvo ese 4-element arrays atorongwa kare:

• 1) unofananidza zvese zviri zviviri zvinhu zvazvino muzvikamu zviviri (pakutanga ikozvino = kutanga)
• 2) wobva watora diki diki kuti uiise mu 8 element array
• 3) uye famba uchienda kune chinotevera chinhu muhurongwa kwawakatora chinhu chidiki
• uye dzokorora 1,2,3 kusvika wasvika kune yekupedzisira chinhu cheimwe yearrays.
• Wobva watora izvo zvasara zveimwe array kuti uzviise mu 8 element array.

Izvi zvinoshanda nekuti ese 4-element arrays akarongedzerwa uye saka haufanirwe "kudzokera" mune izvo arrays.

Zvino zvatiri kunzwisisa hunyengeri, heino pseudocode yangu yekubatanidza:

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 inotyora dambudziko kuita madiki matambudziko uye wozowana mhedzisiro yematambudziko madiki kuti uwane mhedzisiro yedambudziko rekutanga (chinyorwa: iyi mhando yealgorithm inonzi divide and conquer). Kana iwe usinganzwisise algorithm iyi, usanetseka; Handina kuzvinzwisisa pandakatanga kuzviona. Kana ichigona kukubatsira, ini ndinoona iyi algorithm seaviri-chikamu algorithm:

• Chikamu chechikamu, apo mutsara wakakamurwa kuita zvidimbu zvidiki
• Chinhanho chekuronga ndipo panosanganiswa mitsara midiki (uchishandisa mubatanidzwa) kuita hurongwa hwakakura.

Chikamu chechikamu

Muchikamu chekuparadzanisa, mutsara wakakamurwa kuita umwechete arrays mumatanho matatu. Nhamba yakarongeka yematanho ilogi(N) (sezvo N=3, log(N) = 8).

Ndozviziva sei izvi?

Ndiri shasha! Mushoko - masvomhu. Pfungwa iyi ndeyokuti nhanho imwe neimwe inoparadzanisa ukuru hwekutanga kwekutanga ne 2. Nhamba yematanho ndiyo nhamba yenguva dzaunogona kugovera mutsara wepakutanga kuita maviri. Iyi ndiyo tsanangudzo chaiyo yelogarithm (base 2).

Kuronga chikamu

Muchikamu chekugadzirisa, iwe unotanga nekubatana (chimwe-chimwe chinhu) arrays. Munguva yega yega nhanho iwe unoshandisa akawanda ekubatanidza mashandiro uye iyo yakazara mutengo N = 8 mashandiro:

• Muchikamu chekutanga une 4 mamenges ayo anodhura maoperation maviri ega ega
• Munhanho yechipiri une 2 mamenges ayo anodhura 4 maoparesheni ega ega
• Munhanho yechitatu une 1 kubatanidza iyo inodhura 8 maoperation

Sezvo paine log(N) nhanho, mari yose N * log(N) mashandiro.

Zvakanakira kubatanidza mhando

Nei iyi algorithm ine simba zvakadaro?

Nokuti:

• Iwe unogona kuichinja kuti uderedze ndangariro tsoka kuitira kuti urege kugadzira matsva arrays asi zvakananga gadzirisa iyo yekuisa array.

Ongorora: iyi mhando yealgorithm inonzi in-nzvimbo (kuronga pasina imwe ndangariro).

• Iwe unogona kuishandura kuti ushandise dhisiki nzvimbo uye diki ndangariro panguva imwe chete pasina kuunza yakakosha dhisiki I / O pamusoro. Pfungwa ndeyekurodha mundangariro chete izvo zvikamu zviri kugadziriswa izvozvi. Izvi zvakakosha kana iwe uchida kugadzirisa akawanda-gigabyte tafura ine chete 100-megabyte memory buffer.

Ongorora: iyi mhando yealgorithm inonzi kurongedza kwekunze.

• Unogona kuichinja kuti imhanye pane akawanda maitiro/shinda/maseva.

Semuenzaniso, yakagovaniswa merge sort ndechimwe chezvinhu zvakakosha Hadoop (inova chimiro mune data hombe).

• Iyi algorithm inogona kushandura lead kuita goridhe (chaizvo!).

Iyi yekuronga algorithm inoshandiswa mune akawanda (kana asiri ese) dhatabhesi, asi haisiriyo yega. Kana uchida kuziva zvakawanda, unogona kuverenga izvi basa rekutsvakurudza, iyo inokurukura zvakanakira nezvayakaipira zveyakajairwa dhatabhesi kuronga algorithms.

Array, Muti uye Hash Tafura

Iye zvino zvatiri kunzwisisa iyo pfungwa yekuoma kwenguva uye kuronga, ini ndinofanira kukuudza nezve 3 data zvimiro. Izvi zvakakosha nekuti ivo ndiwo hwaro hwezvinyorwa zvemazuva ano. Ndichasumawo pfungwa database index.

Array

A maviri-dimensional array ndiyo yakapfava data chimiro. Tafura inogona kufungidzirwa seyakarongwa. Semuyenzaniso:

Iyi 2-dimensional array itafura ine mitsetse nemakoramu:

• Mutsara wega wega unomiririra chimwe chinhu
• Makolamu anochengetera zvimiro zvinotsanangura sangano.
• Imwe neimwe column inochengeta data yerudzi chairwo (integer, tambo, date...).

Izvi zvakanakira kuchengetedza uye kuona data, zvisinei, kana iwe uchida kuwana chaiyo kukosha, izvi hazvina kukodzera.

Semuyenzaniso, kana waida kutsvaga vakomana vese vanoshanda kuUK, waizofanira kutarisa mutsetse wega wega kuti uone kana mutsara iwoyo ndeweUK. Ichakubhadharira N transactionskupi N - nhamba yemitsara, iyo isina kushata, asi pangava nenzira inokurumidza here? Iye zvino yave nguva yekuti tijairane nemiti.

Cherechedzo: Mazhinji dhatabhesi emazuva ano anopa mitsara yakawedzerwa yekuchengetedza matafura nemazvo: mirwi-yakarongwa uye index-yakarongwa. Asi izvi hazvichinje dambudziko rekukurumidza kuwana mamiriro chaiwo muboka remakoramu.

Database muti uye index

Muti webhinari yekutsvaga muti webhinari une pfuma yakakosha, kiyi pane imwe neimwe node inofanira kunge iri:

• chikuru kupfuura makiyi ese akachengetwa muzasi memuti
• isingasviki makiyi ese akachengetwa mumuti muduku chaiwo

Ngationei kuti izvi zvinorevei nekuona

Idea

Muti uyu une N = 15 zvinhu. Ngatiti ndiri kutsvaga 208:

• Ini ndinotanga pamudzi iyo kiyi iri 136. Kubva 136 <208, ndinotarisa kurudyi subtree ye node 136.
• 398>208 saka ndiri kutarisa kuruboshwe subtree ye node 398
• 250>208 saka ndiri kutarisa kuruboshwe subtree ye node 250
• 200<208, saka ndiri kutarisa kune kurudyi subtree ye node 200. Asi 200 haina kurudyi subtree, kukosha hakuna (nekuti kana iripo, ichave iri mugwara chairo 200).

Zvino ngatiti ndiri kutsvaga makumi mana

• Ndinotanga pamudzi ine kiyi iri 136. Kubva 136 > 40, ndinotarisa kuruboshwe subtree ye node 136.
• 80> 40, saka ndiri kutarisa kuruboshwe subtree ye node 80
• 40= 40, node iripo. Ini ndinotora mutsara ID mukati menode (isina kuratidzwa mumufananidzo) uye tarisa mutafura yeiyo yakapihwa mutsara ID.
• Kuziva mutsara ID kunonditendera kuti ndizive chaizvo pane iyo data iri patafura, saka ndinogona kuitora ipapo ipapo.

Pakupedzisira, kutsvaga kwese kunondidyira nhamba yemazinga mukati memuti. Kana iwe ukaverenga chikamu nezve merge sort zvakanyatsonaka, iwe unofanirwa kuona kuti pane log(N) mazinga. Zvinoitika, tsvaga mutengo log(N), kusaipa!

Ngatidzokere kudambudziko redu

Asi izvi ndezvekufungidzira, saka ngatidzokere kudambudziko redu. Panzvimbo pechiverengero chakareruka, fungidzira tambo inomiririra nyika yemumwe munhu patafura yapfuura. Ngatitii une muti une "nyika" munda (koramu 3) yetafura:

• Kana iwe uchida kuziva kuti ndiani anoshanda kuUK
• iwe unotarisa pamuti kuti uwane node inomiririra Great Britain
• mukati me "UKnode" iwe unowana nzvimbo yeUK marekodhi evashandi.

Kutsvaga uku kunodhura log(N) mashandiro pachinzvimbo cheN mashandiro kana ukashandisa array zvakananga. Zvawangotaura ndizvo database index.

Unogona kuvaka index muti kune chero boka reminda (tambo, nhamba, 2 mitsetse, nhamba uye tambo, zuva...) chero uine basa rekuenzanisa makiyi (kureva mapoka emunda) kuti ugone kuseta. kurongeka pakati pekiyi (ndiyo mamiriro emhando ipi neipi mudhatabhesi).

B+TreeIndex

Kunyange zvazvo muti uyu uchishanda zvakanaka kuti uwane kukosha kwakakosha, pane dambudziko reBIG paunenge uchida wana zvinhu zvakawanda pakati pezvakakosha zviviri. Izvi zvinodhura O(N) nekuti uchafanirwa kutarisa imwe node mumuti wotarisa kana iri pakati pezviviri izvi zvakakosha (semuenzaniso neyakarairwa kufamba kwemuti). Uyezve, kuvhiya uku hakusi dhisiki I / O hushamwari sezvo uchifanira kuverenga muti wese. Isu tinofanirwa kutsvaga nzira yekuita zvinobudirira range chikumbiro. Kugadzirisa dambudziko iri, dhatabhesi dzemazuva ano dzinoshandisa shanduro yakagadziridzwa yemuti wapfuura unonzi B + Tree. Mumuti B+Muti:

• chete node dzakaderera (mashizha) chengetedza ruzivo (nzvimbo yemitsara mutafura ine hukama)
• mamwe ma nodes ari pano yekufambisa kune node chaiyo panguva yekutsvaga.

Sezvauri kuona, kune mamwe ma node pano (kaviri). Zvechokwadi, iwe une dzimwe nodes, "decision nodes", iyo ichakubatsira iwe kuwana node yakarurama (iyo inochengetedza nzvimbo yemitsara mutafura yakabatana). Asi iyo yekutsvaga yakaoma ichiri O(log(N)) (kune imwe chete imwe nhanho). Musiyano mukuru ndewekuti node padanho rezasi dzakabatana nevanotsiva.

Neiyi B + Muti, kana iwe uchitsvaga kukosha pakati pe40 ne100:

• Iwe unongoda kutsvaga makumi mana (kana kukosha kwepedyo mushure me40 kana makumi mana asipo) sezvawakaita nemuti wapfuura.
• Wozounganidza vagari venhaka makumi mana uchishandisa zvakananga mudyi wenhaka kusvika wasvika zana.

Toti unowana M vatevedzeri uye muti une N nodes. Kutsvaga imwe node inodhura log (N) semuti wapfuura. Asi kana iwe uchinge wawana iyi node, iwe unowana M vatevedzeri muM mashandiro ane mareferensi kune avo vanotsiva. Kutsvaga uku kunongoda M+log(N) mashandiro akaenzaniswa neN mashandiro pamuti wapfuura. Uyezve, haufanirwe kuverenga muti uzere (chete M + log (N) node), zvinoreva kushoma dhisiki kushandiswa. Kana M ari mudiki (semuenzaniso mitsara mazana maviri) uye N yakakura (200 mitsara), pachava neBIG musiyano.

Asi pane matambudziko matsva pano (zvakare!). Kana iwe ukawedzera kana kudzima mutsara mudhatabhesi (uye nekudaro mune yakabatana B + Tree index):

• iwe unofanirwa kuchengetedza kurongeka pakati pemanodhi mukati meB + Muti, kana zvisina kudaro hauzokwanisi kuwana node mukati memuti usina kusarudzwa.
• unofanira kuchengeta hushoma hunobvira huwandu hwemazinga muB+Muti, zvikasadaro iyo O(log(N)) nguva yakaoma inova O(N).

Mune mamwe mazwi, B + Muti unofanirwa kunge uchizvirongedza uye wakaenzana. Neraki, izvi zvinogoneka nekuchenjera kudzima uye kuisa mashandiro. Asi izvi zvinouya nemubhadharo: kuiswa uye kudzima muB+ muti kunodhura O(log(N)). Ndiko kusaka vamwe venyu vakazvinzwa kushandisa indexes akawandisa haisi pfungwa yakanaka. Chokwadi, uri kunonoka kukurumidza kuisa / kugadzirisa / kudzima mutsara mutafuranekuti dhatabhesi inoda kuvandudza indexes dzetafura uchishandisa inodhura O(log(N)) mashandiro kune imwe neimwe index. Uyezve, kuwedzera indexes zvinoreva kuwanda kwebasa re maneja wekutengesa (ichatsanangurwa pakupera kwechinyorwa).

Kuti uwane rumwe ruzivo, iwe unogona kuona iyo Wikipedia chinyorwa pa B+Muti. Kana iwe uchida muenzaniso wekushandisa B + Muti mune dhatabhesi, tarisa ichi chinyorwa и ichi chinyorwa kubva kune anotungamira MySQL mugadziri. Ivo vese vanotarisa kuti InnoDB (iyo MySQL injini) inobata sei indexes.

Ongorora: Mumwe muverengi akandiudza kuti, nekuda kweiyo yakaderera-level optimizations, iyo B + muti unofanirwa kuve wakaenzana.

Hashtable

Yedu yekupedzisira yakakosha data chimiro ndiyo tafura yehashi. Izvi zvinobatsira zvakanyanya kana iwe uchida kukurumidza kutarisa maitiro. Uyezve, kunzwisisa tafura yehashi kuchatibatsira gare gare kunzwisisa yakajairwa dhatabhesi yejoinopera inonzi hash join ( hash join) Ichi chimiro chedata chinoshandiswawo nedatabase kuchengetedza zvimwe zvinhu zvemukati (e.g. lock table kana buffer dziva, tichaona maviri aya pfungwa gare gare).

Tafura yehashi idhizaini yedata inokurumidza kuwana chinhu nekiyi yayo. Kuti ugadzire tafura yehashi unofanirwa kutsanangura:

• the key zvezvinhu zvako
• hash basa zvekiyi. Iwo akaverengerwa kiyi hashes anopa nzvimbo yezvinhu (zvinodanwa zvikamu ).
• basa rekuenzanisa makiyi. Kana uchinge wawana chikamu chaicho, iwe unofanirwa kuwana chinhu chauri kutsvaga mukati mechikamu uchishandisa iyi kuenzanisa.

Muenzaniso uri nyore

Ngatitorei muenzaniso wakajeka:

Iyi tafura yehashi ine zvikamu gumi. Nekuti ndine nungo, ndinongoratidzira zvikamu zvishanu, asi ndinoziva kuti wakangwara, saka ndichakurega utore mamwe mashanu uri wega. Ndakashandisa hash basa modulo 10 yekiyi. Mune mamwe mazwi, ini ndinochengeta chete nhamba yekupedzisira yekiyi yechinhu kuti uwane chikamu chayo:

• kana nhamba yekupedzisira iri 0, chinhu chinowira muchikamu 0,
• kana nhamba yekupedzisira iri 1, chinhu chinowira muchikamu 1,
• kana nhamba yekupedzisira iri 2, chinhu chinowira munharaunda 2,
• ...

Basa rekuenzanisa randakashandisa kungoenzana pakati pezvikamu zviviri.

Ngatiti iwe unoda kuwana chikamu 78:

• Iyo hashi tafura inoverengera iyo hashi kodhi ye78, inova 8.
• Tafura yehashi inotarisa chikamu 8, uye chinhu chekutanga chainowana i78.
• Anodzosera chinhu 78 kwauri
• Kutsvaga kunodhura maoperation maviri chete (imwe kuverenga kukosha kwehashi uye imwe kutarisa kumusoro kwechinhu mukati mechikamu).

Zvino ngatiti iwe unoda kutora chikamu 59:

• Iyo hashi tafura inoverengera iyo hashi kodhi ye59, inova 9.
• Tafura yehashi inotsvaga muchikamu chepfumbamwe, chinhu chekutanga chawanikwa i9. Kubva 99!=99, chikamu 59 hachisi chinhu chinoshanda.
• Kushandisa pfungwa imwechete, chinhu chechipiri (9), chechitatu (79), ..., chekupedzisira (29) chinotorwa.
• Element haina kuwanikwa.
• Kutsvaga kunodhura 7 maitiro.

Zvakanaka hashi basa

Sezvauri kuona, zvichienderana nekukosha kwauri kutsvaga, mutengo hauna kufanana!

Kana ini zvino ndikachinja hashi basa modulo 1 yekiyi (kureva, kutora manhamba matanhatu ekupedzisira), kutarisa kwechipiri kunodhura 000 oparesheni sezvo pasina zvinhu muchikamu 000. Dambudziko chairo nderekutsvaga yakanaka hashi basa rinogadzira mabhaketi ane nhamba shoma yezvinhu.

Mumuenzaniso wangu, kuwana yakanaka hashi basa iri nyore. Asi uyu muenzaniso wakapfava, kuwana yakanaka hashi basa kunonetsa kana kiyi iri:

• tambo (semuenzaniso - zita rekupedzisira)
• 2 mitsetse (semuenzaniso - zita rekupedzisira uye rekutanga)
• 2 mitsetse uye zuva (semuenzaniso - zita rekupedzisira, zita rekutanga uye zuva rekuzvarwa)
• ...

Iine yakanaka hashi basa, hashi tafura yekutarisa inodhura O(1).

Array vs hash tafura

Wadii kushandisa array?

Hmm, mubvunzo wakanaka.

• Tafura yehashi inogona kuva zvakazara mundangariro, uye zvikamu zvakasara zvinogona kuramba zviri pa diski.
• Ne array unofanira kushandisa contiguous nzvimbo mundangariro. Kana uri kurodha tafura hombe zvakaoma zvikuru kuwana nzvimbo yakakwana inopfuurira.
• Kune tafura yehashi, unogona kusarudza kiyi yaunoda (semuenzaniso, nyika uye zita rekupedzisira remunhu).

Kuti uwane rumwe ruzivo, unogona kuverenga chinyorwa nezve JavaHashMap, inova kushanda kwakanaka kwetafura yehashi; haufanire kunzwisisa Java kuti unzwisise pfungwa dzakafukidzwa muchinyorwa ichi.

Source: www.habr.com