Эй Хабр! Назарларыңызға мақаланың аудармасын ұсынамын
«Реляциялық деректер базасы қалай жұмыс істейді».

Реляциялық дерекқорларға келетін болсақ, мен бірдеңе жетіспейді деп ойламаймын. Олар барлық жерде қолданылады. Шағын және пайдалы SQLite-тен қуатты Teradata-ға дейін көптеген түрлі дерекқорлар бар. Бірақ деректер базасының қалай жұмыс істейтінін түсіндіретін бірнеше мақалалар ғана бар. Нәтижелердің қаншалықты аз екенін көру үшін "howdoesarelationaldatabasework" арқылы өзіңізді іздей аласыз. Оның үстіне бұл мақалалар қысқа. Егер сіз ең соңғы шулы технологияларды (BigData, NoSQL немесе JavaScript) іздесеңіз, олардың қалай жұмыс істейтінін түсіндіретін тереңірек мақалаларды таба аласыз.

Реляциялық дерекқорлар университет курстарынан, ғылыми жұмыстардан және кітаптардан тыс түсіндіру үшін тым ескі және тым жалықтырарлық па?

Әзірлеуші ретінде мен түсінбейтін нәрсені пайдалануды жек көремін. Ал егер мәліметтер базасы 40 жылдан астам пайдаланылған болса, оның себебі болуы керек. Көптеген жылдар бойы мен күнделікті қолданатын осы біртүрлі қара жәшіктерді түсіну үшін жүздеген сағат жұмсадым. Реляциялық мәліметтер қоры өте қызықты, өйткені олар пайдалы және қайта пайдалануға болатын тұжырымдамаларға негізделген. Егер сіз дерекқорды түсінуге қызығушылық танытсаңыз, бірақ бұл кең тақырыпты зерттеуге ешқашан уақытыңыз немесе бейімділігіңіз болмаса, сізге бұл мақаланы ұнату керек.

Бұл мақаланың тақырыбы анық болғанымен, бұл мақаланың мақсаты дерекқорды қалай пайдалану керектігін түсіну емес. сондықтан, қарапайым қосылу сұрауын және негізгі сұрауларды қалай жазу керектігін білуіңіз керек RAW; әйтпесе бұл мақаланы түсінбеуіңіз мүмкін. Бұл сізге білу керек жалғыз нәрсе, қалғанын түсіндіремін.

Мен алгоритмдердің уақыт күрделілігі (BigO) сияқты информатика негіздерінен бастаймын. Мен сіздердің кейбіреулеріңіз бұл тұжырымдаманы жек көретінін білемін, бірақ онсыз сіз дерекқордағы күрделі мәселелерді түсіне алмайсыз. Бұл үлкен тақырып болғандықтан, мен назар аударамын маңызды деп санаймын: деректер қоры қалай өңделеді SQL сұрау. Мен жай таныстырамын мәліметтер базасы туралы негізгі түсініктермақаланың соңында сізде капюшонның астында не болып жатқаны туралы түсінік болады.

Бұл көптеген алгоритмдер мен деректер құрылымдарын қамтитын ұзақ және техникалық мақала болғандықтан, оны оқып шығуға уақыт бөліңіз. Кейбір ұғымдарды түсіну қиын болуы мүмкін; сіз оларды өткізіп жіберіп, жалпы идеяны ала аласыз.

Араларыңызда неғұрлым білімді адамдар үшін бұл мақала 3 бөлікке бөлінген:

Төмен деңгейлі және жоғары деңгейлі мәліметтер базасының құрамдастарына шолу
Сұрауды оңтайландыру процесіне шолу
Транзакцияға және буфер пулын басқаруға шолу

Негіздерге оралу

Бірнеше жыл бұрын (алыс, алыс галактикада...) әзірлеушілер кодтап жатқан операциялардың нақты санын білуі керек еді. Олар өздерінің алгоритмдері мен деректер құрылымдарын жатқа білді, өйткені олар баяу компьютерлерінің процессоры мен жадын босқа жұмсай алмады.

Бұл бөлімде мен сізге осы ұғымдардың кейбірін еске саламын, өйткені олар дерекқорды түсіну үшін өте маңызды. Мен де тұжырымдамамен таныстырамын деректер қорының индексі.

O(1) қарсы O(n2)

Қазіргі уақытта көптеген әзірлеушілер алгоритмдердің уақыттық күрделілігіне мән бермейді... және олар дұрыс!

Бірақ сіз көптеген деректермен айналысқанда (мен мыңдаған деп айтпаймын) немесе миллисекундтарда күресіп жатсаңыз, бұл тұжырымдаманы түсіну маңызды болады. Сіз ойлағандай, дерекқорлар екі жағдайды да шешуі керек! Мен сізге мәселені түсіну үшін қажет болғаннан артық уақыт жұмсамаймын. Бұл кейінірек шығындарға негізделген оңтайландыру тұжырымдамасын түсінуге көмектеседі (құны негізделген оңтайландыру).

Тұжырымдама

Алгоритмнің уақыттық күрделілігі алгоритмнің берілген деректер көлемін орындауға қанша уақыт кететінін көру үшін пайдаланылады. Бұл күрделілікті сипаттау үшін біз үлкен O математикалық белгісін қолданамыз.Бұл белгі алгоритмге берілген кіріс саны үшін қанша амал қажет екенін сипаттайтын функциямен қолданылады.

Мысалы, мен «бұл алгоритмнің күрделілігі O(кейбір_функция())» десем, бұл алгоритм деректердің белгілі бір көлемін өңдеу үшін кейбір_функция(а_белгілі_мәліметтер_сомасы) операцияларын қажет ететінін білдіреді.

Бола тұра Деректер саны маңызды емес**, әйтпесе ** деректер көлемінің ұлғаюымен операциялар саны қалай артады. Уақыттың күрделілігі операциялардың нақты санын қамтамасыз етпейді, бірақ орындалу уақытын бағалаудың жақсы тәсілі.

Бұл графикте алгоритм уақытының күрделілігінің әртүрлі түрлері үшін кіріс деректерінің көлеміне қарсы операциялардың санын көруге болады. Оларды көрсету үшін логарифмдік шкала қолдандым. Басқаша айтқанда, деректер көлемі 1 миллиардтан 1 миллиардқа дейін тез артады.Біз мынаны көреміз:

O(1) немесе тұрақты күрделілік тұрақты болып қалады (әйтпесе оны тұрақты күрделілік деп атамас еді).
O(журнал(n)) миллиардтаған деректердің өзінде төмен болып қалады.
Ең қиын қиындық - О(n2), мұндағы операциялар саны тез өседі.
Қалған екі асқыну да дәл осылай тез өседі.

мысалдар

Деректер көлемінің аздығымен O(1) және O(n2) арасындағы айырмашылық шамалы. Мысалы, сізде 2000 элементті өңдеу қажет алгоритм бар делік.

O(1) алгоритмі сізге 1 операцияны қажет етеді
O(log(n)) алгоритмі сізге 7 операцияны қажет етеді
O(n) алгоритмі сізге 2 операцияны қажет етеді
O(n*log(n)) алгоритмі сізге 14 операцияны қажет етеді
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).

Ескерту: Келесі бөліктерде біз осы алгоритмдер мен деректер құрылымдарын көреміз.

Алгоритм уақытының күрделілігінің бірнеше түрі бар:

орташа жағдай сценарийі
ең жақсы жағдай сценарийі
және ең нашар жағдай сценарийі

Уақыттың күрделілігі көбінесе ең нашар сценарий болып табылады.

Мен тек алгоритмнің уақыттық күрделілігі туралы айттым, бірақ күрделілік мыналарға да қатысты:

алгоритмнің жадты тұтынуы
дискінің енгізу/шығаруын тұтыну алгоритмі

Әрине, n2-ден де нашар асқынулар бар, мысалы:

n4: бұл қорқынышты! Аталмыш алгоритмдердің кейбірінде осындай күрделілік бар.
3n: бұл одан да жаман! Осы мақаланың ортасында көретін алгоритмдердің бірінде бұл күрделілік бар (және ол көптеген дерекқорларда қолданылады).
факторлық n: тіпті шағын деректер көлемімен де нәтижелерді ешқашан ала алмайсыз.
nn: Егер сіз осы күрделілікке тап болсаңыз, бұл шынымен сіздің қызмет саласыңыз ба деп өзіңізден сұраңыз ...

Ескерту: Мен сізге үлкен O белгісінің нақты анықтамасын берген жоқпын, жай ғана идея. Бұл мақаланы мына жерден оқи аласыз Уикипедия нақты (ассимптотикалық) анықтама үшін.

MergeSort

Топтаманы сұрыптау қажет болғанда не істейсіз? Не? Сіз sort() функциясын шақырасыз... Жарайды, жақсы жауап... Бірақ дерекқор үшін бұл sort() функциясының қалай жұмыс істейтінін түсінуіңіз керек.

Бірнеше жақсы сұрыптау алгоритмдері бар, сондықтан мен ең маңыздыларына тоқталамын: біріктіру сұрыптау. Дәл қазір деректерді сұрыптау неліктен пайдалы екенін түсінбеуіңіз мүмкін, бірақ сұрауды оңтайландыру бөлімінен кейін қажет. Сонымен қатар, біріктіру сұрыптауын түсіну бізге кейінірек деп аталатын жалпы дерекқорды біріктіру операциясын түсінуге көмектеседі қосылу Қосылу (біріктіру қауымдастығы).

Біріктіру

Көптеген пайдалы алгоритмдер сияқты біріктіру сұрыптауы трюкке сүйенеді: N/2 өлшемді 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) қадамдар болғандықтан, жалпы құны Н * log(N) операциялары.

Біріктіру сұрыптауының артықшылықтары

Неліктен бұл алгоритм соншалықты күшті?

Себебі:

Жаңа массивтер жасамай, кіріс массивін тікелей өзгерту үшін жад ізін азайту үшін оны өзгертуге болады.

Ескерту: алгоритмнің бұл түрі деп аталады in-орын (қосымша жадысыз сұрыптау).

Сіз оны дискілік енгізу-шығару шығынынсыз бір уақытта дискілік кеңістік пен шағын жад көлемін пайдалану үшін өзгерте аласыз. Идеясы жадқа тек қазіргі уақытта өңделіп жатқан бөліктерді жүктеу болып табылады. Бұл тек 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, түйін бар. Мен жолдың идентификаторын түйін ішіндегі (суретте көрсетілмеген) шығарып аламын және берілген жол идентификаторын кестеден іздеймін.
Жол идентификаторын білу маған деректердің кестеде қай жерде екенін білуге мүмкіндік береді, сондықтан мен оны бірден шығарып аламын.

Ақырында, екі іздеу де маған ағаштың ішіндегі деңгейлер санына жетеді. Біріктіру сұрыптау бөлімін мұқият оқысаңыз, log(N) деңгейлері бар екенін көруіңіз керек. Шықты, іздеу шығындарының журналы(N), жаман емес!

Мәселемізге оралайық

Бірақ бұл өте дерексіз, сондықтан өз мәселемізге қайта оралайық. Қарапайым бүтін санның орнына алдыңғы кестедегі біреудің елін көрсететін жолды елестетіңіз. Кестенің «ел» өрісін (3-баған) қамтитын ағаш бар делік:

Ұлыбританияда кім жұмыс істейтінін білгіңіз келсе
Сіз Ұлыбританияны білдіретін түйінді алу үшін ағашқа қарайсыз
«UKnode» ішінде сіз Ұлыбританиядағы жұмысшылардың жазбаларының орнын таба аласыз.

Массивті тікелей пайдалансаңыз, бұл іздеу N әрекеттің орнына журнал(N) операцияларын талап етеді. Сіз жаңа ғана ұсынған нәрсе болды деректер қорының индексі.

Сіз кез келген өрістер тобына (жол, сан, 2 жол, сан және жол, күн...) индекс ағашын құра аласыз, егер сізде пернелерді (яғни өріс топтары) салыстыру функциясы болса, осылайша орнатуға болады. кілттердің арасында тапсырыс беріңіз (бұл дерекқордағы кез келген негізгі түрлерге қатысты).

B+TreeIndex

Бұл ағаш белгілі бір мәнді алу үшін жақсы жұмыс істегенімен, қажет кезде ҮЛКЕН мәселе бар екі мән арасында бірнеше элементтерді алу. Бұл O(N) тұрады, себебі сіз ағаштың әрбір түйінін қарап, оның осы екі мәннің арасында екенін тексеруіңіз керек (мысалы, ағаштың реттелген өтуімен). Сонымен қатар, бұл операция дискіге енгізу-шығару үшін қолайлы емес, өйткені сіз бүкіл ағашты оқуыңыз керек. Біз тиімді орындаудың жолын табуымыз керек ауқымды сұрау. Бұл мәселені шешу үшін қазіргі дерекқорлар B+Tree деп аталатын алдыңғы ағаштың өзгертілген нұсқасын пайдаланады. B + ағаш ағашында:

тек ең төменгі түйіндер (жапырақтар) ақпаратты сақтау (қатысты кестедегі жолдардың орналасуы)
қалған түйіндер осында маршруттау үшін дұрыс түйінге іздеу кезінде.

Көріп отырғаныңыздай, мұнда көбірек түйіндер бар (екі есе). Шынында да, сізде дұрыс түйінді (байланысты кестедегі жолдардың орналасуын сақтайтын) табуға көмектесетін қосымша түйіндер, «шешім түйіндері» бар. Бірақ іздеудің күрделілігі бұрынғысынша O(log(N)) (тағы бір ғана деңгей бар). Үлкен айырмашылық сонда төменгі деңгейдегі түйіндер олардың мұрагерлерімен байланысады.

Осы B+ Tree көмегімен 40 пен 100 арасындағы мәндерді іздесеңіз:

Алдыңғы ағаштағыдай 40-ты (немесе 40 жоқ болса, 40-тан кейінгі ең жақын мәнді) іздеу керек.
Содан кейін 40-ге жеткенше тікелей мұрагер сілтемелерін пайдаланып 100 мұрагерді жинаңыз.

Айталық, сіз M мұрагерлерін таптыңыз және ағашта N түйін бар. Арнайы түйінді табу алдыңғы ағаш сияқты журналға (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).

Массив пен хэш кестесі

Неліктен массив пайдаланбасқа?

Хмм, жақсы сұрақ.

Хэш кестесі болуы мүмкін жадқа ішінара жүктеледі, ал қалған сегменттер дискіде қалуы мүмкін.
Массивпен жадта іргелес кеңістікті пайдалану керек. Егер сіз үлкен үстелді жүктеп жатсаңыз жеткілікті үздіксіз кеңістікті табу өте қиын.
Хэш кестесі үшін қажетті кілтті таңдауға болады (мысалы, ел мен адамның тегі).

Қосымша ақпарат алу үшін сіз туралы мақаланы оқи аласыз JavaHashMap, бұл хэш кестесін тиімді жүзеге асыру; осы мақалада қарастырылатын ұғымдарды түсіну үшін Java тілін түсінудің қажеті жоқ.

Ақпарат көзі: www.habr.com

Реляциялық деректер қорлары қалай жұмыс істейді (1 бөлім)