Еј Хабр! Ви го презентирам преводот на статијата
„Како функционира релациската база на податоци“.

Кога станува збор за релациони бази на податоци не можам а да не мислам дека нешто недостасува. Тие се користат насекаде. Достапни се многу различни бази на податоци, од малиот и корисен SQLite до моќниот Teradata. Но, има само неколку написи кои објаснуваат како функционира базата на податоци. Можете да пребарувате за себе користејќи „howdoesarelationaldatabasework“ за да видите колку малку резултати има. Покрај тоа, овие написи се кратки. Ако ги барате најновите buzzy технологии (BigData, NoSQL или JavaScript), ќе најдете подетални статии кои објаснуваат како тие функционираат.

Дали релационите бази на податоци се премногу стари и премногу здодевни за да се објаснат надвор од универзитетските курсеви, научни трудови и книги?

Како програмер, мразам да користам нешто што не го разбирам. И ако базите на податоци се користат повеќе од 40 години, мора да има причина. Со текот на годините, потрошив стотици часови за вистински да ги разберам овие чудни црни кутии што ги користам секој ден. Релациони бази на податоци многу интересно бидејќи тие врз основа на корисни и повеќекратни концепти. Ако сте заинтересирани да ја разберете базата на податоци, но никогаш не сте имале време или склоност да истражувате во оваа широка тема, треба да уживате во оваа статија.

Иако насловот на оваа статија е експлицитен, Целта на оваа статија не е да се разбере како да се користи базата на податоци. Оттука, веќе треба да знаете како да напишете едноставно барање за поврзување и основни прашања КРУД; инаку можеби нема да ја разберете оваа статија. Тоа е единственото нешто што треба да го знаете, другото ќе ви го објаснам.

Ќе започнам со некои основи за компјутерски науки, како што е временската сложеност на алгоритмите (BigO). Знам дека некои од вас го мразат овој концепт, но без него нема да можете да ги разберете сложеноста во базата на податоци. Бидејќи ова е огромна тема, Ќе се фокусирам на што мислам дека е важно: како се обработува базата на податоци SQL истрага. Само ќе воведам основни концепти за бази на податоцитака што на крајот од статијата имате идеја за тоа што се случува под хаубата.

Бидејќи ова е долга и техничка статија која вклучува многу алгоритми и структури на податоци, одвојте време да ја прочитате. Некои концепти може да бидат тешки за разбирање; можете да ги прескокнете и сепак да ја добиете општата идеја.

За поупатените меѓу вас, оваа статија е поделена на 3 дела:

• Преглед на компонентите на базата на податоци на ниско и високо ниво
• Преглед на процесот на оптимизација на барањето
• Преглед на трансакциите и управувањето со баферите

Назад на Основи

Пред неколку години (во галаксија далеку, далеку...), програмерите мораа да го знаат точно бројот на операции што ги кодираат. Тие ги знаеја нивните алгоритми и структури на податоци напамет бидејќи не можеа да си дозволат да го трошат процесорот и меморијата на нивните бавни компјутери.

Во овој дел, ќе ве потсетам на некои од овие концепти бидејќи тие се од суштинско значење за разбирање на базата на податоци. Ќе го претставам и концептот индекс на база на податоци.

O(1) наспроти O(n2)

Во денешно време, многу програмери не се грижат за временската сложеност на алгоритмите... и тие се во право!

Но, кога се занимавате со многу податоци (не зборувам за илјадници) или ако се борите во милисекунди, станува критично да се разбере овој концепт. И како што можете да замислите, базите на податоци треба да се справат со двете ситуации! Нема да ве натерам да потрошите повеќе време отколку што е потребно за да ја пренесете поентата. Ова ќе ни помогне подоцна да го разбереме концептот на оптимизација базирана на трошоци (чини врз основа оптимизација).

Концепт

Временска сложеност на алгоритмот се користи за да се види колку време ќе биде потребно за комплетирање на алгоритам за дадена количина на податоци. За да ја опишеме оваа сложеност, користиме математичка нотација со големо О. Оваа нотација се користи со функција која опишува колку операции му се потребни на алгоритамот за даден број на влезови.

На пример, кога велам „овој алгоритам има сложеност O(some_function())“, тоа значи дека алгоритмот бара операции some_function(a_certain_amount_of_data) за да обработи одредена количина на податоци.

Во овој случај, Не е важна количината на податоци**, во спротивно ** како се зголемува бројот на операции со зголемување на обемот на податоци. Временската сложеност не обезбедува точен број на операции, но е добар начин да се процени времето на извршување.

Во овој графикон можете да го видите бројот на операции наспроти количината на влезни податоци за различни типови на сложеност на време на алгоритам. Јас користев логаритамска скала за да ги прикажам. Со други зборови, количината на податоци брзо се зголемува од 1 на 1 милијарда. Можеме да видиме дека:

• О(1) или константна сложеност останува константна (во спротивно не би се нарекла постојана сложеност).
• O(да се логирате(n)) останува ниско дури и со милијарди податоци.
• Најлоша тешкотија - O(n2), каде што бројот на операции рапидно расте.
• Другите две компликации се зголемуваат исто толку брзо.

примери

Со мала количина на податоци, разликата помеѓу O(1) и O(n2) е занемарлива. На пример, да речеме дека имате алгоритам кој треба да обработи 2000 елементи.

• Алгоритмот O(1) ќе ве чини 1 операција
• Алгоритмот O(log(n)) ќе ве чини 7 операции
• Алгоритмот O(n) ќе ве чини 2 операции
• Алгоритмот O(n*log(n)) ќе ве чини 14 операции
• Алгоритмот O(n2) ќе ве чини 4 операции

Разликата помеѓу O(1) и O(n2) изгледа голема (4 милиони операции), но ќе изгубите максимум 2 ms, само време да трепнете со очите. Навистина, современите процесори можат да обработуваат стотици милиони операции во секунда. Ова е причината зошто перформансите и оптимизацијата не се проблем во многу ИТ проекти.

Како што реков, сè уште е важно да се знае овој концепт кога се работи со огромни количини на податоци. Ако овој пат алгоритмот треба да обработи 1 елементи (што не е толку многу за базата на податоци):

• Алгоритмот O(1) ќе ве чини 1 операција
• Алгоритмот O(log(n)) ќе ве чини 14 операции
• Алгоритмот O(n) ќе ве чини 1 операции
• Алгоритмот O(n*log(n)) ќе ве чини 14 операции
• Алгоритмот O(n2) ќе ве чини 1 операции

Не сум направил математика, но би рекол дека со алгоритмот O(n2) имаш време да се напиеш едно кафе (дури и две!). Ако додадете уште 0 на волуменот на податоците, ќе имате време да дремете.

Ајде да одиме подлабоко

За ваша информација:

• Добро пребарување на хаш табела наоѓа елемент во O(1).
• Пребарувањето на добро избалансирано дрво дава резултати во O(log(n)).
• Пребарувањето низа дава резултати во O(n).
• Најдобрите алгоритми за сортирање имаат сложеност O(n*log(n)).
• Лош алгоритам за сортирање има сложеност O(n2).

Забелешка: Во следните делови ќе ги видиме овие алгоритми и структури на податоци.

Постојат неколку видови на сложеност на време на алгоритам:

• просечно сценарио на случај
• најдоброто сценарио
• и најлошото сценарио

Временската сложеност често е најлошото сценарио.

Зборував само за временската сложеност на алгоритмот, но сложеноста важи и за:

• потрошувачка на меморија на алгоритмот
• алгоритам за потрошувачка на влез/излез на дискот

Се разбира, има компликации полоши од n2, на пример:

• n4: ова е страшно! Некои од споменатите алгоритми ја имаат оваа сложеност.
• 3n: ова е уште полошо! Еден од алгоритмите што ќе ги видиме во средината на оваа статија ја има оваа сложеност (и всушност се користи во многу бази на податоци).
• факторски n: никогаш нема да ги добиете вашите резултати дури и со мала количина на податоци.
• нн: Доколку наидете на оваа сложеност, треба да се запрашате дали навистина ова е вашето поле на активност...

Забелешка: Не ви ја дадов вистинската дефиниција за ознаката голема О, само идеја. Оваа статија можете да ја прочитате на Википедија за вистинската (асимптотична) дефиниција.

MergeSort

Што правите кога треба да сортирате колекција? Што? Ја повикувате функцијата sort()... Добро, добар одговор... Но, за база на податоци, мора да разберете како функционира оваа функција сортирање().

Постојат неколку добри алгоритми за сортирање, па ќе се фокусирам на најважните: сортирање на спојување. Можеби не разбирате зошто сортирањето податоци е корисно во моментов, но треба да го направите по делот за оптимизација на барањето. Покрај тоа, разбирањето на сортирањето на спојување ќе ни помогне подоцна да ја разбереме заедничката операција за приклучување на базата наречена се логирате се приклучат (здружение за спојување).

Спојување

Како и многу корисни алгоритми, сортирањето со спојување се потпира на трик: комбинирањето на 2 подредени низи со големина N/2 во низа сортирана со N елементи чини само N операции. Оваа операција се нарекува спојување.

Ајде да видиме што значи ова со едноставен пример:

Оваа слика покажува дека за да се изгради конечната сортирана низа од 8 елементи, потребно е само да се повтори еднаш преку 2-те низи со 4 елементи. Бидејќи и двете низи со 4 елементи се веќе подредени:

• 1) ги споредувате двата тековни елементи во две низи (на почетокот струја = прва)
• 2) потоа земете го најмалиот за да го ставите во низа од 8 елементи
• 3) и преминете на следниот елемент во низата каде што сте го зеле најмалиот елемент
• и повторете 1,2,3 додека не стигнете до последниот елемент од една од низите.
• Потоа ги земате преостанатите елементи од другата низа за да ги ставите во низа од 8 елементи.

Ова функционира затоа што и двете низи со 4 елементи се подредени и затоа не мора да се „враќате назад“ во тие низи.

Сега кога го разбравме трикот, еве го мојот псевдокод за спојување:

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;

Сортирањето со спојување го разложува проблемот на помали проблеми и потоа ги наоѓа резултатите од помалите проблеми за да го добие резултатот од оригиналниот проблем (забелешка: овој тип на алгоритам се нарекува подели и освојувај). Ако не го разбирате овој алгоритам, не грижете се; Не го разбрав првиот пат кога го видов. Ако може да ви помогне, овој алгоритам го гледам како двофазен алгоритам:

• Фаза на поделба, каде низата е поделена на помали низи
• Фазата на сортирање е местото каде што малите низи се комбинираат (со користење на унија) за да формираат поголема низа.

Фаза на поделба

Во фазата на поделба, низата е поделена на унитарни низи во 3 чекори. Формалниот број на чекори е log(N) (бидејќи N=8, log(N) = 3).

Како го знам ова?

Јас сум генијалец! Со еден збор - математика. Идејата е секој чекор да ја дели големината на оригиналната низа со 2. Бројот на чекори е колку пати можете да ја поделите оригиналната низа на два. Ова е точната дефиниција за логаритам (основа 2).

Фаза на сортирање

Во фазата на сортирање, започнувате со унитарни (едноелементни) низи. За време на секој чекор применувате повеќе операции за спојување и вкупниот трошок е N = 8 операции:

• Во првата фаза имате 4 спојувања кои чинат по 2 операции
• Во вториот чекор имате 2 спојувања кои чинат по 4 операции
• Во третиот чекор имате 1 спојување кое чини 8 операции

Бидејќи има лог (N) чекори, вкупните трошоци Н * log(N) операции.

Предности на сортирање на спојување

Зошто овој алгоритам е толку моќен?

Бидејќи:

• Можете да го промените за да го намалите отпечатокот на меморијата за да не создавате нови низи, туку директно да ја менувате влезната низа.

Забелешка: овој тип на алгоритам се нарекува in-место (сортирање без дополнителна меморија).

• Можете да го промените да користи простор на дискот и мала количина на меморија во исто време без да предизвикате значителни трошоци за влез/излез на дискот. Идејата е да се вчитаат во меморијата само оние делови кои моментално се обработуваат. Ова е важно кога треба да сортирате табела од повеќе гигабајти со мемориски бафер од само 100 мегабајти.

Забелешка: овој тип на алгоритам се нарекува надворешен сорт.

• Можете да го промените да работи на повеќе процеси/нишки/сервери.

На пример, дистрибуираното сортирање на спојување е една од клучните компоненти Hadoop (што е структура во големи податоци).

• Овој алгоритам може да го претвори оловото во злато (навистина!).

Овој алгоритам за сортирање се користи во повеќето (ако не и сите) бази на податоци, но не е единствениот. Ако сакате да дознаете повеќе, можете да го прочитате ова истражувачка работа, кој ги разгледува добрите и лошите страни на заедничките алгоритми за сортирање на бази на податоци.

Низа, дрво и хеш табела

Сега кога ја разбираме идејата за временска сложеност и сортирање, треба да ви кажам за 3 структури на податоци. Ова е важно бидејќи тие се основата на современите бази на податоци. Ќе го претставам и концептот индекс на база на податоци.

Низа

Дводимензионалната низа е наједноставната структура на податоци. Табелата може да се замисли како низа. На пример:

Оваа 2-димензионална низа е табела со редови и колони:

• Секоја линија претставува ентитет
• Колоните складираат својства што го опишуваат ентитетот.
• Секоја колона складира податоци од одреден тип (цел број, низа, датум...).

Ова е погодно за складирање и визуелизирање на податоци, меѓутоа, кога треба да пронајдете одредена вредност, тоа не е соодветно.

На пример, ако сакате да ги најдете сите момци кои работат во ОК, ќе треба да го погледнете секој ред за да одредите дали тој ред припаѓа на ОК. Тоа ќе ве чини N трансакциикаде N - број на линии, што не е лошо, но дали може да има побрз начин? Сега е време да се запознаеме со дрвјата.

Забелешка: Повеќето модерни бази на податоци обезбедуваат проширени низи за ефикасно складирање на табелите: организирани табели со куп и табели организирани според индекс. Но, ова не го менува проблемот за брзо наоѓање на одредена состојба во група колони.

Дрво и индекс на база на податоци

Бинарното стебло за пребарување е бинарно дрво со посебно својство, клучот на секој јазол мора да биде:

• поголема од сите клучеви зачувани во левото поддрво
• помалку од сите клучеви зачувани во десното поддрво

Ајде да видиме што значи ова визуелно

Идејата

Ова дрво има N = 15 елементи. Да речеме дека барам 208:

• Почнувам од коренот чиј клуч е 136. Од 136<208 го гледам десното подстебло на јазолот 136.
• 398>208 затоа го гледам левото поддрво од јазолот 398
• 250>208 затоа го гледам левото поддрво од јазолот 250
• 200<208, затоа го гледам десното поддрво на јазолот 200. Но, 200 нема десно поддрво, вредност не постои (бидејќи ако постои, ќе биде во десното поддрво 200).

Сега да речеме дека барам 40

• Почнувам од коренот чиј клуч е 136. Од 136 > 40, го гледам левото поддрво од јазолот 136.
• 80 > 40, па затоа го гледам левото поддрво од јазолот 80
• 40 = 40, јазол постои. Го враќам ID-то на редот во јазолот (не е прикажано на сликата) и го барам во табелата дадениот ID на редот.
• Познавањето на ID на редот ми овозможува да знам точно каде се податоците во табелата, за да можам веднаш да ги повратам.

На крајот, двете пребарувања ќе ме чинат колку нивоа во дрвото. Ако внимателно го прочитате делот за сортирање со спојување, треба да видите дека има нивоа log(N). Излегува, Дневник на трошоци за пребарување (N), не е лошо!

Да се ​​вратиме на нашиот проблем

Но, ова е многу апстрактно, па да се вратиме на нашиот проблем. Наместо едноставен цел број, замислете низа што ја претставува земјата на некој од претходната табела. Да речеме дека имате дрво што го содржи полето „земја“ (колона 3) од табелата:

• Ако сакате да знаете кој работи во ОК
• гледаш во дрвото за да го добиеш јазолот што ја претставува Велика Британија
• внатре во „UKnode“ ќе ја најдете локацијата на работните записи во ОК.

Ова пребарување ќе чини операции log(N) наместо N операции ако ја користите низата директно. Тоа што штотуку го претстави беше индекс на база на податоци.

Може да изградите индексно стебло за која било група полиња (низа, број, 2 линии, број и низа, датум...) се додека имате функција за споредување клучеви (т.е. групи на полиња) за да можете да поставите ред меѓу клучевите (што е случај за сите основни типови во базата на податоци).

B+TreeIndex

Иако ова дрво работи добро за добивање одредена вредност, има ГОЛЕМ проблем кога ви треба добие повеќе елементи помеѓу две вредности. Ова ќе чини O(N) затоа што ќе треба да го погледнете секој јазол во дрвото и да проверите дали е помеѓу овие две вредности (на пр. со наредено преминување на дрвото). Покрај тоа, оваа операција не е пријателска за влез/излез на дискот бидејќи треба да го прочитате целото стебло. Треба да најдеме начин за ефикасно извршување барање за опсег. За да се реши овој проблем, модерните бази на податоци користат изменета верзија на претходното дрво наречено B+Tree. Во дрвото Б+Дрво:

• само најниските јазли (листови) складирајте информации (локација на редови во соодветната табела)
• остатокот од јазлите се тука за рутирање до правилниот јазол за време на пребарувањето.

Како што можете да видите, тука има повеќе јазли (двапати). Навистина, имате дополнителни јазли, „јазли за одлучување“, кои ќе ви помогнат да го пронајдете точниот јазол (кој ја складира локацијата на редовите во поврзаната табела). Но, сложеноста на пребарувањето е сè уште O(log(N)) (има само уште едно ниво). Големата разлика е во тоа јазлите на пониското ниво се поврзани со нивните наследници.

Со ова Б+Дрво, ако барате вредности помеѓу 40 и 100:

• Треба само да барате 40 (или најблиската вредност по 40 ако 40 не постои) како што направивте со претходното стебло.
• Потоа соберете 40 наследници користејќи директни врски со наследниците додека не достигнете 100.

Да речеме дека наоѓате M наследници и дрвото има N јазли. Пронаоѓањето на специфичен јазол чини log(N) како претходното стебло. Но, штом ќе го добиете овој јазол, ќе добиете M наследници во операциите M со референци за нивните наследници. Ова пребарување чини само M+log(N) операции во споредба со N операции на претходното стебло. Покрај тоа, не мора да го читате целосното стебло (само M+log(N) јазли), што значи помала употреба на дискот. Ако M е мал (на пр. 200 редови) и N е голем (1 редови), ќе има ГОЛЕМА разлика.

Но, тука има нови проблеми (повторно!). Ако додадете или избришете ред во базата на податоци (а со тоа и во поврзаниот индекс B+Tree):

• мора да одржувате ред помеѓу јазлите во B+Tree, инаку нема да можете да ги најдете јазлите во несортираното дрво.
• мора да го задржите минималниот можен број на нивоа во B+Tree, инаку O(log(N)) временската сложеност станува O(N).

Со други зборови, Б+Дрвото мора да биде самоуредувачко и избалансирано. За среќа, ова е можно со паметни операции за бришење и вметнување. Но, ова има цена: вметнувањата и бришењата во дрвото Б+ чинат O(log(N)). Затоа некои од вас го слушнале тоа користењето премногу индекси не е добра идеја. Навистина, го успорувате брзото вметнување/ажурирање/бришење на ред во табелабидејќи базата на податоци треба да ги ажурира индексите на табелата користејќи скапа операција O(log(N)) за секој индекс. Покрај тоа, додавањето индекси значи поголем обем на работа за менаџер на трансакции (ќе биде опишано на крајот од статијата).

За повеќе детали, можете да ја видите статијата на Википедија на B+Дрво. Ако сакате пример за имплементација на B+Tree во база на податоци, погледнете овој член, и овој член, од водечки развивач на MySQL. И двајцата се фокусираат на тоа како InnoDB (моторот MySQL) се справува со индексите.

Забелешка: Читател ми кажа дека, поради оптимизациите на ниско ниво, дрвото B+ треба да биде целосно избалансирано.

Hashtable

Нашата последна важна структура на податоци е хеш-табела. Ова е многу корисно кога сакате брзо да ги барате вредностите. Згора на тоа, разбирањето на хеш табела ќе ни помогне подоцна да ја разбереме заедничката операција за приклучување на базата наречена хаш приклучување ( хаш приклучи се). Оваа структура на податоци се користи и од базата на податоци за складирање на некои внатрешни работи (на пр. маса за заклучување или тампон базен, ќе ги видиме и двата концепта подоцна).

Хеш табела е податочна структура која брзо наоѓа елемент по неговиот клуч. За да изградите хеш табела, треба да дефинирате:

• поим за вашите елементи
• хаш функција за клучеви. Пресметаните хашови на клучеви ја даваат локацијата на елементите (наречени сегменти ).
• функција за споредување копчиња. Откако ќе го пронајдете точниот сегмент, мора да го пронајдете елементот што го барате во сегментот користејќи ја оваа споредба.

Едноставен пример

Да земеме јасен пример:

Оваа хаш табела има 10 сегменти. Бидејќи сум мрзлив, сликав само 5 сегменти, но знам дека си паметен, па ќе ти дозволам да ги сликаш другите 5 сам. Јас користев хаш функција модуло 10 од клучот. Со други зборови, ја складирам само последната цифра од клучот на елементот за да го најдам неговиот сегмент:

• ако последната цифра е 0, елементот спаѓа во сегментот 0,
• ако последната цифра е 1, елементот спаѓа во сегментот 1,
• ако последната цифра е 2, елементот спаѓа во областа 2,
• ...

Функцијата за споредба што ја користев е едноставно еднаквост помеѓу два цели броеви.

Да речеме дека сакате да го добиете елементот 78:

• Хеш-табелата го пресметува хаш-кодот за 78, што е 8.
• Хеш-табелата го гледа сегментот 8, а првиот елемент што го наоѓа е 78.
• Таа ви ја враќа ставката 78
• Пребарувањето чини само 2 операции (едниот за пресметување на вредноста на хашот, а другиот за пребарување на елементот во сегментот).

Сега да речеме дека сакате да го добиете елементот 59:

• Хеш-табелата го пресметува хаш-кодот за 59, што е 9.
• Хеш-табелата пребарува во сегментот 9, првиот пронајден елемент е 99. Бидејќи 99!=59, елементот 99 не е валиден елемент.
• Со истата логика се зема вториот елемент (9), третиот (79), ..., последниот (29).
• Елементот не е пронајден.
• Пребарувањето чинеше 7 операции.

Добра хаш функција

Како што можете да видите, во зависност од вредноста што ја барате, трошокот не е ист!

Ако сега го сменам хаш-функцискиот модуло 1 од клучот (т.е. ги земам последните 000 цифри), второто пребарување чини само 000 операција бидејќи нема елементи во сегментот 6. Вистинскиот предизвик е да се најде добра хаш функција која ќе создаде кофи кои содржат многу мал број елементи.

Во мојот пример, наоѓањето добра хаш функција е лесно. Но, ова е едноставен пример, да се најде добра хаш функција е потешко кога клучот е:

• низа (на пример - презиме)
• 2 реда (на пример - презиме и име)
• 2 реда и датум (на пример - презиме, име и датум на раѓање)
• ...

Со добра хаш функција, пребарувањето на табелите за хаш чини O(1).

Низа наспроти хеш табела

Зошто да не користите низа?

Хм, добро прашање.

• Табелата за хаш може да биде делумно вчитан во меморија, а останатите сегменти можат да останат на дискот.
• Со низа мора да користите соседен простор во меморијата. Ако вчитувате голема маса многу е тешко да се најде доволно континуиран простор.
• За хеш-табела, можете да го изберете клучот што го сакате (на пример, земја и презиме на лицето).

За повеќе информации, можете да ја прочитате статијата за ЈаваHashMap, што е ефикасна имплементација на хеш табела; не треба да ја разбирате Java за да ги разберете концептите опфатени во оваа статија.

Извор: www.habr.com