Hoy Habr! Gipresentar ko sa imong pagtagad ang hubad sa artikulo
"Giunsa ang pagtrabaho sa usa ka relational database".

Kung bahin sa relational database dili nako malikayan nga maghunahuna nga adunay kulang. Gigamit kini bisan asa. Adunay daghang lainlaing mga database nga magamit, gikan sa gamay ug mapuslanon nga SQLite hangtod sa kusgan nga Teradata. Apan adunay pipila ra nga mga artikulo nga nagpatin-aw kung giunsa ang pagtrabaho sa database. Mahimo nimong pangitaon ang imong kaugalingon gamit ang "howdoesarelationaldatabasework" aron makita kung pila ang mga resulta. Dugang pa, kini nga mga artikulo mubo. Kung nangita ka sa labing bag-o nga buzzy nga teknolohiya (BigData, NoSQL o JavaScript), makit-an nimo ang labi ka lawom nga mga artikulo nga nagpatin-aw kung giunsa kini molihok.

Ang mga relational database ba karaan na ug makalaay kaayo nga ipasabut gawas sa mga kurso sa unibersidad, mga research paper ug mga libro?

Isip usa ka developer, gidumtan nako ang paggamit sa usa ka butang nga dili nako masabtan. Ug kung ang mga database gigamit sa sobra sa 40 ka tuig, kinahanglan adunay usa ka hinungdan. Sulod sa mga katuigan, migugol ako og gatusan ka oras aron tinuod nga masabtan kining mga katingad-an nga itom nga mga kahon nga akong gigamit kada adlaw. Relasyonal nga mga database interesting kaayo kay sila base sa mapuslanon ug magamit pag-usab nga mga konsepto. Kung interesado ka nga masabtan ang usa ka database, apan wala ka’y oras o hilig sa pagsusi sa kini nga halapad nga hilisgutan, kinahanglan nimo nga malingaw kini nga artikulo.

Bisan tuod ang ulohan niining artikuloha klaro, ang katuyoan niini nga artikulo dili aron masabtan kung giunsa ang paggamit sa database. Busa, kinahanglan nga nahibal-an na nimo kung giunsa pagsulat ang usa ka yano nga hangyo sa koneksyon ug sukaranan nga mga pangutana SI KRUD; kung dili mahimo nga dili nimo masabtan kini nga artikulo. Mao ra kana ang kinahanglan nimong mahibal-an, akong ipasabut ang nahabilin.

Magsugod ko sa pipila ka sukaranan sa siyensya sa kompyuter, sama sa pagkakomplikado sa oras sa mga algorithm (BigO). Nahibal-an ko nga ang pipila kaninyo nagdumot niini nga konsepto, apan kung wala kini dili nimo masabtan ang mga kakuti sa sulod sa database. Tungod kay kini usa ka dako nga hilisgutan, Magpokus ko sa unsay akong gihunahuna nga importante: kung giunsa ang pagproseso sa database SQL pagpangutana. magpaila lang ko batakang mga konsepto sa databasearon sa katapusan sa artikulo ikaw adunay usa ka ideya kung unsa ang nahitabo sa ilawom sa hood.

Tungod kay kini usa ka taas ug teknikal nga artikulo nga naglambigit sa daghang mga algorithm ug istruktura sa datos, paggahin sa imong oras sa pagbasa niini. Ang ubang mga konsepto mahimong lisod sabton; mahimo nimong laktawan sila ug makuha gihapon ang kinatibuk-ang ideya.

Alang sa mas kahibalo sa taliwala ninyo, kini nga artikulo gibahin sa 3 ka bahin:

Overview sa ubos nga lebel ug taas nga lebel nga mga sangkap sa database
Overview sa Proseso sa Pag-optimize sa Pangutana
Overview sa Transaksyon ug Buffer Pool Management

Balik sa sukaranan

Mga tuig na ang milabay (sa usa ka galaxy nga layo, layo ...), ang mga developers kinahanglan nga masayud sa tukma sa gidaghanon sa mga operasyon nga ilang coding. Nahibal-an nila sa kasingkasing ang ilang mga algorithm ug istruktura sa datos tungod kay dili nila makaya nga usik-usik ang CPU ug memorya sa ilang hinay nga mga kompyuter.

Niini nga bahin, pahinumdoman ko ikaw sa pipila niini nga mga konsepto tungod kay kini hinungdanon aron masabtan ang database. Ipaila usab nako ang konsepto indeks sa database.

O(1) batok sa O(n2)

Karong panahona, daghang mga developer ang wala magtagad bahin sa pagkakomplikado sa oras sa mga algorithm ... ug husto sila!

Apan kung nag-atubang ka sa daghang mga datos (wala ako nagsulti nga libu-libo) o kung nanlimbasug ka sa mga millisecond, mahimong kritikal nga masabtan kini nga konsepto. Ug ingon sa imong mahanduraw, ang mga database kinahanglan nga atubangon ang duha nga mga sitwasyon! Dili ko nimo hatagi og dugang nga oras kaysa kinahanglan aron masulti ang punto. Makatabang kini kanamo nga masabtan ang konsepto sa pag-optimize nga gibase sa gasto sa ulahi (gasto Base pagkamalaumon).

Konsepto

Ang pagkakomplikado sa oras sa algorithm gigamit aron makita kung unsa kadugay ang pag-execute sa usa ka algorithm alang sa gihatag nga kantidad sa datos. Aron ihulagway kini nga pagkakomplikado, gigamit namo ang dako nga notasyon sa matematika nga O. Kini nga notasyon gigamit uban sa usa ka function nga naghulagway kung pila ka mga operasyon ang gikinahanglan sa usa ka algorithm alang sa gihatag nga gidaghanon sa mga input.

Pananglitan, kung moingon ko nga "kini nga algorithm adunay pagkakomplikado O (some_function ())", kini nagpasabut nga ang algorithm nanginahanglan pipila nga_function (a_certain_amount_of_data) nga mga operasyon aron maproseso ang usa ka piho nga kantidad sa datos.

Mao kini ang Dili ang gidaghanon sa datos ang hinungdanon**, kon dili ** kung giunsa ang gidaghanon sa mga operasyon nagdugang uban ang pagtaas sa gidaghanon sa datos. Ang pagkakomplikado sa oras wala maghatag ug eksaktong gidaghanon sa mga operasyon, apan usa ka maayong paagi sa pagbanabana sa oras sa pagpatuman.

Niini nga graph imong makita ang gidaghanon sa mga operasyon kumpara sa gidaghanon sa input data alang sa lain-laing mga matang sa algorithm sa pagkakomplikado sa panahon. Gigamit nako ang logarithmic scale aron ipakita kini. Sa laing pagkasulti, ang gidaghanon sa datos dali nga misaka gikan sa 1 ngadto sa 1 bilyon. Makita nato nga:

Ang O(1) o kanunay nga pagkakomplikado nagpabilin nga makanunayon (kon dili kini matawag nga kanunay nga pagkakomplikado).
O(log(n)) nagpabilin nga ubos bisan pa sa binilyon nga datos.
Ang pinakagrabe nga kalisud - O(n2), diin ang gidaghanon sa mga operasyon paspas nga mitubo.
Ang laing duha ka komplikasyon dali ra nga modaghan.

mga panig-ingnan

Uban sa gamay nga gidaghanon sa datos, ang kalainan tali sa O(1) ug O(n2) kay gamay ra. Pananglitan, ingnon ta nga ikaw adunay algorithm nga kinahanglan magproseso sa 2000 nga mga elemento.

Ang O(1) algorithm mogasto nimo og 1 ka operasyon
Ang O(log(n)) algorithm mogasto kanimo ug 7 ka operasyon
Ang O(n) algorithm mogasto kanimo og 2 ka operasyon
Ang O(n*log(n)) algorithm mogasto nimo ug 14 ka operasyon
Ang O(n2) nga algorithm mogasto kanimo og 4 ka operasyon

Ang kalainan tali sa O(1) ug O(n2) morag dako (4 milyon nga operasyon) apan mawad-an ka ug maximum nga 2 ms, panahon lang sa pagpamilok sa imong mga mata. Sa pagkatinuod, ang modernong mga processor makaproseso gatusan ka milyon nga mga operasyon matag segundo. Mao kini ang hinungdan nga ang pasundayag ug pag-optimize dili usa ka isyu sa daghang mga proyekto sa IT.

Sama sa akong giingon, hinungdanon nga mahibal-an kini nga konsepto kung nagtrabaho uban ang daghang mga datos. Kung niining higayona ang algorithm kinahanglan nga magproseso sa 1 nga mga elemento (nga dili kaayo alang sa usa ka database):

Ang O(1) algorithm mogasto nimo og 1 ka operasyon
Ang O(log(n)) algorithm mogasto kanimo ug 14 ka operasyon
Ang O(n) nga algorithm mogasto kanimo og 1 ka operasyon
Ang O(n*log(n)) nga algorithm mogasto kanimo ug 14 ka operasyon
Ang O(n2) nga algorithm mogasto kanimo og 1 nga operasyon

Wala pa ko makahimo sa matematika, apan ako moingon nga sa O(n2) algorithm aduna kay panahon sa pag-inom ug kape (bisan duha!). Kung magdugang ka og laing 0 sa gidaghanon sa datos, aduna kay panahon sa pagkatulog.

Mas lawom ta

Alang sa pakisayran:

Ang usa ka maayo nga hash table lookup nakakaplag ug elemento sa O(1).
Ang pagpangita sa usa ka maayo nga balanse nga kahoy nagpatunghag mga resulta sa O(log(n)).
Ang pagpangita sa usa ka laray nagpatunghag mga resulta sa O(n).
Ang labing maayo nga mga algorithm sa paghan-ay adunay pagkakomplikado O(n*log(n)).
Ang dili maayo nga algorithm sa paghan-ay adunay pagkakomplikado O(n2).

Hinumdomi: Sa mosunod nga mga bahin atong makita kini nga mga algorithm ug mga istruktura sa datos.

Adunay daghang mga matang sa pagkakomplikado sa oras sa algorithm:

kasagaran nga senaryo sa kaso
labing maayo nga senaryo sa kaso
ug worst case scenario

Ang pagkakomplikado sa oras kasagaran ang pinakagrabe nga senaryo sa kaso.

Naghisgot lang ako bahin sa pagkakomplikado sa oras sa algorithm, apan ang pagkakomplikado magamit usab sa:

konsumo sa memorya sa algorithm
disk I/O konsumo algorithm

Siyempre, adunay mga komplikasyon nga mas grabe pa sa n2, pananglitan:

n4: makalilisang! Ang pila sa nahisgutan nga mga algorithm adunay kini nga pagkakomplikado.
3n: mas grabe pa ni! Usa sa mga algorithm nga atong makita sa tunga-tunga sa kini nga artikulo adunay kini nga pagkakomplikado (ug kini sa tinuud gigamit sa daghang mga database).
factorial n: dili nimo makuha ang imong mga resulta bisan sa gamay nga kantidad sa datos.
nn: Kung makasugat ka niini nga pagkakomplikado, kinahanglan nimong pangutan-on ang imong kaugalingon kung kini ba gyud ang imong natad sa kalihokan...

Mubo nga sulat: Wala ko naghatag kanimo sa aktwal nga kahulugan sa dako nga ngalan sa O, usa lamang ka ideya. Mahimo nimong basahon kini nga artikulo sa Wikipedia para sa tinuod (asymptotic) nga kahulugan.

MergeSort

Unsa ang imong buhaton kung kinahanglan nimo paghan-ay ang usa ka koleksyon? Unsa? Gitawag nimo ang sort() function... Ok, maayong tubag... Apan para sa database, kinahanglan nimong masabtan kung giunsa kini nga sort() function naglihok.

Adunay ubay-ubay nga maayo nga mga algorithm sa paghan-ay, mao nga akong ipunting ang labing hinungdanon: merge sort. Mahimong dili nimo masabtan kung ngano nga ang paghan-ay sa datos mapuslanon karon, apan kinahanglan nimo pagkahuman sa bahin sa pag-optimize sa pangutana. Dugang pa, ang pagsabot sa merge sort makatabang nato sa ulahi nga masabtan ang komon nga database join operation nga gitawag paghiusa apil (paghiusa nga asosasyon).

Paghiusa

Sama sa daghang mapuslanong mga algorithm, ang merge sort nagsalig sa usa ka lansis: ang pagkombinar sa 2 ka han-ay nga arrays sa gidak-on N/2 ngadto sa N-element sorted array nagkantidad lang ug N operations. Kini nga operasyon gitawag nga paghiusa.

Atong tan-awon kung unsa ang gipasabut niini sa usa ka yano nga pananglitan:

Kini nga numero nagpakita nga aron matukod ang kataposang gihan-ay nga 8-elemento nga han-ay, kinahanglan ka nga mag-uli sa makausa sa 2 4-elemento nga han-ay. Tungod kay ang duha ka 4-element arrays nahan-ay na:

1) imong itandi ang duha ka kasamtangan nga mga elemento sa duha ka arrays (sa sinugdanan kasamtangan = una)
2) unya kuhaa ang pinakagamay aron ibutang kini sa 8 elemento array
3) ug mobalhin sa sunod nga elemento sa laray diin imong gikuha ang pinakagamay nga elemento
ug balika ang 1,2,3 hangtod maabot nimo ang kataposang elemento sa usa sa mga arrays.
Dayon imong kuhaon ang nahabilin nga mga elemento sa laing laray aron ibutang kini sa usa ka 8 elemento nga laray.

Kini molihok tungod kay ang duha nga 4-element arrays gisunod ug busa dili na kinahanglan nga "mobalik" sa mga arrays.

Karon nga nasabtan na nato ang lansis, ania ang akong pseudocode para sa paghiusa:

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;

Ang merge sort nagbungkag sa usa ka problema ngadto sa mas gagmay nga mga problema ug dayon makit-an ang mga resulta sa gagmay nga mga problema aron makuha ang resulta sa orihinal nga problema (timan-i: kini nga matang sa algorithm gitawag nga divide and conquer). Kung dili nimo masabtan kini nga algorithm, ayaw kabalaka; Wala ko kasabot sa una nakong nakita. Kung makatabang kini kanimo, nakita nako kini nga algorithm ingon usa ka duha ka hugna nga algorithm:

Division phase, diin ang array gibahin ngadto sa mas gagmay nga arrays
Ang yugto sa paghan-ay kung diin ang gagmay nga mga arrays gihiusa (gamit ang unyon) aron maporma ang usa ka mas dako nga array.

Dibisyon nga hugna

Sa yugto sa dibisyon, ang array gibahin sa unitary arrays sa 3 nga mga lakang. Ang pormal nga gidaghanon sa mga lakang mao ang log(N) (tungod kay N=8, log(N) = 3).

Giunsa ko kini nahibal-an?

Genius ko! Sa usa ka pulong - matematika. Ang ideya mao nga ang matag lakang magbahin sa gidak-on sa orihinal nga laray sa 2. Ang gidaghanon sa mga lakang mao ang gidaghanon sa mga higayon nga imong mabahin ang orihinal nga laray sa duha. Kini ang eksaktong kahulugan sa usa ka logarithm (base 2).

Yugto sa paghan-ay

Sa yugto sa paghan-ay, magsugod ka sa unitary (single-element) arrays. Sa matag lakang imong magamit ang daghang mga operasyon sa paghiusa ug ang kinatibuk-ang gasto mao ang N = 8 nga mga operasyon:

Sa unang yugto ikaw adunay 4 nga paghiusa nga nagkantidad ug 2 ka operasyon matag usa
Sa ikaduhang lakang aduna kay 2 ka paghiusa nga nagkantidad ug 4 ka operasyon matag usa
Sa ikatulong lakang aduna kay 1 merge nga nagkantidad ug 8 ka operasyon

Tungod kay adunay mga log(N) nga mga lakang, kinatibuk-ang gasto N * log(N) nga mga operasyon.

Mga bentaha sa merge sort

Ngano nga kini nga algorithm kusog kaayo?

Tungod kay:

Mahimo nimo kini usbon aron makunhuran ang memory footprint aron dili ka makahimo og bag-ong mga arrays apan direkta nga usbon ang input array.

Hinumdomi: kini nga matang sa algorithm gitawag in-dapit (paghan-ay nga walay dugang nga memorya).

Mahimo nimo kini usbon aron magamit ang espasyo sa disk ug gamay nga memorya sa parehas nga oras nga wala’y hinungdan nga overhead sa disk I/O. Ang ideya mao ang pag-load sa memorya lamang sa mga bahin nga giproseso karon. Importante kini kung kinahanglan nimo nga paghan-ay ang usa ka multi-gigabyte nga lamesa nga adunay 100-megabyte nga memory buffer lamang.

Hinumdomi: kini nga matang sa algorithm gitawag gawas nga paghan-ay.

Mahimo nimo kini usbon aron modagan sa daghang mga proseso / thread / server.

Pananglitan, ang giapod-apod nga merge sort usa sa mga hinungdan nga sangkap Hadoop (nga usa ka istruktura sa dagkong datos).

Kini nga algorithm makahimo sa tingga ngadto sa bulawan (tinuod!).

Kini nga algorithm sa paghan-ay gigamit sa kadaghanan (kung dili tanan) nga mga database, apan dili kini usa ra. Kung gusto nimo mahibal-an ang dugang, mahimo nimong basahon kini trabaho sa panukiduki, nga naghisgot sa mga bentaha ug disbentaha sa komon nga database sorting algorithms.

Array, Kahoy ug Hash Table

Karon nga nahibal-an namon ang ideya sa pagkakomplikado sa oras ug pagsunud, kinahanglan nako isulti kanimo ang bahin sa 3 nga mga istruktura sa datos. Importante kini tungod kay sila mao ang basehan sa modernong mga database. Ipaila usab nako ang konsepto indeks sa database.

Array

Ang duha ka dimensyon nga array mao ang pinakasimple nga istruktura sa datos. Ang usa ka lamesa mahimong isipon nga usa ka laray. Pananglitan:

Kining 2-dimensional nga array kay usa ka lamesa nga adunay mga row ug column:

Ang matag linya nagrepresentar sa usa ka entidad
Ang mga column nagtipig sa mga kabtangan nga naghulagway sa entidad.
Ang matag kolum nagtipig sa datos sa usa ka piho nga tipo (integer, string, petsa...).

Kombenyente kini alang sa pagtipig ug paghanduraw sa datos, bisan pa, kung kinahanglan nimo pangitaon ang usa ka piho nga kantidad, dili kini angay.

Pananglitan, kung gusto nimo pangitaon ang tanan nga mga lalaki nga nagtrabaho sa UK, kinahanglan nimo nga tan-awon ang matag laray aron mahibal-an kung kana nga linya iya sa UK. Magasto ka sa N nga mga transaksyondiin N - gidaghanon sa mga linya, nga dili daotan, apan mahimo bang adunay mas paspas nga paagi? Karon na ang panahon nga atong ilhon ang mga kahoy.

Mubo nga sulat: Kadaghanan sa modernong mga database naghatag ug pinalawig nga mga han-ay alang sa pagtipig sa mga lamesa nga episyente: heap-organizedtables ug index-organizedtables. Apan wala kini mag-usab sa problema sa dali nga pagpangita sa usa ka piho nga kondisyon sa usa ka grupo sa mga kolum.

Database tree ug index

Ang binary search tree usa ka binary tree nga adunay espesyal nga kabtangan, ang yawe sa matag node kinahanglan nga:

mas dako kay sa tanang yawe nga gitipigan sa wala nga subtree
ubos sa tanang yawe nga gitipigan sa hustong subtree

Atong tan-awon kung unsa ang gipasabut niini nga makita

Ideya

Kini nga kahoy adunay N = 15 nga mga elemento. Ingnon ta nga nangita ko sa 208:

Nagsugod ko sa gamut kansang yawe kay 136. Sukad sa 136<208, tan-awon nako ang tuo nga subtree sa node 136.
398> 208 busa akong gitan-aw ang wala nga subtree sa node 398
250> 208 busa akong gitan-aw ang wala nga subtree sa node 250
200<208, busa akong gitan-aw ang tuo nga subtree sa node 200. Apan ang 200 walay hustong subtree, walay bili (kay kung kini anaa, kini anaa sa husto nga subtree 200).

Karon ingnon ta nga nangita kog 40

Nagsugod ko sa gamut kansang yawe mao ang 136. Sukad sa 136 > 40, akong gitan-aw ang wala nga subtree sa node 136.
80> 40, busa akong gitan-aw ang wala nga subtree sa node 80
40= 40, node anaa. Gikuha nako ang row ID sulod sa node (wala gipakita sa hulagway) ug tan-awa sa lamesa ang gihatag nga row ID.
Ang pagkahibalo sa row ID nagtugot kanako nga mahibal-an kung asa ang datos sa lamesa, aron makuha nako kini dayon.

Sa katapusan, ang duha nga pagpangita gasto kanako sa gidaghanon sa mga lebel sa sulod sa kahoy. Kung gibasa nimo pag-ayo ang bahin bahin sa paghiusa, kinahanglan nimo nga makita nga adunay mga lebel sa log(N). Kini nahimo, log sa gasto sa pagpangita(N), dili daotan!

Balik ta sa atong problema

But this is very abstract, so balik ta sa atong problema. Imbis usa ka yano nga integer, hunahunaa ang usa ka hilo nga nagrepresentar sa nasud sa usa ka tawo sa miaging lamesa. Ingnon ta nga ikaw adunay usa ka kahoy nga naglangkob sa "nasud" nga uma (kolum 3) sa lamesa:

Kung gusto nimo mahibal-an kung kinsa ang nagtrabaho sa UK
imong tan-awon ang kahoy aron makuha ang node nga nagrepresentar sa Great Britain
sulod sa "UKnode" makit-an nimo ang lokasyon sa mga rekord sa trabahante sa UK.

Kini nga pagpangita mogasto sa log(N) nga mga operasyon imbes sa N nga mga operasyon kung gamiton nimo ang array direkta. Ang imong gipresentar mao indeks sa database.

Mahimo kang magtukod ug index tree para sa bisan unsang grupo sa mga field (string, number, 2 lines, number ug string, date...) basta duna kay function sa pagtandi sa mga yawe (ie field groups) aron imong ma-set. han-ay taliwala sa mga yawe (nga mao ang kaso sa bisan unsang sukaranan nga mga tipo sa database).

B+TreeIndex

Samtang kini nga kahoy maayo alang sa pagkuha sa usa ka piho nga kantidad, adunay usa ka DAKO nga problema kung kinahanglan nimo pagkuha daghang mga elemento tali sa duha nga mga kantidad. Magasto kini sa O(N) tungod kay kinahanglan nimong tan-awon ang matag node sa kahoy ug susihon kung naa ba kini taliwala sa duha nga mga kantidad (pananglitan sa usa ka gimando nga pag-agi sa kahoy). Dugang pa, kini nga operasyon dili mahigalaon sa disk I / O tungod kay kinahanglan nimo nga basahon ang tibuuk nga kahoy. Kinahanglan namon nga mangita usa ka paagi aron epektibo nga ipatuman hangyo sa range. Aron masulbad kini nga problema, ang modernong mga database naggamit sa usa ka giusab nga bersyon sa miaging kahoy nga gitawag og B+Tree. Sa usa ka B+Tree nga kahoy:

lamang ang pinakaubos nga mga buko (mga dahon) tindahan sa impormasyon (lokasyon sa mga laray sa may kalabutan nga lamesa)
ang nahabilin nga mga node ania dinhi alang sa routing sa husto nga node atol sa pagpangita.

Sama sa imong nakita, adunay daghang mga node dinhi (kaduha). Sa tinuud, adunay ka dugang nga mga node, "mga node sa desisyon", nga makatabang kanimo sa pagpangita sa husto nga node (nga nagtipig sa lokasyon sa mga linya sa kauban nga lamesa). Apan ang pagkakomplikado sa pagpangita kay O(log(N)) (adunay usa pa ka lebel). Ang dakong kalainan mao kana Ang mga node sa ubos nga lebel konektado sa ilang mga manununod.

Uban niini nga B+Tree, kung nangita ka mga kantidad tali sa 40 ug 100:

Kinahanglan ra nimo pangitaon ang 40 (o ang labing duol nga kantidad pagkahuman sa 40 kung wala ang 40) sama sa imong gibuhat sa miaging kahoy.
Unya kolektaha ang 40 ka manununod gamit ang direktang mga link sa manununod hangtod makaabot ka sa 100.

Ingnon ta nga nakit-an nimo ang M nga mga manununod ug ang kahoy adunay N node. Ang pagpangita sa usa ka piho nga node gasto log (N) sama sa miaging kahoy. Apan kung makuha nimo kini nga node, makuha nimo ang mga manununod sa M sa mga operasyon nga adunay mga pakisayran sa ilang mga manununod. Kini nga pagpangita nagkantidad lamang og M+log(N) operasyon kumpara sa N nga operasyon sa miaging kahoy. Dugang pa, dili nimo kinahanglan nga basahon ang tibuuk nga punoan (mga M + log (N) node lamang), nga nagpasabut nga dili kaayo paggamit sa disk. Kung ang M gamay (eg 200 ka laray) ug ang N dako (1 ka laray), adunay dako nga kalainan.

Apan adunay bag-ong mga problema dinhi (pag-usab!). Kung magdugang ka o magtangtang sa usa ka laray sa database (ug busa sa kaubang B+Tree index):

kinahanglan nimo nga ipadayon ang kahusay tali sa mga buko sa sulod sa usa ka B+Tree, kung dili dili nimo makit-an ang mga buko sa sulod sa usa ka wala masunud nga kahoy.
kinahanglan nimo nga tipigan ang minimum nga posible nga gidaghanon sa lebel sa B+Tree, kung dili ang O(log(N)) nga pagkakomplikado sa oras mahimong O(N).

Sa laing pagkasulti, ang B+Tree kinahanglan nga mag-order sa kaugalingon ug balanse. Suwerte, posible kini sa mga smart delete ug insert nga mga operasyon. Apan kini moabut sa usa ka gasto: pagsal-ot ug pagtangtang sa usa ka B+ nga kahoy gasto O(log(N)). Mao nga ang uban kaninyo nakadungog niana Ang paggamit sa daghang mga indeks dili maayong ideya. tinuod, gipahinay nimo ang paspas nga pagsulod/pag-update/pagtangtang sa usa ka laray sa usa ka lamesatungod kay ang database kinahanglan nga i-update ang mga indeks sa lamesa gamit ang usa ka mahal nga O (log (N)) nga operasyon alang sa matag indeks. Dugang pa, ang pagdugang sa mga indeks nagpasabut nga daghang trabaho alang sa manager sa transaksyon (ihulagway sa katapusan sa artikulo).

Alang sa dugang nga mga detalye, imong makita ang artikulo sa Wikipedia sa B+Kahoy. Kung gusto nimo ang usa ka pananglitan sa pagpatuman sa B+Tree sa usa ka database, tan-awa kini nga artikulo и kini nga artikulo gikan sa usa ka nag-unang MySQL developer. Pareho silang nagpunting kung giunsa pagdumala sa InnoDB (ang MySQL engine) ang mga indeks.

Mubo nga sulat: Gisultihan ako sa usa ka magbabasa nga, tungod sa ubos nga lebel sa pag-optimize, ang B+ nga kahoy kinahanglan nga hingpit nga balanse.

Hashtable

Ang among katapusang importante nga istruktura sa datos mao ang hash table. Kini mapuslanon kaayo kung gusto nimo nga dali nga mangita sa mga kantidad. Dugang pa, ang pagsabut sa usa ka hash table makatabang kanato sa ulahi nga masabtan ang usa ka komon nga database join operation nga gitawag ug hash join ( hash apil). Kini nga istruktura sa datos gigamit usab sa database sa pagtipig sa pipila ka mga internal nga butang (eg. lock nga lamesa o buffer pool, atong makita ang duha niini nga mga konsepto sa ulahi).

Ang hash table usa ka istruktura sa datos nga dali nga makit-an ang usa ka elemento pinaagi sa yawe niini. Aron makahimo og hash table kinahanglan nimo nga ipasabut:

ключ alang sa imong mga elemento
hash function alang sa mga yawe. Ang computed key hash naghatag sa lokasyon sa mga elemento (gitawag mga bahin ).
function alang sa pagtandi sa mga yawe. Kung nakit-an na nimo ang husto nga bahin, kinahanglan nimo nga makit-an ang elemento nga imong gipangita sa sulod sa bahin gamit kini nga pagtandi.

Simple nga pananglitan

Atong kuhaon ang usa ka tin-aw nga pananglitan:

Kini nga hash table adunay 10 ka bahin. Kay lage ko 5 segment ra akong gi picture pero kabalo ko nga smart ka, mao to ako ra gyung ipa picture sa imoha ang laing 5. Gigamit nako ang usa ka hash function modulo 10 sa yawe. Sa laing pagkasulti, akong gitipigan lamang ang katapusang digit sa yawe sa elemento aron makit-an ang bahin niini:

kung ang katapusan nga digit mao ang 0, ang elemento mahulog sa bahin 0,
kung ang katapusan nga digit mao ang 1, ang elemento mahulog sa bahin 1,
kung ang katapusang digit mao ang 2, ang elemento mahulog sa lugar 2,
...

Ang function sa pagtandi nga akong gigamit mao ang pagkaparehas tali sa duha nga integer.

Ingnon ta nga gusto nimo makuha ang elemento 78:

Ang hash table nagkalkula sa hash code alang sa 78, nga mao ang 8.
Ang hash table nagtan-aw sa bahin 8, ug ang unang elemento nga nakit-an niini mao ang 78.
Giuli niya kanimo ang aytem 78
Ang pagpangita gasto lamang sa 2 nga mga operasyon (usa aron makalkulo ang hash nga kantidad ug ang usa aron pangitaon ang elemento sulod sa bahin).

Karon ingnon ta nga gusto nimo makuha ang elemento 59:

Ang hash table nagkalkula sa hash code alang sa 59, nga mao ang 9.
Ang hash table nangita sa bahin 9, ang unang elemento nga nakit-an mao ang 99. Tungod kay 99!=59, ang elemento 99 dili balido nga elemento.
Gamit ang parehas nga lohika, ang ikaduha nga elemento (9), ang ikatulo (79), ..., ang katapusan (29) gikuha.
Ang elemento wala makit-an.
Ang pagpangita nagkantidad ug 7 ka operasyon.

Maayo nga hash function

Sama sa imong nakita, depende sa kantidad nga imong gipangita, ang gasto dili parehas!

Kung akong usbon karon ang hash function modulo 1 sa yawe (nga mao, pagkuha sa katapusan nga 000 nga numero), ang ikaduha nga pagpangita nagkantidad lang og 000 nga operasyon tungod kay wala’y elemento sa bahin 6. Ang tinuod nga hagit mao ang pagpangita sa usa ka maayo nga hash function nga maghimo og mga balde nga adunay gamay nga gidaghanon sa mga elemento.

Sa akong pananglitan, ang pagpangita og maayo nga hash function sayon. Apan kini usa ka yano nga pananglitan, ang pagpangita sa usa ka maayo nga hash function mas lisud kung ang yawe mao ang:

string (pananglitan - apelyido)
2 linya (pananglitan - apelyido ug una nga ngalan)
2 linya ug petsa (pananglitan - apelyido, ngalan ug petsa sa pagkatawo)
...

Uban sa usa ka maayo nga hash function, hash table lookups gasto O(1).

Array vs hash nga lamesa

Nganong dili mogamit ug array?

Hmm, maayong pangutana.

Ang hash nga lamesa mahimong partially loaded sa memorya, ug ang nahabilin nga mga bahin mahimong magpabilin sa disk.
Uban sa usa ka array kinahanglan nimo nga gamiton ang magkadugtong nga luna sa memorya. Kung nagkarga ka ug dako nga lamesa lisud kaayo ang pagpangita og igo nga padayon nga luna.
Alang sa hash table, mahimo nimong pilion ang yawe nga imong gusto (pananglitan, nasud ug apelyido sa tawo).

Alang sa dugang nga kasayuran, mahimo nimong basahon ang artikulo bahin sa JavaHashMap, nga usa ka episyente nga pagpatuman sa usa ka hash table; dili nimo kinahanglan nga masabtan ang Java aron masabtan ang mga konsepto nga nasakup niini nga artikulo.

Source: www.habr.com

Giunsa Pagtrabaho ang Relational Database (Bahin 1)