Эй Хабр! Сиздердин назарыңыздарга макаланын котормосун сунуштайм
"Реляциялык маалымат базасы кантип иштейт".

Реляциялык маалымат базаларына келгенде мен бир нерсе жетишпей жатат деп ойлобойм. Алар бардык жерде колдонулат. Чакан жана пайдалуу SQLiteден күчтүү Teradataга чейин көптөгөн ар кандай маалымат базалары бар. Бирок маалымат базасы кантип иштээрин түшүндүргөн бир нече гана макалалар бар. Канчалык аз натыйжалар бар экенин көрүү үчүн "howdoesarelationaldatabasework" аркылуу өзүңүздү издесеңиз болот. Анын үстүнө, бул макалалар кыска. Эгер сиз эң акыркы ызылдаган технологияларды (BigData, NoSQL же JavaScript) издеп жатсаңыз, алардын кантип иштээрин түшүндүргөн тереңирээк макалаларды таба аласыз.

Реляциялык маалымат базалары университет курстарынан, илимий эмгектерден жана китептерден тышкары түшүндүрүү үчүн өтө эски жана кызыксызбы?

Иштеп чыгуучу катары мен түшүнбөгөн нерсени колдонууну жек көрөм. Ал эми маалымат базалары 40 жылдан ашык убакыттан бери колдонулуп келген болсо, анын себеби болушу керек. Жылдар бою мен күн сайын колдонгон бул кызыктай кара кутуларды түшүнүү үчүн жүздөгөн сааттарды короттум. Реляциялык маалымат базалары абдан кызыктуу, анткени алар пайдалуу жана көп жолу колдонулуучу түшүнүктөрдүн негизинде. Эгер сиз маалымат базасын түшүнгүңүз келсе, бирок бул кеңири теманы изилдөөгө эч качан убактыңыз же каалооңуз жок болсо, анда бул макаладан ырахат алыңыз.

Бул макаланын аталышы ачык болсо да, Бул макаланын максаты маалымат базасын кантип колдонууну түшүнүү эмес. Ошондуктан, сиз буга чейин эле жөнөкөй байланыш өтүнүчүн жана негизги суроо жазууну билиши керек RAW; антпесе бул макаланы түшүнбөй калышыңар мүмкүн. Сиз билишиңиз керек болгон бир гана нерсе, калганын түшүндүрүп берем.

Мен алгоритмдердин убакыттын татаалдыгы (BigO) сыяктуу информатиканын кээ бир негиздеринен баштайм. Мен билем, силердин кээ бириңер бул түшүнүктү жек көрөсүңөр, бирок ансыз сиз маалымат базасынын ичиндеги татаал нерселерди түшүнө албайсыз. Бул чоң тема болгондуктан, Мен көңүл бурам мен эмне маанилүү деп ойлойм: маалымат базасы кантип иштейт SQL справка. Мен жөн эле тааныштырайын базалык маалымат базасы түшүнүктөрүОшентип, макаланын аягында сиз капоттун астында эмне болуп жатканын түшүнөсүз.

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

Араңарда көбүрөөк билимдүү адамдар үчүн бул макала 3 бөлүккө бөлүнөт:

Төмөнкү жана жогорку деңгээлдеги маалыматтар базасынын компоненттерине сереп салуу
Сурамдарды оптималдаштыруу процессине сереп салуу
Транзакция жана буфердик пулду башкарууга сереп салуу

Негиздерге кайтуу

Бир нече жыл мурун (алыс, алыскы галактикада...) иштеп чыгуучулар коддоп жаткан операциялардын санын так билиши керек болчу. Алар өздөрүнүн алгоритмдерин жана берилиш структураларын жатка билишкен, анткени алар жай компьютерлеринин CPU жана эс тутумун текке кетире алышкан эмес.

Бул бөлүктө мен бул түшүнүктөрдүн кээ бирлерин эскертем, анткени алар маалымат базасын түшүнүү үчүн зарыл. Мен дагы концепция менен тааныштырам маалымат базасы индекси.

O(1) vs O(n2)

Бүгүнкү күндө көптөгөн иштеп чыгуучулар алгоритмдердин убакыттын татаалдыгына маани беришпейт... жана алар туура!

Бирок сиз көп маалыматтар менен (мен миңдегендерди айтып жаткан жокмун) же миллисекунддор менен күрөшүп жатсаңыз, бул түшүнүктү түшүнүү маанилүү болуп калат. Жана сиз элестете тургандай, маалымат базалары эки жагдайды тең чечиши керек! Мен сизди кепти түшүнүү үчүн зарыл болгондон ашык убакыт коротпойм. Бул кийинчерээк чыгымдарга негизделген оптималдаштыруу түшүнүгүн түшүнүүгө жардам берет (нарк негизделген оптималдаштыруу).

түшүнүк

Алгоритмдин убакыттын татаалдыгы алгоритм белгилүү бир көлөмдөгү маалымат үчүн канча убакытта бүтөөрүн көрүү үчүн колдонулат. Бул татаалдыкты сүрөттөө үчүн биз чоң O математикалык белгини колдонобуз.Бул белги алгоритмге берилген сандагы киргизүүлөр үчүн канча операция керек экендигин сүрөттөгөн функция менен колдонулат.

Мисалы, мен "бул алгоритмдин татаалдыгы O(some_function())" десем, бул алгоритм белгилүү бир көлөмдөгү маалыматтарды иштеп чыгуу үчүн кээ бир_функция(а_белгилүү_маалыматтардын_суммасы) операцияларын талап кылат дегенди билдирет.

Ошентип, Маанилүү маалымат көлөмү эмес**, болбосо ** маалымат көлөмүнүн өсүшү менен операциялардын саны кантип көбөйөт. Убакыттын татаалдыгы операциялардын так санын бербейт, бирок аткаруу убактысын эсептөөнүн жакшы жолу.

Бул графикте сиз алгоритмдик убакыттын татаалдыгынын ар кандай түрлөрү үчүн киргизилген маалыматтардын көлөмүнө каршы операциялардын санын көрө аласыз. Мен аларды көрсөтүү үчүн логарифмдик шкаланы колдондум. Башкача айтканда, маалыматтардын көлөмү 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 мс жоготосуз, жөн гана көзүңүздү ирмеп коюуга убакыт кетет. Чынында эле, заманбап процессорлор иштете алат секундасына жүз миллиондогон операциялар. Ошондуктан көптөгөн IT долбоорлорунда аткаруу жана оптималдаштыруу маселе эмес.

Мен айткандай, чоң көлөмдөгү маалыматтар менен иштөөдө бул түшүнүктү билүү дагы эле маанилүү. Эгерде бул жолу алгоритм 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: Эгер сиз бул татаалдыкка туш болсоңуз, анда бул чындап эле сиздин ишмердүүлүк чөйрөңүзбү деп ойлонуп көрүңүз...

Эскертүү: Мен сизге чоң О белгисинин чыныгы аныктамасын берген жокмун, жөн гана идея. Сиз бул макаланы окуй аласыз Wikipedia реалдуу (ассимптотикалык) аныктама үчүн.

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 маалымат структурасы жөнүндө айтып беришим керек. Бул маанилүү, анткени алар заманбап маалымат базаларынын негизи болуп саналат. Мен дагы концепция менен тааныштырам маалымат базасы индекси.

Array

Эки өлчөмдүү массив эң жөнөкөй маалымат структурасы. Таблицаны массив катары кароого болот. Мисалы:

Бул 2 өлчөмдүү массив саптар жана мамычалардан турган таблица:

Ар бир сап бир нерсени билдирет
Мамычалар объектти сүрөттөгөн касиеттерди сактайт.
Ар бир тилке белгилүү бир типтеги маалыматтарды (бүтүн, сап, дата...) сактайт.

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

Мисалы, эгер сиз Улуу Британияда иштеген бардык балдарды тапкыңыз келсе, анда ал катар Улуу Британияга таандык экенин аныктоо үчүн ар бир катарды карап чыгышыңыз керек. Бул сизге 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 операциянын ордуна log(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 түйүнү бар дейли. Белгилүү бир түйүндү табуу мурунку дарак сыяктуу журналга (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)) операциясын колдонуу менен таблицанын индекстерин жаңыртышы керек. Мындан тышкары, индекстерди кошуу көбүрөөк жумуш жүгүн билдирет транзакция менеджери (макаланын аягында баяндалат).

Көбүрөөк маалымат алуу үчүн, сиз Wikipedia макаласын көрө аласыз B+дарак. Эгерде сиз маалымат базасында B+Treeди ишке ашыруунун мисалын кааласаңыз, карап көрүңүз бул макалада и бул макалада алдыңкы MySQL иштеп чыгуучусунан. Экөө тең InnoDB (MySQL кыймылдаткычы) индекстерди кантип иштетээрине көңүл бурушат.

Эскертүү: Окурман мага төмөнкү деңгээлдеги оптималдаштыруудан улам B+ дарагы толугу менен тең салмактуу болушу керектигин айтты.

Hashtable

Биздин акыркы маанилүү маалымат структурасы хэш таблицасы болуп саналат. Бул сиз баалуулуктарды тез издегиңиз келгенде абдан пайдалуу. Андан тышкары, хэш таблицасын түшүнүү бизге кийинчерээк хэш кошулуу деп аталган жалпы маалымат базасын бириктирүү операциясын түшүнүүгө жардам берет ( хэш кошулуу). Бул маалымат структурасы кээ бир ички нерселерди сактоо үчүн маалымат базасы тарабынан да колдонулат (мис. кулпу үстөл же буфердик бассейн, биз бул эки түшүнүктү кийинчерээк көрөбүз).

Хэш таблицасы - бул элементти ачкычы менен тез таба турган маалымат структурасы. Хэш таблицасын түзүү үчүн сиз төмөнкүлөрдү аныкташыңыз керек:

ачкыч элементтериңиз үчүн
хэш функциясы ачкычтар үчүн. Эсептелген ачкыч хэштери элементтердин жайгашкан жерин берет (деп аталат сегменттер ).
баскычтарды салыштыруу функциясы. Туура сегментти тапкандан кийин, ушул салыштыруу аркылуу сегменттин ичинде издеп жаткан элементти табышыңыз керек.

Жөнөкөй мисал

Келгиле, ачык мисалды алалы:

Бул хэш таблицасы 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 түшүнүүнүн кереги жок.

Source: www.habr.com

Реляциялык маалымат базалары кантип иштейт (1-бөлүк)