Салом, Хабр! Ман ба диққати шумо тарҷумаи мақоларо пешкаш мекунам
"Чӣ гуна пойгоҳи додаҳои релятсионӣ кор мекунад".

Вақте ки сухан дар бораи пойгоҳи додаҳои релятсионӣ меравад, ман наметавонам фикр кунам, ки чизе намерасад. Онҳо дар ҳама ҷо истифода мешаванд. Аз SQLite хурд ва муфид то Teradata пурқудрати пойгоҳи додаҳои гуногун мавҷуданд. Аммо танҳо якчанд мақолаҳо мавҷуданд, ки чӣ тавр кор кардани базаро шарҳ медиҳанд. Шумо метавонед худро бо истифода аз "howdoesarelationaldatabasework" ҷустуҷӯ кунед, то бубинед, ки чанд натиҷа вуҷуд дорад. Илова бар ин, ин мақолаҳо кӯтоҳанд. Агар шумо дар ҷустуҷӯи технологияҳои навтарини пурқувват бошед (BigData, NoSQL ё JavaScript), шумо мақолаҳои амиқи бештареро хоҳед ёфт, ки чӣ тавр онҳо кор мекунанд.

Оё пойгоҳи додаҳои релятсионӣ хеле кӯҳна ва хеле дилгиркунанда барои шарҳ додани берун аз курсҳои донишгоҳӣ, мақолаҳои илмӣ ва китобҳо?

Ҳамчун таҳиякунанда, ман аз истифодаи чизе, ки ман намефаҳмам, нафрат дорам. Ва агар базаи маълумотҳо зиёда аз 40 сол истифода шуда бошад, бояд сабабе дошта бошад. Дар тӯли солҳо, ман садҳо соатро сарф кардам, то воқеан дарк кардани ин қуттиҳои сиёҳи аҷибе, ки ман ҳамарӯза истифода мебарам. Пойгоҳи додаҳои релятсионӣ хеле ҷолиб, зеро онҳо дар асоси консепсияҳои муфид ва дубора истифодашаванда. Агар шумо ба фаҳмидани пойгоҳи додаҳо таваҷҷӯҳ дошта бошед, аммо ҳеҷ гоҳ вақт ё майл барои омӯхтани ин мавзӯи васеъ надошта бошед, шумо бояд аз ин мақола лаззат баред.

Гарчанде ки сарлавҳаи ин мақола равшан аст, Мақсади ин мақола фаҳмидани тарзи истифодаи базаи маълумот нест. Бинобар ин шумо бояд аллакай донед, ки чӣ гуна дархости оддии пайвастшавӣ ва дархостҳои асосиро нависед RAW; вагарна шумо ин мақоларо намефаҳмед. Ин ягона чизест, ки шумо бояд донед, ман боқимондаро шарҳ медиҳам.

Ман бо баъзе асосҳои илми информатика, ба монанди мураккабии вақти алгоритмҳо (BigO) оғоз мекунам. Ман медонам, ки баъзеи шумо ин консепсияро бад мебинанд, аммо бе он шумо нозукиҳои дохили базаро дарк карда наметавонед. Азбаски ин мавзӯи бузург аст, Ман тамаркуз мекунам он чизе ки ман фикр мекунам муҳим аст: базаи маълумот чи тавр кор мекунад SQL дархост. Ман танҳо муаррифӣ мекунам консепсияҳои асосии базаи маълумотто дар охири мақола шумо тасаввуроте дошта бошед, ки дар зери кулоҳ чӣ рӯй медиҳад.

Азбаски ин мақолаи дароз ва техникӣ аст, ки бисёр алгоритмҳо ва сохторҳои додаҳоро дар бар мегирад, вақти худро барои хондани он сарф кунед. Баъзе мафҳумҳоро фаҳмидан душвор буда метавонад; шумо метавонед онҳоро гузаред ва ба ҳар ҳол фикри умумиро ба даст оред.

Барои донишмандони бештари шумо, ин мақола ба 3 қисм тақсим мешавад:

Баррасии ҷузъҳои пойгоҳи додаҳои сатҳи паст ва баланд
Баррасии раванди оптимизатсияи дархост
Баррасии муомилот ва идоракунии ҳавзи буферӣ

Бозгашт ба асосҳо

Солҳо пеш (дар галактикаи дур, дур...) таҳиягарон бояд миқдори амалиётҳоеро, ки рамзгузорӣ мекарданд, медонистанд. Онҳо алгоритмҳо ва сохторҳои додаҳои худро аз ёд медонистанд, зеро онҳо наметавонистанд CPU ва хотираи компютерҳои сусти худро сарф кунанд.

Дар ин қисм, ман ба шумо баъзе аз ин мафҳумҳоро хотиррасон мекунам, зеро онҳо барои фаҳмидани пойгоҳи додаҳо муҳиманд. Ман инчунин консепсияро муаррифӣ мекунам индекси пойгоҳи додаҳо.

O(1) против O(n2)

Имрӯзҳо, бисёре аз таҳиягарон ба мураккабии вақти алгоритмҳо аҳамият намедиҳанд ... ва онҳо дурустанд!

Аммо вақте ки шумо бо маълумоти зиёд кор карда истодаед (ман ҳазорон нафарро намегӯям) ё агар шумо дар миллисонияҳо мубориза баред, фаҳмидани ин консепсия муҳим мегардад. Ва тавре ки шумо тасаввур карда метавонед, пойгоҳи додаҳо бояд бо ҳарду ҳолат мубориза баранд! Ман шуморо водор намекунам, ки барои фаҳмидани нуқтаи зарурӣ вақти зиёдтар сарф кунед. Ин ба мо кӯмак мекунад, ки консепсияи оптимизатсия дар асоси хароҷотро дертар фаҳмем (арзиш дар асоси оптимизатсия).

Консепсия

Мушкилии вақти алгоритм истифода бурда мешавад, то бубинад, ки алгоритм барои миқдори додаи маълумот чӣ қадар вақт мегирад. Барои тавсифи ин мураккабӣ мо аломати бузурги математикии O-ро истифода мебарем.Ин нишона бо функсияе истифода мешавад, ки алгоритм барои миқдори додаи воридот чанд амалиёт лозим аст.

Масалан, вақте ки ман мегӯям, ки "ин алгоритм дорои мураккабии 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 амалиётро талаб мекунад
Алгоритми 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 амалиётро талаб мекунад

Ман математикаро иҷро накардаам, аммо ман мегӯям, ки бо алгоритми O(n2) шумо барои нӯшидани қаҳва (ҳатто ду!) вақт доред. Агар шумо ба ҳаҷми маълумот 0-и дигар илова кунед, шумо барои хоб кардан вақт хоҳед дошт.

Биёед амиқтар равем

Барои баррасӣ:

Ҷустуҷӯи хуби ҷадвали hash як элементро дар O(1) пайдо мекунад.
Ҷустуҷӯи дарахти хуб мутавозин натиҷаҳоро дар O(log(n)) медиҳад.
Ҷустуҷӯи массив натиҷаҳоро дар O(n) медиҳад.
Беҳтарин алгоритмҳои ҷудокунӣ мураккабии O(n*log(n)) доранд.
Алгоритми ҷудокунии бад дорои мураккабии O(n2) мебошад.

Эзоҳ: Дар қисмҳои зерин мо ин алгоритмҳо ва сохторҳои додаҳоро мебинем.

Якчанд намуди мураккабии вақти алгоритм вуҷуд дорад:

сенарияи миёна
сенарияи беҳтарин
ва сенарияи бадтарин

Мушкилии вақт аксар вақт сенарияи бадтарин аст.

Ман танҳо дар бораи мураккабии вақти алгоритм сухан ронда будам, аммо мураккабӣ инчунин ба:

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

Албатта, мушкилиҳои бадтар аз n2 вуҷуд доранд, масалан:

n4: ин даҳшатнок аст! Баъзе аз алгоритмҳои зикршуда ин мураккабиро доранд.
3n: ин боз ҳам бадтар аст! Яке аз алгоритмҳое, ки мо дар мобайни ин мақола хоҳем дид, ин мураккабиро дорад (ва он воқеан дар бисёр пойгоҳи додаҳо истифода мешавад).
факториалӣ: шумо ҳеҷ гоҳ натиҷаҳои худро ҳатто бо миқдори ками маълумот ба даст намеоред.
nn: Агар шумо ба ин мураккабӣ дучор шавед, шумо бояд аз худ бипурсед, ки оё ин воқеан соҳаи фаъолияти шумост...

Эзоҳ: Ман ба шумо таърифи воқеии аломати бузурги O-ро надодаам, танҳо як идея. Шумо метавонед ин мақоларо дар зер хонед Википедия барои таърифи воқеӣ (ассимптотикӣ).

MergeSort

Вақте ки шумо бояд коллексияро ҷудо кунед, шумо чӣ кор мекунед? Чӣ? Шумо ба функсияи 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) мавҷуданд, арзиши умумии Н * log(N) амалиёти.

Афзалиятҳои навъҳои якҷоякунӣ

Чаро ин алгоритм ин қадар пурқувват аст?

Азбаски:

Шумо метавонед онро барои кам кардани изофаи хотира тағир диҳед, то шумо массивҳои нав эҷод накунед, балки массиви вурудро мустақиман тағир диҳед.

Эзоҳ: ин навъи алгоритм номида мешавад in-ҷои (бе хотираи иловагӣ ҷудокунӣ).

Шумо метавонед онро барои истифодаи фазои диск ва миқдори ками хотира ҳамзамон бидуни сарбории назарраси диски воридотӣ / баромад иваз кунед. Идеяи он аст, ки ба хотира танҳо он қисмҳое, ки ҳоло коркард мешаванд, бор карда шаванд. Ин муҳим аст, вақте ки шумо бояд ҷадвали бисёр гигабайтиро бо буфери хотираи 100-мегабайт ҷудо кунед.

Эзоҳ: ин навъи алгоритм номида мешавад навъи беруна.

Шумо метавонед онро тағир диҳед, то дар якчанд раванд/ришта/сервер кор кунад.

Масалан, навъи якҷоякунии тақсимшуда яке аз ҷузъҳои калидӣ мебошад Hadoop (ки сохтор дар маълумоти калон аст).

Ин алгоритм метавонад сурбро ба тилло табдил диҳад (воқеан!).

Ин алгоритми ҷудокунӣ дар аксари (агар на ҳама) пойгоҳи додаҳо истифода мешавад, аммо он ягона нест. Агар шумо хоҳед, ки маълумоти бештар гиред, шумо метавонед инро хонед кори тадкикотй, ки ҷиҳатҳои мусбат ва манфии алгоритмҳои ҷудокунии пойгоҳи додаҳоро баррасӣ мекунад.

Ҷадвали массив, дарахт ва хэш

Акнун, ки мо идеяи мураккабӣ ва ҷудокунии вақтро дарк мекунем, ман бояд ба шумо дар бораи 3 сохтори маълумот нақл кунам. Ин муҳим аст, зеро онҳо асоси базахои хозиразамон мебошанд. Ман инчунин консепсияро муаррифӣ мекунам индекси пойгоҳи додаҳо.

массив

Массиви дученака соддатарин сохтори додаҳост. Ҷадвалро ҳамчун массив тасаввур кардан мумкин аст. Барои намуна:

Ин массиви 2-ченака ҷадвали дорои сатрҳо ва сутунҳо мебошад:

Ҳар як сатр як объектро ифода мекунад
Сутунҳо хосиятҳоеро нигоҳ медоранд, ки объектро тавсиф мекунанд.
Ҳар як сутун маълумоти навъи мушаххасро нигоҳ медорад (тамоми, сатр, сана...).

Ин барои нигоҳдорӣ ва визуализатсияи додаҳо қулай аст, аммо вақте ки шумо бояд арзиши мушаххасро пайдо кунед, ин мувофиқ нест.

Масалан, агар шумо хоҳед, ки ҳамаи бачаҳоеро, ки дар Британияи Кабир кор мекунанд, пайдо кунед, ба шумо лозим меояд, ки ба ҳар як сатр назар андозед, то муайян кунед, ки оё он сатр ба Британияи Кабир тааллуқ дорад. Он ба шумо N транзаксияро талаб мекунадки дар N - шумораи сатрҳо, ки бад нест, аммо метавонист роҳи тезтар бошад? Акнун вақти шиносоӣ бо дарахтон расидааст.

Эзоҳ: Аксари пойгоҳи додаҳои замонавӣ массивҳои васеъро барои нигоҳдории самараноки ҷадвалҳо таъмин мекунанд: ҷадвалҳои heap-organized and index-organized tables. Аммо ин масъалаи дар як гурух сутунхо зуд пайдо кардани шарти мушаххасро тагьир намедихад.

Дарахти базаи маълумот ва индекс

Дарахти ҷустуҷӯии бинарӣ дарахти бинарӣ бо моликияти махсус мебошад, калид дар ҳар як гиреҳ бояд чунин бошад:

бузургтар аз ҳамаи калидҳои дар зердарахти чап захирашуда
камтар аз ҳамаи калидҳои дар зер дарахти рост захирашуда

Биёед бубинем, ки ин ба таври визуалӣ чӣ маъно дорад

Idea

Ин дарахт дорои 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 сатри дохили гиреҳро мегирам (дар расм нишон дода нашудааст) ва дар ҷадвал барои ID сатри додашуда назар мекунам.
Донистани ID-и сатр ба ман имкон медиҳад, ки дақиқ дар куҷо будани маълумот дар ҷадвалро бидонам, то ман онро фавран дарёфт кунам.

Дар ниҳоят, ҳарду ҷустуҷӯҳо ба ман миқдори сатҳҳои дохили дарахт арзиш доранд. Агар шумо қисматро дар бораи навъбандии якҷоя бодиққат хонед, шумо бояд бубинед, ки сатҳи 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 гиреҳ дорад. Ҷустуҷӯи гиреҳи мушаххас ба монанди дарахти қаблӣ log(N) арзиш дорад. Аммо вақте ки шумо ин гиреҳро ба даст меоред, шумо ворисони Mро дар амалиёти M бо истинод ба ворисони онҳо хоҳед гирифт. Ин ҷустуҷӯ танҳо арзиши M+log(N) амалиёт нисбат ба N амалиёт дар дарахти қаблӣ. Гузашта аз ин, ба шумо лозим нест, ки дарахти пурраро хонед (танҳо гиреҳҳои M+log(N)), ки маънои истифодаи камтари дискро дорад. Агар M хурд (масалан, 200 сатр) ва N калон (1 сатр) бошад, фарқияти КАЛОН хоҳад буд.

Аммо дар ин ҷо мушкилоти нав вуҷуд доранд (боз!). Агар шумо сатрро дар пойгоҳи додаҳо илова кунед ё нест кунед (ва аз ин рӯ дар индекси алоқаманди 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 + бояд комилан мутавозин бошад.

Ҷадвали ҳашт

Сохтори охирини муҳими маълумоти мо ҷадвали hash аст. Ин хеле муфид аст, вақте ки шумо мехоҳед арзишҳоро зуд ҷустуҷӯ кунед. Ғайр аз он, фаҳмидани ҷадвали hash ба мо кӯмак мекунад, ки баъдтар дарк кардани амалиёти умумии пайвастшавии пойгоҳи додаҳо бо номи hash join ( ҳаш ҳамроҳ). Ин сохтори додаҳо инчунин аз ҷониби пойгоҳи додаҳо барои нигоҳ доштани баъзе чизҳои дохилӣ истифода мешавад (масалан. мизи қулф ё ҳавзи буферӣ, мо ҳардуи ин мафҳумҳоро баъдтар мебинем).

Ҷадвали ҳаш сохтори додаҳост, ки элементро бо калиди худ зуд пайдо мекунад. Барои сохтани ҷадвали hash шумо бояд муайян кунед:

калл барои унсурҳои шумо
функсияи hash барои калидҳо. Хешҳои калидии ҳисобшуда ҷойгиршавии элементҳоро медиҳанд (ном сегментҳо ).
функсия барои муқоисаи калидҳо. Пас аз он ки шумо сегменти дурустро ёфтед, шумо бояд бо истифода аз ин муқоиса унсуреро, ки дар дохили сегмент ҷустуҷӯ мекунед, пайдо кунед.

Намунаи оддӣ

Биёед як мисоли равшанро гирем:

Ин ҷадвали ҳаш аз 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 сатр ва сана (масалан - насаб, ном ва санаи таваллуд)
...

Бо функсияи хуби хэш, ҷустуҷӯи ҷадвали hash арзиши O(1).

Массив ва ҷадвали хэш

Чаро массивро истифода набаред?

Ҳмм, саволи хуб.

Ҷадвали ҳаш метавонад бошад кисман ба хотира бор карда шудааст, ва сегментҳои боқимонда метавонанд дар диск бимонанд.
Бо массив шумо бояд фосилаи ҳамҷояро дар хотира истифода баред. Агар шумо ҷадвали калонро бор кунед ба кадри кофй фазой доимй ёфтан хеле душвор аст.
Барои ҷадвали ҳаш шумо метавонед калиди дилхоҳатонро интихоб кунед (масалан, кишвар ва насаб шахс).

Барои маълумоти иловагӣ, шумо метавонед мақоларо дар бораи он хонед JavaHashMap, ки татбиқи самараноки ҷадвали ҳаш аст; Барои фаҳмидани мафҳумҳои дар ин мақола овардашуда ба шумо Java лозим нест.

Манбаъ: will.com

Чӣ тавр пойгоҳи додаҳои релятсионӣ кор мекунанд (Қисми 1)