Прывітанне, Хабр! Уяўляю вашай увазе пераклад артыкула
"Гэта ў relative database work".

Калі справа даходзіць да рэляцыйных баз дадзеных я не магу не думаць, што нечага не хапае. Яны выкарыстоўваюцца ўсюды. Існуе мноства розных баз дадзеных: ад невялікага і карыснага SQLite да магутнай Teradata. Але ёсць толькі некалькі артыкулаў, якія тлумачаць, як працуе база даных. Вы можаце шукаць самі па запыце "howdoesarelationaldatabasework" («як працуюць рэляцыйныя базы дадзеных») каб убачыць, як мала вынікаў. Больш за тое, гэтыя артыкулы - кароткія. Калі ж вы шукаеце апошнія модныя тэхналогіі (BigData, NoSQL ці JavaScript), вы знойдзеце больш паглыбленых артыкулаў, якія тлумачаць, як яны працуюць.

Ці з'яўляюцца рэляцыйныя базы дадзеных занадта старымі і занадта сумнымі, каб іх можна было растлумачыць па-за ўніверсітэцкімі курсамі, даследаваннямі і кнігамі?

Як распрацоўшчык я ненавіджу выкарыстоўваць тое, што не разумею. І калі базы дадзеных выкарыстоўваюцца на працягу больш за 40 гадоў, павінна быць прычына. За гэтыя гады я патраціў сотні гадзін, каб па-сапраўднаму зразумець гэтыя дзіўныя чорныя скрыні, якія я выкарыстоўваю кожны дзень. Рэляцыйныя базы дадзеных вельмі цікавыя, таму што яны заснаваныя на карысных і шматразова выкарыстоўваных канцэпцыях. Калі вас цікавіць разуменне базы дадзеных, але ў вас ніколі не было часу ці жадання капацца ў гэтай шырокай тэме, вам павінен спадабацца гэты артыкул.

Хоць назва гэтага артыкула з'яўляецца відавочным, мэта гэтага артыкула не ў тым, каб зразумець, як выкарыстоўваць базу дадзеных. Такім чынам, вы ўжо павінны ведаць, як напісаць просты запыт злучэння і базавыя запыты СЫРЫ; інакш вы можаце не зразумець гэты артыкул. Гэта адзінае, што вам трэба ведаць, я растлумачу ўсё астатняе.

Пачну з некаторых асноў кампутарных навук, такіх як часавая складанасць алгарытмаў (BigO). Я ведаю, што некаторыя з вас ненавідзяць гэтую канцэпцыю, але без яе вы не зможаце зразумець тонкасці ўнутры базы дадзеных. Паколькі гэта вялізная тэма, я засяроджуся на тым, што лічу важным: як база дадзеных апрацоўвае SQL запыт. Я прадстаўлю толькі асноўныя канцэпцыі базы даных, Каб у канцы артыкула вы мелі ўяўленне аб тым, што адбываецца пад капотам.

Паколькі гэта доўгі і тэхнічны артыкул, якая ўключае ў сябе мноства алгарытмаў і структур дадзеных, не спяшайцеся, каб прачытаць яе. Некаторыя канцэпцыі могуць быць складаныя для разумення; вы можаце прапусціць іх і ўсё роўна атрымаць агульнае ўяўленне.

Для больш дасведчаных з вас, гэты артыкул падзелена на 3 часткі:

Агляд нізкаўзроўневых і высокаўзроўневых кампанентаў базы даных
Агляд працэсу аптымізацыі запытаў
Агляд кіравання транзакцыямі і буферным пулам

Вяртаючыся да асноў

Шмат гадоў таму (у далёкай, далёкай галактыцы…), распрацоўшчыкі павінны былі дакладна ведаць колькасць аперацый, якія яны кадзіравалі. Яны ведалі на памяць свае алгарытмы і структуры дадзеных, таму што не маглі дазволіць сабе марнаваць ЦП і памяць сваіх марудных кампутараў.

У гэтай частцы я нагадаю вам аб некаторых з гэтых канцэпцый, паколькі яны неабходныя для разумення базы дадзеных. Я таксама ўвяду паняцце індэкса базы даных.

O(1) vs O(n2)

У цяперашні час многія распрацоўшчыкі не клапоцяцца аб часовай складанасці алгарытмаў … і яны маюць рацыю!

Але калі вы маеце справу з вялікай колькасцю дадзеных (я не кажу пра тысячы) ці калі вы змагаецеся за мілісекунды, становіцца крытычна важным зразумець гэтую канцэпцыю. І як вы разумееце, базы дадзеных павінны мець справу з абедзвюма сітуацыямі! Я не прымушу вас патраціць больш часу, чым неабходна каб ухапіць сутнасць. Гэта дапаможа нам пазней зразумець канцэпцыю аптымізацыі на аснове затрат (каштаваць заснаваны аптымізацыя).

Канцэпцыя

Часавая складанасць алгарытму выкарыстоўваецца, каб убачыць колькі часу зойме выкананне алгарытму для дадзенага аб'ёму дадзеных. Каб апісаць гэтую складанасць, выкарыстоўваюць матэматычныя абазначэнні вялікіх О. Гэтая натацыя выкарыстоўваецца з функцыяй, якая апісвае, колькі аперацый трэба алгарытму для зададзенай колькасці ўваходных дадзеных.

Напрыклад, калі я кажу "гэты алгарытм мае складанасць O (some_function() )", гэта азначае, што для апрацоўкі вызначанага аб'ёму дадзеных алгарытму патрабуецца 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 000 аперацый
Алгарытм O (n * log (n)) абыйдзецца вам у 14 000 аперацый
Алгарытм O (n2) абыйдзецца вам у 4 000 000 аперацый

Розніца паміж O(1) і O(n2) здаецца вялікі (4 мільёны аперацый) але вы страціце максімум 2 мс, проста час міргнуць вачыма. Сапраўды, сучасныя працэсары могуць апрацоўваць сотні мільёнаў аперацый у секунду. Вось чаму прадукцыйнасць і аптымізацыя не з'яўляюцца праблемай у шматлікіх ІТ-праектах.

Як я ўжо сказаў, па-ранейшаму важна ведаць гэтую канцэпцыю пры працы з вялікай колькасцю дадзеных. Калі на гэты раз алгарытм павінен апрацаваць 1 элементаў (што не так ужо шмат для базы дадзеных):

Алгарытм O (1) абыдзецца вам у 1 аперацыю
Алгарытм O (log (n)) абыдзецца вам у 14 аперацый
Алгарытм O(n) абыдзецца вам у 1 000 000 аперацый
Алгарытм O (n * log (n)) абыйдзецца вам у 14 аперацый
Алгарытм O (n2) абыдзецца вам у 1 000 000 000 000 аперацый

Я не рабіў разлікаў, але я б сказаў, што з дапамогай алгарытму O (n2) у вас ёсць час выпіць кавы (нават два!). Калі вы дадасце яшчэ 0 да аб'ёму дадзеных, у вас будзе час, каб задрамаць.

Ідзем глыбей

Для даведкі:

Пошук у добрай хэш-табліцы знаходзіць элемент за O (1).
Пошук у добра збалансаваным дрэве дае вынік за O (log (n)).
Пошук у масіве дае вынік за O(n).
Лепшыя алгарытмы сартавання маюць складанасць O(n*log(n)).
Дрэнны алгарытм сартавання мае складанасць O (n2).

Нататка: у наступных частках мы ўбачым гэтыя алгарытмы і структуры дадзеных.

Ёсць некалькі тыпаў часовай складанасці алгарытму:

сцэнар сярэдняга выпадку
лепшы варыянт развіцця падзей
і горшы сцэнар

Часавая складанасць часта з'яўляецца найгоршым сцэнарам.

Я казаў толькі аб часовай складанасці алгарытму, але складанасць таксама дастасавальная для:

спажывання памяці алгарытмам
спажывання дыскавага ўводу / вываду алгарытмам

Вядома, ёсць складанасці горш, чым n2, напрыклад:

n4: гэта жудасна! Некаторыя са згаданых алгарытмаў маюць такую складанасць.
3n: гэта яшчэ горш! Адзін з алгарытмаў, якія мы ўбачым у сярэдзіне гэтага артыкула, мае гэтую складанасць (і ён сапраўды выкарыстоўваецца ў шматлікіх базах дадзеных).
факторыял n: вы ніколі не атрымаеце свае вынікі нават з невялікай колькасцю дадзеных.
nn: калі вы сутыкнецеся з гэтай складанасцю, вы павінны спытаць сябе, ці сапраўды гэта ваша сфера дзейнасці …

Заўвага: я даў вам не рэальнае вызначэнне абазначэння "вялікі О", а проста ідэю. Вы можаце прачытаць гэты артыкул у Вікіпедыі для рэальнага (асімптатычнага) вызначэння.

MergeSort (Сартаванне зліццём)

Што вы робіце, калі вам трэба адсартаваць калекцыю? Што? Вы выклікаеце функцыю sort ()… Ок, добры адказ… Але для базы дадзеных вы павінны разумець, як працуе гэтая функцыя sort ().

Існуе некалькі добрых алгарытмаў сартавання, таму я спынюся на найважнейшым: сартаванні зліццём. Магчыма, вы зараз не разумееце, чаму сартаванне дадзеных карысная, але вы павінны будзеце зразумець, пасля часткі прысвечанай аптымізацыі запытаў. Больш за тое, разуменне сартавання зліццём дапаможа нам пазней зразумець агульную аперацыю join баз дадзеных, званую зліццё далучыцца (аб'яднанне зліццём).

Merge (зліццё)

Як і многія карысныя алгарытмы, сартаванне зліццём заснавана на хітрасці: аб'яднанне 2 адсартаваных масіваў памеру N / 2 у N-элементны адсартаваны масіў варта ўсяго N аперацый. Гэтая аперацыя называецца зліццём.

Давайце паглядзім, што гэта значыць на простым прыкладзе:

На гэтым малюнку відаць, што для пабудовы канчатковага адсартаванага масіва з 8 элементаў вам трэба ўсяго толькі выканаць ітэрацыю адзін раз у 2х 4-элементных масівах. Паколькі абодва 4-элементных масіва ўжо адсартаваны:

1) вы параўноўваеце абодва бягучых элемента ў двух масівах (у пачатку бягучы = першаму)
2) затым вазьміце найменшы, каб змясціць яго ў масіў з 8 элементаў
3) і пераходзіце да наступнага элемента ў масіве, дзе вы ўзялі самы маленькі элемент
і паўтарайце 1,2,3, пакуль не дойдзеце да апошняга элемента аднаго з масіваў.
Затым вы бераце астатнія элементы іншага масіва, каб змясціць іх у масіў з 8 элементаў.

Гэта працуе, таму што абодва 4-элементных масіва адсартаваны, і таму вам не трэба «вяртацца» у гэтых масівах.

Цяпер, калі мы зразумелі гэты трук, вось мой псеўдакод для merge:

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;

Сартаванне зліццём разбівае задачу на меншыя задачы, а затым знаходзіць вынікі меншых задач, каб атрымаць вынік зыходнай задачы (нататка: гэты від алгарытмаў завецца падзяляй і пануй). Калі вы не разумееце гэты алгарытм, не хвалюйцеся; я не зразумеў гэтага ў першы раз, калі ўбачыў. Калі гэта можа дапамагчы вам, я бачу гэты алгарытм як двухфазны алгарытм:

Фаза дзялення, дзе масіў дзеліцца на меншыя масівы.
Фаза сартавання, дзе маленькія масівы аб'ядноўваюцца (выкарыстоўваючы аб'яднанне), каб сфарміраваць большы масіў.

Division phase (фаза дзялення)

На этапе дзялення масіў дзеліцца на унітарныя масівы за 3 крокі. Фармальная колькасць крокаў - log (N) (паколькі N = 8, log (N) = 3).

Адкуль я гэта ведаю?

Я геній! Адным словам - матэматыка. Ідэя складаецца ў тым, што кожны крок дзеліць памер зыходнага масіва на 2. Колькасць крокаў - гэта колькасць разоў, якое вы можаце падзяліць зыходны масіў на два. Гэта дакладнае азначэнне лагарыфма (з падставай 2).

Sorting phase (Фаза сартавання)

На этапе сартавання вы пачынаеце з унітарных (аднаэлементных) масіваў. На працягу кожнага этапу вы ўжываеце некалькі аперацый зліцця, і агульны кошт складае N = 8 аперацый:

На першым этапе ў вас ёсць 4 зліцця, якія стаяць 2 аперацыі кожны
На другім кроку ў вас ёсць 2 зліцця, якія стаяць 4 аперацыі кожны
На трэцім кроку ў вас ёсць 1 зліццё, якое каштуе 8 аперацый

Паколькі існуе log (N) крокаў, агульны кошт N * log(N) аперацый.

Перавагі merge sort

Чаму гэты алгарытм такі магутны?

Таму што:

Вы можаце змяніць яго, каб паменшыць аб'ём памяці, такім чынам, каб вы не стваралі новыя масівы, а непасрэдна змянялі ўваходны масіў.

Заўвага: гэты від алгарытмаў называецца in-месца (сартаванне без дадатковай памяці).

Вы можаце змяніць яго для адначасовага выкарыстання дыскавай прасторы і невялікага аб'ёму памяці без значных выдаткаў на дыскавы ўвод/вывад. Ідэя складаецца ў тым, каб загружаць у памяць толькі тыя часткі, якія ў дадзены момант апрацоўваюцца. Гэта важна, калі вам трэба адсартаваць табліцу памерам у некалькі гігабайт толькі з буферам памяці аб'ёмам 100 мегабайт.

Заўвага: гэты від алгарытмаў называецца знешняя сартаванне.

Вы можаце змяніць яго для запуску на некалькіх працэсах / патоках / серверах.

Напрыклад, размеркаванае сартаванне зліццём з'яўляецца адным з ключавых кампанентаў. Hadoop (які з'яўляецца структурай у вялікіх дадзеных).

Гэты алгарытм можа ператварыць свінец у золата (праўда!).

Гэты алгарытм сартавання выкарыстоўваецца ў большасці (калі не ва ўсіх) базах дадзеных, але ён не адзіны. Калі вы хочаце даведацца больш, вы можаце прачытаць гэтую даследчую працу, Якая абмяркоўвае плюсы і мінусы агульных алгарытмаў сартавання ў базе дадзеных.

Масіў, Дрэва і Хэш-табліца

Цяпер, калі мы разумеем ідэю часовай складанасці і сартавання, я павінен расказаць вам аб 3 структурах дадзеных. Гэта важна, таму што яны з'яўляюцца асновай сучасных баз даных. Я таксама ўвяду паняцце індэкса базы даных.

масіў

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

Гэты 2-мерны масіў уяўляе сабой табліцу з радкамі і слупкамі:

Кожны радок уяўляе сутнасць
Стоўбцы захоўваюць уласцівасці, якія апісваюць сутнасць.
Кожны слупок захоўвае дадзеныя вызначанага тыпу (integer, string, date…).

Так зручна захоўваць і візуалізаваць дадзеныя аднак, калі вам трэба знайсці пэўны значэнне, гэта не падыходзіць.

Напрыклад, калі вы хочаце знайсці ўсіх хлопцаў, якія працуюць у Вялікабрытаніі, вам трэба будзе прагледзець кожны радок, каб вызначыць, ці належыць гэты радок да Вялікабрытаніі. Гэта будзе каштаваць вам N аперацый, Дзе N - Колькасць радкоў, што нядрэнна, але ці можа быць больш хуткі шлях? Цяпер нам прыйшоў час пазнаёміцца з дрэвамі.

Нататка: большасць сучасных баз дадзеных падаюць пашыраныя масівы для эфектыўнага захоўвання табліц: heap-organizedtables і index-organizedtables. Але гэта не мяняе праблему хуткага пошуку пэўнай умовы ў групе слупкоў.

Дрэва і індэкс базы дадзеных

Двайковае дрэва пошуку - гэта двайковае дрэва са спецыяльнай уласцівасцю, ключ у кожным вузле павінен быць:

больш, чым усе ключы, якія захоўваюцца ў левым поддереве
менш за ўсіх ключоў, якія захоўваюцца ў правым поддереве

Давайце паглядзім, што гэта значыць візуальна

Ідэя

Гэта дрэва мае 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), не дрэнна!

Вяртаемся да нашай праблемы

Але гэта вельмі абстрактна, таму давайце вернемся да нашай праблемы. Замест простага integer, прадстаўце радок, якая прадстаўляе краіну кагосьці ў папярэдняй табліцы. Дапусцім, у вас ёсць дрэва, якое змяшчае поле "country" (column 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) вузлоў), што азначае меншае выкарыстанне дыска. Калі М мала (напрыклад, 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 няма элементаў. Рэальная задача - знайсці добрую хэш-функцыю, якая будзе ствараць сегменты, якія змяшчаюць вельмі невялікая колькасць элементаў.

У маім прыкладзе знайсці добрую хэш-функцыю лёгка. Але гэта просты прыклад, знайсці добрую хэш-функцыю складаней, калі ключ:

радок (напрыклад - прозвішча)
2 радкі (напрыклад - прозвішча і імя)
2 радкі і дата (напрыклад - прозвішча, імя і дата нараджэння)
...

З добрай хэш-функцыяй пошук у хэш-табліцы абыходзіцца ў O(1).

Масіў vs хэш-табліца

Чаму б не выкарыстоўваць масіў?

Хм, добрае пытанне.

Хэш-табліца можа быць часткова загружана ў памяць, а астатнія сегменты могуць заставацца на дыску.
З масівам вы павінны выкарыстоўваць бесперапыннае прастору ў памяці. Калі вы загружаеце вялікую табліцу вельмі складана знайсці дастаткова бесперапыннай прасторы.
Для хэш-табліцы вы можаце выбраць патрэбны ключ (напрыклад, краіну і прозвішча чалавека).

Для дадатковай інфармацыі, вы можаце прачытаць артыкул аб яваHashMap, якая з'яўляецца эфектыўнай рэалізацыяй хэш-табліцы; вам не трэба разумець Java, каб зразумець канцэпцыі, выкладзеныя ў гэтым артыкуле.

Крыніца: habr.com

Як працуюць рэляцыйныя базы дадзеных (Частка 1)