Здраво, Хабр! Представљам вашој пажњи превод чланка
"Како ради релационе базе података".

Када су у питању релационе базе података, не могу а да не мислим да нешто недостаје. Користе се свуда. На располагању је много различитих база података, од малог и корисног СКЛите-а до моћног Терадата. Али постоји само неколико чланака који објашњавају како база података функционише. Можете сами да тражите користећи „ховдоесарелатионалдатабасеворк“ да видите колико је мало резултата. Штавише, ови чланци су кратки. Ако тражите најновије технологије (БигДата, НоСКЛ или ЈаваСцрипт), наћи ћете детаљније чланке који објашњавају како оне функционишу.

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

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

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

Почећу са неким основама рачунарства, као што је временска сложеност алгоритама (БигО). Знам да неки од вас мрзе овај концепт, али без њега нећете моћи да разумете замршености унутар базе података. Пошто је ово огромна тема, Ја ћу се фокусирати на оно што мислим да је важно: како база података обрађује СКЛ упит. Само ћу се представити основни концепти базе податакатако да на крају чланка имате представу о томе шта се дешава испод хаубе.

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

За боље упућене међу вама, овај чланак је подељен на 3 дела:

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

Повратак основи

Пре много година (у далекој, далекој галаксији...), програмери су морали да знају тачно број операција које су кодирали. Знали су своје алгоритме и структуре података напамет јер нису могли приуштити да троше ЦПУ и меморију својих спорих рачунара.

У овом делу ћу вас подсетити на неке од ових концепата јер су они од суштинског значаја за разумевање базе података. Такође ћу представити концепт индекс базе података.

О(1) против О(н2)

Данас многи програмери не маре за временску сложеност алгоритама... и у праву су!

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

Цонцепт

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

На пример, када кажем „овај алгоритам има сложеност О(соме_фунцтион())“, то значи да алгоритам захтева операције соме_фунцтион(а_цертаин_амоунт_оф_дата) за обраду одређене количине података.

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

На овом графикону можете видети број операција у односу на количину улазних података за различите типове временске сложености алгоритама. Користио сам логаритамску скалу да их прикажем. Другим речима, количина података се брзо повећава са 1 на 1 милијарду. Видимо да:

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

Примери

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

О(1) алгоритам ће вас коштати 1 операцију
О(лог(н)) алгоритам ће вас коштати 7 операција
О(н) алгоритам ће вас коштати 2 операција
О(н*лог(н)) алгоритам ће вас коштати 14 операција
О(н2) алгоритам ће вас коштати 4 операција

Чини се да је разлика између О(1) и О(н2) велика (4 милиона операција), али ћете изгубити највише 2 мс, само време да трепнете очима. Заиста, савремени процесори могу да обрађују стотине милиона операција у секунди. Због тога перформансе и оптимизација нису проблем у многим ИТ пројектима.

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

О(1) алгоритам ће вас коштати 1 операцију
О(лог(н)) алгоритам ће вас коштати 14 операција
О(н) алгоритам ће вас коштати 1 операција
О(н*лог(н)) алгоритам ће вас коштати 14 операција
О(н2) алгоритам ће вас коштати 1 операција

Нисам израчунао, али бих рекао да са О(н2) алгоритмом имате времена да попијете кафу (чак и две!). Ако додате још 0 количини података, имаћете времена да одспавате.

Хајдемо дубље

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

Добро тражење хеш табеле проналази елемент у О(1).
Претраживање добро избалансираног стабла даје резултате у О(лог(н)).
Претраживање низа даје резултате у О(н).
Најбољи алгоритми за сортирање имају сложеност О(н*лог(н)).
Лош алгоритам за сортирање има сложеност О(н2).

Напомена: У наредним деловима ћемо видети ове алгоритме и структуре података.

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

просечан сценарио случаја
најбољи сценарио
и најгорем сценарију

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

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

потрошња меморије алгоритма
алгоритам потрошње И/О диска

Наравно, постоје компликације горе од н2, на пример:

н4: ово је страшно! Неки од наведених алгоритама имају ову сложеност.
3н: ово је још горе! Један од алгоритама које ћемо видети у средини овог чланка има ову сложеност (и заправо се користи у многим базама података).
факторијал н: никада нећете добити резултате чак ни са малом количином података.
нн: Ако наиђете на ову сложеност, запитајте се да ли је то заиста ваше поље деловања...

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

Сортирање спајањем

Шта радите када треба да сортирате колекцију? Шта? Позивате функцију сорт()... Ок, добар одговор... Али за базу података, морате разумети како ова функција сорт() функционише.

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

Споји

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

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

Ова слика показује да за прављење коначног сортираног низа од 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 корака. Формални број корака је лог(Н) (пошто је Н=8, лог(Н) = 3).

Откуд ја то знам?

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

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

У фази сортирања почињете са унитарним (једноструким) низовима. Током сваког корака примењујете више операција спајања и укупни трошак је Н = 8 операција:

У првој фази имате 4 спајања која коштају по 2 операције
У другом кораку имате 2 спајања која коштају по 4 операције
У трећем кораку имате 1 стапање које кошта 8 операција

Пошто постоји лог(Н) корака, укупни трошкови Н * лог(Н) операције.

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

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

Јер:

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

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

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

Напомена: овај тип алгоритма се зове екстерна сорта.

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

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

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

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

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

Сада када смо разумели идеју временске сложености и сортирања, требало би да вам кажем о 3 структуре података. Ово је важно јер они су основа савремених база података. Такође ћу представити концепт индекс базе података.

Арраи

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

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

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

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

На пример, ако желите да пронађете све момке који раде у УК, требало би да погледате сваки ред да бисте утврдили да ли тај ред припада УК. То ће вас коштати Н трансакцијаГде 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, чвор постоји. Преузимам ИД реда унутар чвора (није приказан на слици) и тражим у табели дати ИД реда.
Познавање ИД-а реда ми омогућава да знам тачно где се подаци налазе у табели, тако да могу одмах да их преузмем.

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

Вратимо се нашем проблему

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

Ако желите да знате ко ради у УК
погледате у дрво да бисте добили чвор који представља Велику Британију
унутар "УКноде" наћи ћете локацију евиденције радника у УК.

Ова претрага ће коштати лог(Н) операција уместо Н операција ако директно користите низ. Оно што сте управо представили је индекс базе података.

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

Б+ТрееИндек

Иако ово дрво добро функционише за добијање одређене вредности, постоји ВЕЛИКИ проблем када вам затреба добити више елемената између две вредности. Ово ће коштати О(Н) јер ћете морати да погледате сваки чвор у стаблу и проверите да ли се налази између ове две вредности (нпр. са наређеним обиласком дрвета). Штавише, ова операција није прилагођена за диск И/О пошто морате да прочитате цело стабло. Морамо пронаћи начин да ефикасно извршимо захтев домета. Да би решили овај проблем, модерне базе података користе модификовану верзију претходног стабла под називом Б+Трее. У стаблу Б+дрво:

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

Као што видите, овде има више чворова (два пута). Заиста, имате додатне чворове, „чворове одлуке“, који ће вам помоћи да пронађете тачан чвор (који чува локацију редова у повезаној табели). Али сложеност претраге је и даље О(лог(Н)) (постоји само још један ниво). Велика разлика је у томе чворови на нижем нивоу су повезани са својим наследницима.

Са овим Б+дрветом, ако тражите вредности између 40 и 100:

Само треба да потражите 40 (или најближу вредност после 40 ако 40 не постоји) као што сте урадили са претходним стаблом.
Затим прикупите 40 наследника користећи директне везе за наследнике док не достигнете 100.

Рецимо да сте пронашли М наследника и дрво има Н чворова. Проналажење одређеног чвора кошта лог(Н) као претходно стабло. Али када једном добијете овај чвор, добићете М наследника у М операцијама са референцама на њихове наследнике. Ова претрага кошта само М+лог(Н) операције у поређењу са Н операцијама на претходном стаблу. Штавише, не морате да читате цело стабло (само М+лог(Н) чворова), што значи мање коришћење диска. Ако је М мало (нпр. 200 редова), а Н велико (1 редова), биће ВЕЛИКА разлика.

Али овде (опет!) постоје нови проблеми. Ако додате или избришете ред у бази података (а самим тим и у повезаном Б+Трее индексу):

морате одржавати ред између чворова унутар Б+дрвета, иначе нећете моћи да пронађете чворове унутар несортираног дрвета.
морате задржати минимални могући број нивоа у Б+Стабло, иначе временска сложеност О(лог(Н)) постаје О(Н).

Другим речима, Б+Трее мора бити самоуређен и уравнотежен. Срећом, ово је могуће са паметним операцијама брисања и уметања. Али ово има своју цену: уметања и брисања у Б+ стаблу коштају О(лог(Н)). Зато су неки од вас то чули коришћење превише индекса није добра идеја. стварно, успоравате брзо уметање/ажурирање/брисање реда у табелијер база података треба да ажурира индексе табеле користећи скупу операцију О(лог(Н)) за сваки индекс. Штавише, додавање индекса значи веће оптерећење за менаџер трансакција (биће описано на крају чланка).

За више детаља, можете погледати чланак на Википедији на B+Дрво. Ако желите пример имплементације Б+Трее у базу података, погледајте овај чланак и овај чланак од водећег МиСКЛ програмера. Обоје се фокусирају на то како ИнноДБ (МиСКЛ мотор) рукује индексима.

Напомена: Читалац ми је рекао да би, због оптимизације ниског нивоа, Б+ стабло требало да буде потпуно избалансирано.

Хасхтабле

Наша последња важна структура података је хеш табела. Ово је веома корисно када желите да брзо потражите вредности. Штавише, разумевање хеш табеле ће нам помоћи да касније разумемо уобичајену операцију придруживања бази података која се зове хеш придруживање ( хасх јоин). Ову структуру података такође користи база података за складиштење неких интерних ствари (нпр. закључати сто или пуфер пуфера, касније ћемо видети оба ова концепта).

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

кључ за своје елементе
хасх функција за кључеве. Израчунати хешови кључа дају локацију елемената (тзв сегментима ).
функција за поређење кључева. Када пронађете тачан сегмент, морате пронаћи елемент који тражите унутар сегмента користећи ово поређење.

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

Узмимо јасан пример:

Ова хеш табела има 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 реда и датум (на пример - презиме, име и датум рођења)
...

Са добром хеш функцијом, тражење хеш табеле кошта О(1).

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

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

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

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

За више информација, можете прочитати чланак о ЈаваХасхМап, што је ефикасна имплементација хеш табеле; не морате да разумете Јаву да бисте разумели концепте обрађене у овом чланку.

Извор: ввв.хабр.цом

Како функционишу релационе базе података (1. део)