Здравей, Хабр! Представям ви превода на статията
"Как работи релационната база данни".

Когато става въпрос за релационни бази данни, не мога да не мисля, че нещо липсва. Те се използват навсякъде. Съществуват множество различни бази данни: от малкия и полезен SQLite до мощната Teradata. Но само няколко статии обясняват как работи базата данни. Можете сами да потърсите за "howdoesarelationaldatabasework" («как работят релационните бази данни»), за да видите колко малко резултати има. Освен това, тези статии са кратки. Ако търсите последните модни технологии (BigData, NoSQL или JavaScript), ще намерите повече задълбочени статии, които обясняват как те работят.

Релационните бази данни твърде стари и твърде скучни ли са, за да бъдат обяснени извън университетските курсове, научни статии и книги?

Като разработчик, мразя да използвам нещо, което не разбирам. И ако базите данни се използват от повече от 40 години, трябва да има причина за това. През тези години съм отделил стотици часове, за да разбера наистина тези странни черни кутии, които използвам всеки ден. Релационни бази данни много интересни, защото те са основани на полезни и многократно използвани концепции.Ако искате да разберете базата данни, но никога не сте имали време или желание да задълбавате в тази обширна тема, трябва да харесате тази статия.

Въпреки че заглавието на тази статия е ясно, целта на тази статия не е да разберете как да използвате базата данни.Следователно, вие вече трябва да знаете как да напишете прост заявка за свързване и основни запитвания; CRUDв противен случай, може да не разберете тази статия. Това е единственото, което трябва да знаете, ще обясня всичко останало.

Ще започна с някои основи на компютърните науки, като времевата сложност на алгоритмите (BigO). Знам, че някои от вас мразят тази концепция, но без нея не можете да разберете нюансите във вътрешността на базата данни. Тъй като това е огромна тема, ще се съсредоточа върху това, което смятам за важно.: как базата данни обработва SQL запитване. Ще представя само основните концепции на базата данни,, за да имате представа за това, което се случва в дъното в края на статията.

Тъй като това е дълга и техническа статия, която включва много алгоритми и структури от данни, не бързайте да я прочетете. Някои концепции може да са трудни за разбиране; можете да ги пропуснете и все пак да получите обща представа.

За по-добре осведомените от вас, тази статия е разделена на 3 части:

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

Връщане към основите

Много години назад (в далечна, далечна галактика…) разработчиците трябваше да знаят точно колко операции кодираха. Те знаеха наизуст своите алгоритми и структури от данни, тъй като не можеха да си позволят да губят ЦП и паметта на своите бавни компютри.

В тази част ще ви напомня за някои от тези концепции, тъй като те са необходими за разбирането на базата данни. Ще въведа и концепцията за индекса на базата данни.

O(1) срещу O(n2)

В момента много разработчици не се интересуват от времевата сложност на алгоритмите… и те са прави!

Но когато имате работа с много данни (не говоря за хиляди) или ако се борите за милисекунди, става критично важно да разберете тази концепция. Както разбирате, базите данни трябва да се справят с двете ситуации! Няма да ви карам да отделяте повече време от необходимо, за да усвоите същността. Това ще ни помогне по-късно да разберем концепцията за оптимизация на базата на разходи (cost based optimization).

Концепцията

Времевата сложност на алгоритъма се използва, за да се види колко време ще отнеме изпълнението на алгоритъма за даден обем данни. За да опишат тази сложност, използват математическите обозначения на голямото O. Тази нотация се използва с функция, която описва колко операции са необходими на алгоритъма за зададено количество входни данни.

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

В същото време важно е не количеството данни**, а това, ** как се увеличава количеството операции с увеличаването на обема данни. Времевата сложност не дава точен брой операции, а е добър начин за оценка на времето за изпълнение.

На този график можете да видите зависимостта между броя операции и обема на входящите данни за различни типове времеви сложности на алгоритмите. Използвах логаритмична скала, за да ги представя. С други думи, количеството данни бързо нараства от 1 до 1 млрд. Можем да видим, че:

O(1) или постоянната сложност остава постоянна (иначе не може да се нарече постоянна сложност).
O(log(n)) остава ниска дори при милиарди данни.
Най-лошата сложност — O(n2), при която броят на операциите бързо нараства.
Другите две сложности също нарастват бързо.

Примери

При малко количество данни разликата между O(1) и O(n2) е незначителна. Например, предположим, че имате алгоритъм, който трябва да обработва 2000 елемента.

Алгоритъм O(1) ще ви струва 1 операция
Алгоритъм O(log(n)) ще ви струва 7 операции
Алгоритъм O(n) ще ви струва 2 000 операции
Алгоритъм O(n * log(n)) ще ви струва 14 000 операции
Алгоритъм O(n2) ще ви струва 4 000 000 операции

Разликата между O(1) и O(n2) изглежда голяма (4 милиона операции), но ще загубите максимум 2 мс, просто времето да мигнете с очи. Наистина, съвременните процесори могат да обработват стотици милиони операции в секунда. Затова производителността и оптимизацията не са проблем в много ИТ проекти.

Както вече споменах, все още е важно да познавате тази концепция при работа с огромно количество данни. Ако този път алгоритъмът трябва да обработи 1 000 000 елемента (което не е много за база данни):

Алгоритъм O(1) ще ви струва 1 операция
Алгоритъм O(log(n)) ще ви струва 14 операции
Алгоритъм O(n) ще ви струва 1 000 000 операции
Алгоритъм O(n * log(n)) ще ви струва 14 000 000 операции
Алгоритъм O(n2) ще ви струва 1 000 000 000 000 операции

Не съм правил изчисления, но бих казал, че с алгоритъм O(n2) имате време да изпите кафето си (дори две!). Ако добавите още 0 към обема на данните, ще имате време да подремнете.

Да задълбочим

За справка:

Търсенето в добра хеш таблица намира елемент за O(1).
Търсенето в добре балансирано дърво дава резултат за O(log(n)).
Търсенето в масив дава резултат за O(n).
Най-добрите алгоритми за сортиране имат сложност O(n * log(n)).
Лош алгоритъм за сортиране има сложност O(n2).

Забележка: в следващите части ще видим тези алгоритми и структури от данни.

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

среден случай
най-добрия сценарий
и най-лошия сценарий

Времевата сложност често е в най-лошия сценарий.

Говорех само за времевата сложност на алгоритмите, но сложността също така се прилага за:

потреблението на памет от алгоритъма
потреблението на диск I/O от алгоритъма

Разбира се, има по-лоши сложности от n², например:

n⁴: това е ужасно! Някои от споменатите алгоритми имат такава сложност.
3n: това е още по-лошо! Един от алгоритмите, които ще видим по-късно в статията, има тази сложност (и той наистина се използва в много бази данни).
факториал n: никога няма да получите своите резултати дори с малко количество данни.
nⁿ: ако се сблъскате с тази сложност, трябва да се запитате дали това наистина е вашата област...

Забележка: дадох ви не реално определение на обозначението „голямо O“, а просто идея. Можете да прочетете тази статия за Уикипедия реалното (асимптотично) определение.

MergeSort (Сортиране с сливане)

Какво правите, когато трябва да сортирате колекция? Какво? Извиквате функцията sort()… ОК, добър отговор… Но за бази данни трябва да разберете как работи тази функция sort().

Съществуват няколко добри алгоритма за сортиране, затова ще се спра на най-важния: сортирането с сливане. Може би сега не разбирате защо сортирането на данни е полезно, но ще трябва да разберете след частта, посветена на оптимизация на заявките. Освен това разбирането на сортирането с сливане ще ни помогне по-късно да разберем общата операция join на базите данни, наречена обединение join (сливане на обединения).

Merge (сливане)

Както много полезни алгоритми, сортирането с сливане се основава на трик: обединяването на 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

   // рекурсивни извиквания
   [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);

   // сливане на 2-те малки сортирани масива в един голям
   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 операции

Тъй като съществуват log(N) стъпки, общата цена N * log(N) операции.

Предимства на сортирането чрез сливане

Защо този алгоритъм е толкова мощен?

Защото:

Можете да го промените, за да намалите обема на паметта, така че да не създавате нови масиви, а да променяте директно входния масив.

Забележка: този вид алгоритми се нарича в—място (сортиране без допълнителна памет).

Можете да го измените да използва едновременно дисково пространство и малък обем памет без значителни разходи за дисков вход/изход. Идеята е да зареждате в паметта само тези части, които в момента се обработват. Това е важно, когато трябва да сортирате таблица с размер няколко гигабайта, използвайки само кеш с размер 100 мегабайта.

Забележка: този вид алгоритми се нарича външна сортировка.

Можете да го промените да се изпълнява на множество процеси/нишки/сървъри.

Например, разпределената сортировка сливане е един от ключовите компоненти Hadoop (която е структура в големите данни).

Този алгоритъм може да превърне оловото в злато (истински!).

Този алгоритъм за сортиране се използва в повечето (ако не и във всички) бази данни, но не е единственият. Ако искате да научите повече, можете да прочетете тази изследователска работа, която обсъжда плюсовете и минусите на общите алгоритми за сортиране в бази данни.

Масив, Дерево и Хеш-таблица

Сега, когато разбираме идеята за времевата сложност и сортирането, трябва да ви разкажа за 3 структури от данни. Това е важно, защото те са основата на съвременните бази данни.Ще въведа също понятието индекса на базата данни.

Масив

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

Този 2-мерен масив представлява таблица с редове и колони:

Всеки ред представлява единица
Колоните съхраняват свойства, описващи единицата.
Всяка колона съхранява данни от определен тип (integer, string, date …).

Така е удобно да се съхраняват и визуализират данни, обаче, когато трябва да намерите определена стойност, това не е подходящо.

Например, ако искате да намерите всички момчета, които работят в Обединеното кралство, трябва да прегледате всеки ред, за да определите дали този ред принадлежи към Обединеното кралство. Това ще ви струва N операции, където N — броят редове, което не е лошо, но може ли да има по-бърз начин? Сега е време да се запознаем с дърветата.

Забележка: повечето съвременни бази данни предлагат разширени масиви за ефективно съхранение на таблици: heap-organized tables и index-organized tables. Но това не променя проблема с бързото търсене на определено условие в група от колони.

Дърво и индекс на бази данни

Двоичното дърво за търсене е двоично дърво със специално свойство, ключът в всеки възел трябва да бъде:

по-голям от всички ключове, съ хранят се в лявото поддърво
по-малък от всички ключове, съ хранят се в дясното поддърво

Нека да видим какво означава това визуално

Идея

Това дърво има 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, възел съществува. Извличам идентификатора на реда в възела (това не е на изображението) и гледам в таблицата за съответния идентификатор на реда.
Знанието на идентификатора на реда ми позволява да разбера къде точно се намират данните в таблицата, и затова мога да ги получа незабавно.

В крайна сметка и двете търсения ще ми струват броя на нивата в дървото. Ако внимателно прочетете частта за сливане на сортиране, трябва да видите, че тук има log (N) нива. Получава се, цената на търсене log(N), не лошо!

Връщаме се на нашия проблем

Но това е много абстрактно, затова да се върнем на нашия проблем. Вместо просто цяло число, си представете низ, който представлява страната на някого в предишната таблица. Да предположим, че имате дърво, което съдържа поле "country" (колона 3) от таблицата:

Ако искате да знаете кой работи във Великобритания
гледате дървото, за да получите възел, който представлява Великобритания
вътре в "UKnode" ще намерите местоположението на записите на работниците във Великобритания.

Търсенето ще струва log(N) операции вместо N операции, ако използвате масив директно. Това, което току-що представихте, беше индекс на база данни.

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

B+TreeIndex

Въпреки че това дърво работи добре за получаване на определена стойност, има ГОЛЯМ проблем, когато трябва да получите няколко елемента между две стойности. Това ще струва O(N), защото ще трябва да прегледате всеки възел в дървото и да проверите дали той е между тези две стойности (например, с подредено обхождане на дървото). Освен това, тази операция не е удобна за дисково входно-изходно устройство, тъй като ще трябва да прочетете цялото дърво. Трябва да намерим начин да изпълним запитване в диапазон. За решаване на този проблем, съвременните бази данни използват модифицирана версия на предишното дърво, наречена B+Tree. В B+Tree дървото:

само най-долните възли (листата) съхраняват информацията (разположение на редовете в свързаната таблица)
останалите възли са тук за маршрутизиране към правилния възел по време на търсене.

Както можете да видите, тук има повече възли (двойно повече). Всъщност, имате допълнителни възли, „възли за вземане на решения“, които ще ви помогнат да намерите правилния възел (който съхранява разположението на редовете в свързаната таблица). Но сложността на търсенето все още е O(log(N)) (има само един допълнителен слой). Голямата разлика е, че възлите на долното ниво са свързани с техните наследници.

С това B+Tree, ако търсите стойности от 40 до 100:

Трябва просто да потърсите 40 (или най-близката стойност след 40, ако 40 не съществува), както правехте с предишното дърво.
След това съберете наследниците на 40, като използвате директни връзки към наследниците, докато не достигнете 100.

Да предположим, че сте намерили M наследници, а дървото има N възли. Търсенето на конкретен възел струва log(N), подобно на предишното дърво. Но, получавайки този възел, ще получите M наследници в M операции с връзки към техните наследници. Търсенето ще струва само M+log(N) операции в сравнение с N операции от предишното дърво. Освен това, не е необходимо да четете цялото дърво (само M + log (N) възела), което означава по-малка дискова употреба. Ако M е малко (например, 200 реда) и N голямо (1 000 000 реда), това ще бъде ГОЛЯМА разлика.

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

трябва да поддържате реда между възлите в B+Tree, в противен случай не можете да намерите възлите в несортирано дърво.
трябва да запазите минимално възможното количество нива в B+Tree, в противен случай времевата сложност от O (log (N)) ще стане O (N).

С други думи, B+Tree трябва да бъде самоподредено и балансирано. За щастие, това е възможно с умни операции за изтриване и вмъкване. Но това е скъпо: вмъкването и изтриването в B+ дърво струва O (log (N)). Ето защо някои от вас са чували, че прекомерната употреба на индекси не е много добра идея. Наистина, забавяте бързото вмъкване / актуализиране / изтриване на редове в таблицата, тъй като базата данни трябва да актуализира индексите на таблицата с помощта на скъпата операция O (log (N)) за всеки индекс. Освен това, добавянето на индекси означава по-голямо натоварване за мениджъра на транзакции ще бъде описан в края на статията).

За по-подробна информация, можете да погледнете статията в Уикипедия за B+Дърво. Ако искате пример за реализация на B+Tree в базата данни, разгледайте тази статия и тази статия от водещия разработчик на MySQL. И двете се фокусират върху това как InnoDB (двигателят на MySQL) обработва индексите.

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

Hashtable (Хеш-таблица)

Нашата последна важна структура от данни е хеш-таблицата. Тя е много полезна, когато искате бързо да търсите стойности. Освен това, разбирането на хеш-таблицата ще ни помогне по-късно да разберем общата операция за съединение с базата данни, наречена хеш-съединение ( hash join). Тази структура от данни също се използва от базата данни за съхранение на някои вътрешни неща (например, таблица за заключване или буферен пул, ще видим и двете тези концепции по-късно).

Хеш-таблица е структура от данни, която бързо намира елемента по неговия ключ. За изграждането на хеш-таблица трябва да определите:

ключ за вашите елементи
хеш-функция за ключовете. Изчислените хешове на ключовете дават местоположението на елементите (наречени сегменти ).
функция за сравнение на ключове. След като намерите правилния сегмент, трябва да намерите елемента, който търсите, в сегмента, използвайки това сравнение.

Прост пример

Нека да вземем визуален пример:

Тази хеш-таблица има 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 цифри), второто търсене ще струва само 1 операция, тъй като в сегмент 000059 няма елементи. Истинската задача е да намерите добра хеш-функция, която ще създава сегменти, съдържащи много малко елементи..

В примера ми, намирането на добра хеш-функция е лесно. Но това е прост пример, намирането на добра хеш-функция е по-сложно, когато ключът:

стринг (например – фамилия)
2 стринга (например – фамилия и име)
2 стринга и дата (например – фамилия, име и дата на раждане)
…

С добра хеш-функция, търсенето в хеш-таблицата става в O(1).

Масив vs хеш-таблица

Защо да не използваме масив?

Хм, добър въпрос.

Хеш-таблицата може да бъде частично заредена в паметта, а останалите сегменти могат да останат на диска.
С масив трябва да използвате непрекъснато пространство в паметта. Ако заредите голяма таблица, много е трудно да намерите достатъчно непрекъснато пространство.
За хеш-таблицата можете да изберете необходимия ключ (например, страната и фамилията на човека).

За допълнителна информация можете да прочетете статията за JavaHashMap, която е ефективна реализация на хеш-таблица; не е необходимо да разбирате Java, за да разберете концепциите, изложени в тази статия.

Източник: habr.com