Hello, Habr! Ipinakita ko sa iyong pansin ang isang pagsasalin ng artikulo
"Paano gumagana ang isang relational database".

Pagdating sa mga relational database hindi ko maiwasang isipin na may kulang. Ginagamit ang mga ito sa lahat ng dako. Mayroong maraming iba't ibang mga database na magagamit, mula sa maliit at kapaki-pakinabang na SQLite hanggang sa makapangyarihang Teradata. Ngunit may ilang mga artikulo lamang na nagpapaliwanag kung paano gumagana ang database. Maaari kang maghanap para sa iyong sarili gamit ang "howdoesarelationaldatabasework" upang makita kung gaano kaunti ang mga resulta. Bukod dito, ang mga artikulong ito ay maikli. Kung naghahanap ka ng mga pinakabagong buzzy na teknolohiya (BigData, NoSQL o JavaScript), makakahanap ka ng mas malalalim na artikulo na nagpapaliwanag kung paano gumagana ang mga ito.

Ang mga relational database ba ay masyadong luma at masyadong boring para ipaliwanag sa labas ng mga kurso sa unibersidad, research paper at libro?

Bilang isang developer, ayaw kong gumamit ng isang bagay na hindi ko maintindihan. At kung ang mga database ay ginamit nang higit sa 40 taon, dapat mayroong dahilan. Sa paglipas ng mga taon, gumugol ako ng daan-daang oras upang tunay na maunawaan ang mga kakaibang black box na ito na ginagamit ko araw-araw. Mga database ng relasyon very interesting kasi sila batay sa kapaki-pakinabang at magagamit muli na mga konsepto. Kung ikaw ay interesado sa pag-unawa sa isang database, ngunit hindi kailanman nagkaroon ng oras o pagkahilig upang bungkalin ang malawak na paksang ito, dapat mong tangkilikin ang artikulong ito.

Bagama't tahasan ang pamagat ng artikulong ito, ang layunin ng artikulong ito ay hindi upang maunawaan kung paano gamitin ang database. Samakatuwid dapat alam mo na kung paano magsulat ng isang simpleng kahilingan sa koneksyon at mga pangunahing query RAW; kung hindi, maaaring hindi mo maintindihan ang artikulong ito. Iyon lang ang kailangan mong malaman, ipapaliwanag ko ang iba.

Magsisimula ako sa ilang mga pangunahing kaalaman sa computer science, tulad ng pagiging kumplikado ng oras ng mga algorithm (BigO). Alam kong ang ilan sa inyo ay napopoot sa konseptong ito, ngunit kung wala ito ay hindi mo mauunawaan ang mga intricacies sa loob ng database. Dahil ito ay isang malaking paksa, Pagtutuunan ko ng pansin ang sa tingin ko ay mahalaga: kung paano nagpoproseso ang database SQL pagtatanong. magpapakilala lang ako pangunahing mga konsepto ng databaseupang sa dulo ng artikulo ay mayroon kang ideya kung ano ang nangyayari sa ilalim ng talukbong.

Dahil isa itong mahaba at teknikal na artikulo na nagsasangkot ng maraming algorithm at istruktura ng data, maglaan ng oras upang basahin ito. Ang ilang mga konsepto ay maaaring mahirap maunawaan; maaari mong laktawan ang mga ito at makuha pa rin ang pangkalahatang ideya.

Para sa higit na nakakaalam sa inyo, ang artikulong ito ay nahahati sa 3 bahagi:

Pangkalahatang-ideya ng mababang antas at mataas na antas ng mga bahagi ng database
Pangkalahatang-ideya ng Proseso ng Pag-optimize ng Query
Pangkalahatang-ideya ng Pamamahala ng Transaksyon at Buffer Pool

Balik sa simula

Ilang taon na ang nakalilipas (sa isang kalawakan na malayo, malayo...), kailangang malaman ng mga developer ang eksaktong bilang ng mga operasyon na kanilang ini-coding. Alam nila sa puso ang kanilang mga algorithm at istruktura ng data dahil hindi nila kayang sayangin ang CPU at memorya ng kanilang mabagal na mga computer.

Sa bahaging ito, ipapaalala ko sa iyo ang ilan sa mga konseptong ito dahil mahalaga ang mga ito sa pag-unawa sa database. Ipapakilala ko rin ang konsepto index ng database.

O(1) vs O(n2)

Sa ngayon, maraming developer ang walang pakialam sa pagiging kumplikado ng oras ng mga algorithm... at tama sila!

Ngunit kapag nakikitungo ka sa maraming data (hindi ako nagsasalita ng libu-libo) o kung nahihirapan ka sa mga millisecond, nagiging kritikal na maunawaan ang konseptong ito. At gaya ng maiisip mo, kailangang harapin ng mga database ang parehong sitwasyon! Hindi kita gugugol ng mas maraming oras kaysa sa kinakailangan para maiparating ang punto. Makakatulong ito sa amin na maunawaan ang konsepto ng cost-based optimization mamaya (gastos batay optimization).

Pagkaunawa

Ang pagiging kumplikado ng oras ng algorithm ginagamit upang makita kung gaano katagal bago magsagawa ng algorithm para sa isang partikular na dami ng data. Upang ilarawan ang pagiging kumplikado, gumagamit kami ng malaking O mathematical notation. Ginagamit ang notation na ito kasama ng isang function na naglalarawan kung gaano karaming mga operasyon ang kailangan ng isang algorithm para sa isang naibigay na bilang ng mga input.

Halimbawa, kapag sinabi kong "ang algorithm na ito ay may kumplikado O(some_function())", nangangahulugan ito na ang algorithm ay nangangailangan ng ilang_function(a_certain_amount_of_data) na mga operasyon upang maproseso ang isang tiyak na halaga ng data.

Sa kasong ito, Hindi ang dami ng data ang mahalaga**, kung hindi ** kung paano tumataas ang bilang ng mga operasyon sa pagtaas ng dami ng data. Ang pagiging kumplikado ng oras ay hindi nagbibigay ng eksaktong bilang ng mga operasyon, ngunit ito ay isang mahusay na paraan upang matantya ang oras ng pagpapatupad.

Sa graph na ito makikita mo ang bilang ng mga operasyon kumpara sa dami ng data ng pag-input para sa iba't ibang uri ng mga kumplikadong oras ng algorithm. Gumamit ako ng logarithmic scale upang ipakita ang mga ito. Sa madaling salita, mabilis na tumataas ang dami ng data mula 1 hanggang 1 bilyon. Makikita natin na:

Ang O(1) o pare-pareho ang pagiging kumplikado ay nananatiling pare-pareho (kung hindi, ito ay hindi matatawag na pare-pareho ang pagiging kumplikado).
O(mag-log(n)) nananatiling mababa kahit na may bilyun-bilyong data.
Pinakamahirap na kahirapan - O(n2), kung saan mabilis na lumalaki ang bilang ng mga operasyon.
Ang iba pang dalawang komplikasyon ay mabilis na tumataas.

Mga halimbawa

Sa isang maliit na halaga ng data, ang pagkakaiba sa pagitan ng O(1) at O(n2) ay bale-wala. Halimbawa, sabihin nating mayroon kang algorithm na kailangang magproseso ng 2000 elemento.

Ang O(1) algorithm ay gagastos sa iyo ng 1 operasyon
Ang O(log(n)) algorithm ay gagastos sa iyo ng 7 operasyon
Ang O(n) algorithm ay gagastos sa iyo ng 2 na operasyon
Ang O(n*log(n)) algorithm ay gagastos sa iyo ng 14 na operasyon
Ang O(n2) algorithm ay gagastos sa iyo ng 4 na operasyon

Ang pagkakaiba sa pagitan ng O(1) at O(n2) ay tila malaki (4 na milyong operasyon) ngunit mawawalan ka ng maximum na 2 ms, oras lamang upang kumurap ang iyong mga mata. Sa katunayan, ang mga modernong processor ay maaaring magproseso daan-daang milyong mga operasyon bawat segundo. Ito ang dahilan kung bakit ang pagganap at pag-optimize ay hindi isang isyu sa maraming mga proyekto sa IT.

Tulad ng sinabi ko, mahalaga pa ring malaman ang konseptong ito kapag nagtatrabaho sa malaking halaga ng data. Kung sa pagkakataong ito ang algorithm ay kailangang magproseso ng 1 elemento (na hindi ganoon karami para sa isang database):

Ang O(1) algorithm ay gagastos sa iyo ng 1 operasyon
Ang O(log(n)) algorithm ay gagastos sa iyo ng 14 operasyon
Ang O(n) algorithm ay gagastos sa iyo ng 1 na operasyon
Ang O(n*log(n)) algorithm ay gagastos sa iyo ng 14 na operasyon
Ang O(n2) algorithm ay gagastos sa iyo ng 1 na operasyon

Hindi ko pa nagawa ang matematika, ngunit sasabihin ko na sa O(n2) algorithm mayroon kang oras para uminom ng kape (kahit dalawa!). Kung magdaragdag ka ng isa pang 0 sa dami ng data, magkakaroon ka ng oras upang umidlip.

Palalimin pa natin

Para sa iyong impormasyon:

Ang isang magandang hash table lookup ay nakakahanap ng elemento sa O(1).
Ang paghahanap sa isang mahusay na balanseng puno ay nagbubunga ng mga resulta sa O(log(n)).
Ang paghahanap sa isang array ay nagbubunga ng mga resulta sa O(n).
Ang pinakamahusay na mga algorithm ng pag-uuri ay may pagiging kumplikado O(n*log(n)).
Ang isang masamang algorithm sa pag-uuri ay may pagiging kumplikado O(n2).

Tandaan: Sa mga sumusunod na bahagi makikita natin ang mga algorithm at istruktura ng data na ito.

Mayroong ilang mga uri ng pagiging kumplikado ng oras ng algorithm:

karaniwang senaryo ng kaso
pinakamahusay na senaryo ng kaso
at worst case scenario

Ang pagiging kumplikado ng oras ay madalas na ang pinakamasamang sitwasyon.

Pinag-uusapan ko lang ang pagiging kumplikado ng oras ng algorithm, ngunit nalalapat din ang pagiging kumplikado sa:

pagkonsumo ng memorya ng algorithm
algorithm ng pagkonsumo ng disk I/O

Siyempre, may mga komplikasyon na mas malala kaysa sa n2, halimbawa:

n4: grabe naman! Ang ilan sa mga nabanggit na algorithm ay may ganitong kumplikado.
3n: ito ay mas masahol pa! Ang isa sa mga algorithm na makikita natin sa gitna ng artikulong ito ay may ganitong kumplikado (at ito ay aktwal na ginagamit sa maraming mga database).
factorial n: hindi mo makukuha ang iyong mga resulta kahit na may maliit na halaga ng data.
nn: Kung nakatagpo ka ng ganitong kumplikado, dapat mong tanungin ang iyong sarili kung ito ba talaga ang iyong larangan ng aktibidad...

Tandaan: Hindi ko ibinigay sa iyo ang aktwal na kahulugan ng malaking O pagtatalaga, isang ideya lamang. Mababasa mo ang artikulong ito sa Wikipedia para sa tunay na (asymptotic) na kahulugan.

Sumanib-uuri

Ano ang gagawin mo kapag kailangan mong pagbukud-bukurin ang isang koleksyon? Ano? Tinatawag mo ang sort() function... Ok, magandang sagot... Ngunit para sa isang database, dapat mong maunawaan kung paano gumagana ang sort() function na ito.

Mayroong ilang mga mahusay na algorithm sa pag-uuri, kaya't tututok ako sa pinakamahalaga: sumanib-uuri. Maaaring hindi mo maintindihan kung bakit kapaki-pakinabang ang pag-uuri ng data sa ngayon, ngunit dapat mong matapos ang bahagi ng pag-optimize ng query. Bukod dito, ang pag-unawa sa pag-uuri ng merge ay makakatulong sa amin sa ibang pagkakataon na maunawaan ang karaniwang tinatawag na operasyon ng pagsali sa database pagsamahin sumali (samahan ng pagsasanib).

Pagsamahin

Tulad ng maraming kapaki-pakinabang na algorithm, umaasa ang merge sort sa isang trick: ang pagsasama-sama ng 2 pinagsunod-sunod na array ng laki N/2 sa isang N-element sorted array ay nagkakahalaga lamang ng N operations. Ang operasyong ito ay tinatawag na pagsasama.

Tingnan natin kung ano ang ibig sabihin nito sa isang simpleng halimbawa:

Ipinapakita ng figure na ito na para mabuo ang pinal na pinagsunod-sunod na 8-element array, kailangan mo lang umulit nang isang beses sa 2 4 na elementong array. Dahil ang parehong 4-element arrays ay nakaayos na:

1) inihambing mo ang parehong kasalukuyang mga elemento sa dalawang array (sa simula kasalukuyang = una)
2) pagkatapos ay kunin ang pinakamaliit upang ilagay ito sa isang 8 elemento array
3) at lumipat sa susunod na elemento sa array kung saan mo kinuha ang pinakamaliit na elemento
at ulitin ang 1,2,3 hanggang sa maabot mo ang huling elemento ng isa sa mga array.
Pagkatapos ay kukunin mo ang natitirang mga elemento ng isa pang array upang ilagay ang mga ito sa isang 8 elemento array.

Gumagana ito dahil ang parehong 4-element na array ay pinagsunod-sunod at kaya hindi mo na kailangang "bumalik" sa mga array na iyon.

Ngayon na naiintindihan na natin ang trick, narito ang aking pseudocode para sa pagsasama:

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;

Pinaghihiwa-hiwalay ng merge sort ang isang problema sa mas maliliit na problema at pagkatapos ay hahanapin ang mga resulta ng mas maliliit na problema para makuha ang resulta ng orihinal na problema (tandaan: ang ganitong uri ng algorithm ay tinatawag na divide and conquer). Kung hindi mo naiintindihan ang algorithm na ito, huwag mag-alala; Hindi ko naintindihan nung una kong nakita. Kung makakatulong ito sa iyo, nakikita ko ang algorithm na ito bilang isang two-phase algorithm:

Division phase, kung saan ang array ay nahahati sa mas maliliit na arrays
Ang yugto ng pag-uuri ay kung saan pinagsama ang maliliit na array (gamit ang unyon) upang bumuo ng mas malaking array.

Yugto ng dibisyon

Sa yugto ng paghahati, ang array ay nahahati sa unitary array sa 3 hakbang. Ang pormal na bilang ng mga hakbang ay log(N) (dahil N=8, log(N) = 3).

Paano ko malalaman ito?

Ako ay henyo! Sa isang salita - matematika. Ang ideya ay ang bawat hakbang ay hinahati ang laki ng orihinal na array sa pamamagitan ng 2. Ang bilang ng mga hakbang ay ang bilang ng beses na maaari mong hatiin ang orihinal na array sa dalawa. Ito ang eksaktong kahulugan ng logarithm (base 2).

Yugto ng pag-uuri

Sa yugto ng pag-uuri, magsisimula ka sa mga unitary (iisang elemento) na array. Sa bawat hakbang, naglalapat ka ng maramihang pagpapatakbo ng pagsasanib at ang kabuuang gastos ay N = 8 na pagpapatakbo:

Sa unang yugto mayroon kang 4 na pagsasanib na nagkakahalaga ng 2 operasyon bawat isa
Sa pangalawang hakbang mayroon kang 2 merge na nagkakahalaga ng 4 na operasyon bawat isa
Sa ikatlong hakbang mayroon kang 1 merge na nagkakahalaga ng 8 operasyon

Dahil may mga log(N) na hakbang, kabuuang gastos N * mga operasyon ng log(N)..

Mga kalamangan ng merge sort

Bakit napakalakas ng algorithm na ito?

dahil:

Maaari mo itong baguhin upang bawasan ang memory footprint upang hindi ka lumikha ng mga bagong array ngunit direktang baguhin ang input array.

Tandaan: ang ganitong uri ng algorithm ay tinatawag in-lugar (pag-uuri nang walang karagdagang memorya).

Maaari mo itong baguhin upang gumamit ng espasyo sa disk at isang maliit na halaga ng memory sa parehong oras nang hindi nagkakaroon ng malaking disk I/O overhead. Ang ideya ay i-load sa memorya lamang ang mga bahaging kasalukuyang pinoproseso. Mahalaga ito kapag kailangan mong pag-uri-uriin ang isang multi-gigabyte na talahanayan na may 100-megabyte na memory buffer lamang.

Tandaan: ang ganitong uri ng algorithm ay tinatawag panlabas na uri.

Maaari mong baguhin ito upang tumakbo sa maraming proseso/mga thread/server.

Halimbawa, ang distributed merge sort ay isa sa mga pangunahing bahagi Hadoop (na isang istraktura sa malaking data).

Ang algorithm na ito ay maaaring gawing ginto ang tingga (talaga!).

Ang algorithm ng pag-uuri na ito ay ginagamit sa karamihan (kung hindi lahat) na database, ngunit hindi lang ito. Kung gusto mong malaman ang higit pa, maaari mong basahin ito gawaing pananaliksik, na tumatalakay sa mga kalamangan at kahinaan ng karaniwang mga algorithm sa pag-uuri ng database.

Array, Puno at Hash Table

Ngayon na naiintindihan namin ang ideya ng pagiging kumplikado at pag-uuri ng oras, dapat kong sabihin sa iyo ang tungkol sa 3 mga istruktura ng data. Mahalaga ito dahil sila ay ang batayan ng mga modernong database. Ipapakilala ko rin ang konsepto index ng database.

Array

Ang isang two-dimensional array ay ang pinakasimpleng istraktura ng data. Ang isang talahanayan ay maaaring isipin bilang isang array. Halimbawa:

Ang 2-dimensional na array na ito ay isang table na may mga row at column:

Ang bawat linya ay kumakatawan sa isang entity
Nag-iimbak ang mga column ng mga property na naglalarawan sa entity.
Ang bawat column ay nag-iimbak ng data ng isang partikular na uri (integer, string, petsa...).

Maginhawa ito para sa pag-iimbak at pag-visualize ng data, gayunpaman, kapag kailangan mong makahanap ng isang partikular na halaga, hindi ito angkop.

Halimbawa, kung gusto mong mahanap ang lahat ng lalaking nagtatrabaho sa UK, kakailanganin mong tingnan ang bawat row para matukoy kung ang row na iyon ay kabilang sa UK. Aabutin ka nito ng N transaksyonSaan N - bilang ng mga linya, na hindi masama, ngunit maaaring mayroong mas mabilis na paraan? Ngayon ay oras na para makilala natin ang mga puno.

Tandaan: Karamihan sa mga modernong database ay nagbibigay ng mga pinahabang array para sa mahusay na pag-iimbak ng mga talahanayan: heap-organizedtables at index-organizedtables. Ngunit hindi nito binabago ang problema ng mabilis na paghahanap ng isang partikular na kondisyon sa isang pangkat ng mga haligi.

Database tree at index

Ang binary search tree ay isang binary tree na may espesyal na katangian, ang susi sa bawat node ay dapat na:

mas malaki kaysa sa lahat ng mga susi na nakaimbak sa kaliwang subtree
mas mababa sa lahat ng mga susi na nakaimbak sa tamang subtree

Tingnan natin kung ano ang ibig sabihin nito nang biswal

Idea

Ang punong ito ay may N = 15 elemento. Sabihin nating hinahanap ko ang 208:

Nagsisimula ako sa ugat na ang susi ay 136. Dahil 136<208, tinitingnan ko ang kanang subtree ng node 136.
398>208 samakatuwid tinitingnan ko ang kaliwang subtree ng node 398
250>208 samakatuwid tinitingnan ko ang kaliwang subtree ng node 250
200<208, samakatuwid tinitingnan ko ang tamang subtree ng node 200. Ngunit ang 200 ay walang tamang subtree, walang halaga (dahil kung ito ay umiiral, ito ay nasa tamang subtree 200).

Ngayon sabihin nating naghahanap ako ng 40

Nagsisimula ako sa ugat na ang susi ay 136. Dahil 136 > 40, tinitingnan ko ang kaliwang subtree ng node 136.
80 > 40, kaya tumitingin ako sa kaliwang subtree ng node 80
40= 40, umiiral ang node. Kinukuha ko ang row ID sa loob ng node (hindi ipinapakita sa larawan) at tumingin sa talahanayan para sa ibinigay na row ID.
Ang pag-alam sa row ID ay nagbibigay-daan sa akin na malaman kung nasaan ang data sa talahanayan, para makuha ko ito kaagad.

Sa huli, ang parehong mga paghahanap ay gagastos sa akin ng bilang ng mga antas sa loob ng puno. Kung babasahin mo nang mabuti ang bahagi tungkol sa pagsasama-sama, dapat mong makita na mayroong mga antas ng log(N). Iyon pala, log ng gastos sa paghahanap(N), hindi masama!

Balik tayo sa problema natin

Ngunit ito ay napaka-abstract, kaya bumalik tayo sa ating problema. Sa halip na isang simpleng integer, isipin ang isang string na kumakatawan sa bansa ng isang tao sa nakaraang talahanayan. Sabihin nating mayroon kang puno na naglalaman ng field na "bansa" (column 3) ng talahanayan:

Kung gusto mong malaman kung sino ang nagtatrabaho sa UK
tumingin ka sa puno upang makuha ang node na kumakatawan sa Great Britain
sa loob ng "UKnode" makikita mo ang lokasyon ng mga tala ng manggagawa sa UK.

Ang paghahanap na ito ay nagkakahalaga ng log(N) na mga operasyon sa halip na N na mga operasyon kung gagamitin mo ang array nang direkta. Ang ipinakita mo lang ay index ng database.

Maaari kang bumuo ng isang index tree para sa anumang pangkat ng mga field (string, numero, 2 linya, numero at string, petsa...) hangga't mayroon kang isang function upang ihambing ang mga key (ibig sabihin, mga pangkat ng field) upang maitakda mo pagkakasunud-sunod sa mga susi (na ang kaso para sa anumang mga pangunahing uri sa database).

B+TreeIndex

Bagama't mahusay na gumagana ang punong ito para sa pagkuha ng isang partikular na halaga, mayroong MALAKING problema kapag kailangan mo makakuha ng maraming elemento sa pagitan ng dalawang halaga. Magkakahalaga ito ng O(N) dahil kailangan mong tingnan ang bawat node sa tree at suriin kung ito ay nasa pagitan ng dalawang value na ito (hal. sa isang ordered traversal ng tree). Bukod dito, ang operasyong ito ay hindi disk I/O friendly dahil kailangan mong basahin ang buong puno. Kailangan nating maghanap ng paraan upang mahusay na maisagawa kahilingan sa saklaw. Upang malutas ang problemang ito, ang mga modernong database ay gumagamit ng isang binagong bersyon ng nakaraang puno na tinatawag na B+Tree. Sa isang B+Tree tree:

tanging ang pinakamababang node (mga dahon) mag-imbak ng impormasyon (lokasyon ng mga hilera sa kaugnay na talahanayan)
ang iba pang mga node ay narito para sa pagruruta sa tamang node habang naghahanap.

Tulad ng nakikita mo, mayroong higit pang mga node dito (dalawang beses). Sa katunayan, mayroon kang mga karagdagang node, "mga node ng desisyon", na makakatulong sa iyong mahanap ang tamang node (na nag-iimbak ng lokasyon ng mga hilera sa nauugnay na talahanayan). Ngunit ang pagiging kumplikado ng paghahanap ay O(log(N)) pa rin (may isa pang antas). Ang malaking pagkakaiba ay iyon ang mga node sa mas mababang antas ay konektado sa kanilang mga kahalili.

Sa B+Tree na ito, kung naghahanap ka ng mga halaga sa pagitan ng 40 at 100:

Kailangan mo lang maghanap ng 40 (o ang pinakamalapit na halaga pagkatapos ng 40 kung 40 ay hindi umiiral) tulad ng ginawa mo sa nakaraang puno.
Pagkatapos ay mangolekta ng 40 tagapagmana gamit ang mga direktang link ng tagapagmana hanggang sa maabot mo ang 100.

Sabihin nating nakahanap ka ng mga M na kahalili at ang puno ay may N node. Ang paghahanap ng isang partikular na node ay nagkakahalaga ng log(N) tulad ng nakaraang puno. Ngunit sa sandaling makuha mo ang node na ito, makakakuha ka ng mga M na kahalili sa mga operasyong M na may mga sanggunian sa kanilang mga kahalili. Ang paghahanap na ito ay nagkakahalaga lamang ng M+log(N) operasyon kumpara sa N operasyon sa nakaraang puno. Bukod dito, hindi mo kailangang basahin ang buong puno (mga M+log(N) node lamang), na nangangahulugang mas kaunting paggamit ng disk. Kung maliit ang M (hal. 200 row) at malaki ang N (1 row), magkakaroon ng MALAKING pagkakaiba.

Ngunit may mga bagong problema dito (muli!). Kung nagdagdag ka o nagtanggal ng isang row sa database (at samakatuwid ay nasa nauugnay na B+Tree index):

dapat mong mapanatili ang pagkakasunud-sunod sa pagitan ng mga node sa loob ng isang B+Tree, kung hindi, hindi mo mahahanap ang mga node sa loob ng isang unsorted tree.
dapat mong panatilihin ang pinakamababang posibleng bilang ng mga antas sa B+Tree, kung hindi, ang pagiging kumplikado ng oras ng O(log(N)) ay magiging O(N).

Sa madaling salita, dapat na self-ordering at balanse ang B+Tree. Sa kabutihang palad, posible ito sa matalinong pagtanggal at pagpasok ng mga operasyon. Ngunit ito ay may halaga: ang mga pagsingit at pagtanggal sa isang B+ tree ay nagkakahalaga ng O(log(N)). Kaya naman narinig na iyan ng ilan sa inyo ang paggamit ng masyadong maraming index ay hindi magandang ideya. Talaga, ikaw ay nagpapabagal ng mabilis na pagpasok/pag-update/pagtanggal ng isang row sa isang tabledahil kailangang i-update ng database ang mga index ng talahanayan gamit ang isang mamahaling O(log(N)) na operasyon para sa bawat index. Bukod dito, ang pagdaragdag ng mga index ay nangangahulugan ng mas maraming workload para sa tagapamahala ng transaksyon (ay ilalarawan sa dulo ng artikulo).

Para sa higit pang mga detalye, makikita mo ang artikulo sa Wikipedia sa B+puno. Kung gusto mo ng halimbawa ng pagpapatupad ng B+Tree sa isang database, tingnan artikulong ito и artikulong ito mula sa isang nangungunang MySQL developer. Pareho silang tumutuon sa kung paano pinangangasiwaan ng InnoDB (ang MySQL engine) ang mga index.

Tandaan: Sinabi sa akin ng isang mambabasa na, dahil sa mababang antas ng mga pag-optimize, ang B+ tree ay dapat na ganap na balanse.

Hashtable

Ang aming huling mahalagang istraktura ng data ay ang hash table. Ito ay lubhang kapaki-pakinabang kapag gusto mong mabilis na maghanap ng mga halaga. Higit pa rito, ang pag-unawa sa hash table ay makakatulong sa amin na maunawaan sa ibang pagkakataon ang isang karaniwang operasyon ng pagsali sa database na tinatawag na hash join ( sumali sa hash). Ang istraktura ng data na ito ay ginagamit din ng database upang mag-imbak ng ilang mga panloob na bagay (hal. lock table o buffer pool, makikita natin ang parehong mga konseptong ito mamaya).

Ang hash table ay isang istraktura ng data na mabilis na nakakahanap ng isang elemento sa pamamagitan ng key nito. Upang bumuo ng hash table kailangan mong tukuyin:

ang susi para sa iyong mga elemento
pag-andar ng hash para sa mga susi. Ang nakalkulang key hash ay nagbibigay ng lokasyon ng mga elemento (tinatawag na mga segment ).
function para sa paghahambing ng mga key. Kapag nahanap mo na ang tamang segment, dapat mong mahanap ang elementong hinahanap mo sa loob ng segment gamit ang paghahambing na ito.

Simpleng halimbawa

Kumuha tayo ng malinaw na halimbawa:

Ang hash table na ito ay may 10 segment. Dahil tinatamad ako, 5 segments lang ang napicturan ko, pero alam kong matalino ka, kaya ipapapicture ko na lang mag-isa ang pang 5. Gumamit ako ng hash function modulo 10 ng key. Sa madaling salita, iniimbak ko lamang ang huling digit ng susi ng elemento upang mahanap ang segment nito:

kung ang huling digit ay 0, ang elemento ay mahuhulog sa segment 0,
kung ang huling digit ay 1, ang elemento ay mahuhulog sa segment 1,
kung ang huling digit ay 2, ang elemento ay nahuhulog sa lugar 2,
...

Ang pag-andar ng paghahambing na ginamit ko ay simpleng pagkakapantay-pantay sa pagitan ng dalawang integer.

Sabihin nating gusto mong makuha ang elemento 78:

Kinakalkula ng hash table ang hash code para sa 78, na 8.
Ang hash table ay tumitingin sa segment 8, at ang unang elementong nahanap nito ay 78.
Ibinalik niya sa iyo ang item 78
Ang paghahanap ay nagkakahalaga lamang ng 2 operasyon (isa para kalkulahin ang hash value at isa pa para hanapin ang elemento sa loob ng segment).

Ngayon sabihin nating gusto mong makakuha ng elemento 59:

Kinakalkula ng hash table ang hash code para sa 59, na 9.
Ang hash table ay naghahanap sa segment 9, ang unang elementong natagpuan ay 99. Dahil 99!=59, ang element 99 ay hindi isang wastong elemento.
Gamit ang parehong lohika, ang pangalawang elemento (9), ang pangatlo (79), ..., ang huling (29) ay kinuha.
Hindi nahanap ang elemento.
Ang paghahanap ay nagkakahalaga ng 7 operasyon.

Magandang hash function

Tulad ng nakikita mo, depende sa halaga na iyong hinahanap, ang gastos ay hindi pareho!

Kung babaguhin ko ngayon ang hash function na modulo 1 ng key (iyon ay, pagkuha ng huling 000 na numero), ang pangalawang paghahanap ay nagkakahalaga lang ng 000 operasyon dahil walang mga elemento sa segment 6. Ang tunay na hamon ay ang paghahanap ng magandang hash function na gagawa ng mga bucket na naglalaman ng napakaliit na bilang ng mga elemento.

Sa aking halimbawa, ang paghahanap ng magandang hash function ay madali. Ngunit ito ay isang simpleng halimbawa, ang paghahanap ng magandang hash function ay mas mahirap kapag ang susi ay:

string (halimbawa - apelyido)
2 linya (halimbawa - apelyido at unang pangalan)
2 linya at petsa (halimbawa - apelyido, pangalan at petsa ng kapanganakan)
...

Sa isang mahusay na hash function, ang hash table lookup ay nagkakahalaga ng O(1).

Array vs hash table

Bakit hindi gumamit ng array?

Hmm, magandang tanong.

Ang hash table ay maaaring bahagyang na-load sa memorya, at ang natitirang mga segment ay maaaring manatili sa disk.
Sa isang array kailangan mong gumamit ng magkadikit na espasyo sa memorya. Kung naglo-load ka ng malaking mesa napakahirap makahanap ng sapat na tuluy-tuloy na espasyo.
Para sa hash table, maaari mong piliin ang key na gusto mo (halimbawa, bansa at apelyido ng tao).

Para sa karagdagang impormasyon, maaari mong basahin ang artikulo tungkol sa JavaHashMap, na isang mahusay na pagpapatupad ng hash table; hindi mo kailangang maunawaan ang Java para maunawaan ang mga konseptong sakop sa artikulong ito.

Pinagmulan: www.habr.com

Paano Gumagana ang Mga Relational Database (Bahagi 1)