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

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

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

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

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

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

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

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

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

Обратно към основите

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

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

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

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

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

Понятие

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

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

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

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

• O(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 000 операции
• Алгоритъмът O(n2) ще ви струва 4 000 000 операции

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

Както казах, все още е важно да знаете тази концепция, когато работите с огромни количества данни. Ако този път алгоритъмът трябва да обработи 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 на диска

Разбира се, има усложнения, по-лоши от n2, например:

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

Забележка: Не ви дадох действителната дефиниция на голямото обозначение O, просто идея. Можете да прочетете тази статия на Wikipedia за реалната (асимптотична) дефиниция.

MergeSort

Какво правите, когато трябва да сортирате колекция? Какво? Извиквате функцията sort()... Добре, добър отговор... Но за база данни трябва да разберете как работи тази функция 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 операции

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

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

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

Защото:

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

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

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

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

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

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

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

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

Масив, дърво и хеш таблица

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

Массив

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

Този двуизмерен масив е таблица с редове и колони:

• Всеки ред представлява обект
• Колоните съхраняват свойства, които описват обекта.
• Всяка колона съхранява данни от определен тип (цяло число, низ, дата...).

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

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

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

Да се ​​върнем към нашия проблем

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

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

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

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

B+TreeIndex

Докато това дърво работи добре за получаване на конкретна стойност, има ГОЛЯМ проблем, когато имате нужда получите множество елементи между две стойности. Това ще струва O(N), защото ще трябва да погледнете всеки възел в дървото и да проверите дали е между тези две стойности (напр. с подредено обхождане на дървото). Освен това тази операция не е удобна за I/O на диска, тъй като трябва да прочетете цялото дърво. Трябва да намерим начин за ефективно изпълнение заявка за диапазон. За да решат този проблем, съвременните бази данни използват модифицирана версия на предишното дърво, наречено 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+ дървото трябва да бъде напълно балансирано.

Хеш таблица

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

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

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

Прост пример

Да вземем ясен пример:

Тази хеш таблица има 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).

Масив срещу хеш таблица

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

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

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

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

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