Հե՜յ Հաբր։ Ձեր ուշադրությանն եմ ներկայացնում հոդվածի թարգմանությունը
«Ինչպես է աշխատում հարաբերական տվյալների բազան».

Երբ խոսքը վերաբերում է հարաբերական տվյալների բազաներին, ես չեմ կարող չմտածել, որ ինչ-որ բան պակասում է: Դրանք օգտագործվում են ամենուր: Կան բազմաթիվ տարբեր տվյալների բազաներ՝ փոքր և օգտակար SQLite-ից մինչև հզոր Teradata: Բայց կան միայն մի քանի հոդվածներ, որոնք բացատրում են, թե ինչպես է աշխատում տվյալների բազան: Դուք կարող եք ինքներդ որոնել՝ օգտագործելով «howdoesarelationaldatabasework»-ը՝ տեսնելու, թե որքան քիչ արդյունքներ կան: Ավելին, այս հոդվածները կարճ են։ Եթե ​​դուք փնտրում եք ամենավերջին աշխույժ տեխնոլոգիաները (BigData, NoSQL կամ JavaScript), դուք կգտնեք ավելի խորը հոդվածներ, որոնք կբացատրեն, թե ինչպես են դրանք աշխատում:

Արդյո՞ք հարաբերական տվյալների բազաները չափազանց հին և ձանձրալի են՝ բացատրելու համար համալսարանական դասընթացներից, հետազոտական ​​աշխատանքներից և գրքերից դուրս:

Որպես ծրագրավորող, ես ատում եմ օգտագործել այն, ինչ ես չեմ հասկանում: Իսկ եթե տվյալների շտեմարաններն օգտագործվել են ավելի քան 40 տարի, ապա պետք է պատճառ լինի։ Տարիների ընթացքում ես հարյուրավոր ժամեր եմ ծախսել՝ իսկապես հասկանալու այս տարօրինակ սև արկղերը, որոնք ես օգտագործում եմ ամեն օր: Հարաբերական տվյալների բազաներ շատ հետաքրքիր է, քանի որ նրանք հիմնված օգտակար և բազմակի օգտագործման գաղափարների վրա. Եթե ​​դուք շահագրգռված եք հասկանալ տվյալների բազան, բայց երբեք ժամանակ կամ հակվածություն չեք ունեցել խորանալու այս լայն թեմայի մեջ, դուք պետք է վայելեք այս հոդվածը:

Չնայած այս հոդվածի վերնագիրը հստակ է. Այս հոդվածի նպատակը չէ հասկանալ, թե ինչպես օգտագործել տվյալների բազան. Հետևաբար դուք արդեն պետք է իմանաք, թե ինչպես գրել միացման պարզ հարցում և հիմնական հարցումներ ՔԱԱՔ; հակառակ դեպքում դուք կարող եք չհասկանալ այս հոդվածը: Միայն դա է պետք իմանալ, մնացածը կբացատրեմ:

Ես կսկսեմ համակարգչային գիտության որոշ հիմունքներից, ինչպիսիք են ալգորիթմների ժամանակային բարդությունը (BigO): Ես գիտեմ, որ ձեզնից ոմանք ատում են այս հասկացությունը, բայց առանց դրա դուք չեք կարողանա հասկանալ տվյալների բազայի ներսում առկա բարդությունները: Քանի որ սա հսկայական թեմա է, Ես կկենտրոնանամ այն, ինչ իմ կարծիքով կարևոր է: ինչպես է գործում տվյալների բազան SQL հարցումը. Պարզապես կներկայացնեմ տվյալների բազայի հիմնական հասկացություններըորպեսզի հոդվածի վերջում պատկերացում ունենաք, թե ինչ է կատարվում գլխարկի տակ:

Քանի որ սա երկար և տեխնիկական հոդված է, որը ներառում է բազմաթիվ ալգորիթմներ և տվյալների կառուցվածքներ, ժամանակ տրամադրեք այն կարդալու համար: Որոշ հասկացություններ կարող են դժվար հասկանալ. դուք կարող եք բաց թողնել դրանք և դեռ ստանալ ընդհանուր գաղափարը:

Ձեզանից ավելի բանիմացների համար այս հոդվածը բաժանված է 3 մասի.

• Ցածր և բարձր մակարդակի տվյալների բազայի բաղադրիչների ակնարկ
• Հարցման օպտիմիզացման գործընթացի ակնարկ
• Գործարքների և բուֆերային լողավազանի կառավարման ակնարկ

Վերադարձ դեպի հիմունքներ

Տարիներ առաջ (հեռու, հեռու գալակտիկայում...), մշակողները պետք է հստակ իմանային իրենց կողմից կոդավորվող գործողությունների քանակը: Նրանք անգիր գիտեին իրենց ալգորիթմներն ու տվյալների կառուցվածքը, քանի որ չէին կարող իրենց թույլ տալ վատնել իրենց դանդաղ համակարգիչների պրոցեսորն ու հիշողությունը:

Այս մասում ես ձեզ կհիշեցնեմ այս հասկացություններից մի քանիսը, քանի որ դրանք էական են տվյալների բազան հասկանալու համար: Ներկայացնեմ նաև հայեցակարգը տվյալների բազայի ինդեքս.

O(1) vs O(n2)

Մեր օրերում ծրագրավորողներից շատերին չի հետաքրքրում ալգորիթմների ժամանակային բարդությունը... և նրանք ճիշտ են:

Բայց երբ գործ ունես շատ տվյալների հետ (ես չեմ խոսում հազարների մասին) կամ եթե դու պայքարում ես միլիվայրկյանների ընթացքում, կարևոր է դառնում հասկանալ այս հայեցակարգը: Եվ ինչպես կարող եք պատկերացնել, տվյալների բազաները պետք է զբաղվեն երկու իրավիճակներով: Ես ձեզ չեմ ստիպի ավելի շատ ժամանակ ծախսել, քան անհրաժեշտ է` նպատակը հասկանալու համար: Սա կօգնի մեզ ավելի ուշ հասկանալ ծախսերի վրա հիմնված օպտիմալացման հայեցակարգը (արժենալ հիմնված Օպտիմալացում).

Հայեցակարգ

Ալգորիթմի ժամանակային բարդությունը օգտագործվում է տեսնելու համար, թե որքան ժամանակ կպահանջվի ալգորիթմի ավարտին տվյալ քանակի տվյալների համար. Այս բարդությունը նկարագրելու համար մենք օգտագործում ենք մեծ O մաթեմատիկական նշում: Այս նշումն օգտագործվում է ֆունկցիայի հետ, որը նկարագրում է, թե քանի գործողություն է անհրաժեշտ ալգորիթմին տվյալ թվի մուտքերի համար:

Օրինակ, երբ ես ասում եմ «այս ալգորիթմն ունի բարդություն O(some_function())», դա նշանակում է, որ ալգորիթմը պահանջում է some_function(a_certain_amount_of_ta) գործողություններ՝ որոշակի քանակությամբ տվյալներ մշակելու համար։

Այս դեպքում, Կարևորը տվյալների քանակությունը չէ**, հակառակ դեպքում ** ինչպես է ավելանում գործողությունների քանակը տվյալների ծավալի ավելացման հետ. Ժամանակի բարդությունը չի ապահովում գործողությունների ճշգրիտ թիվը, բայց կատարման ժամանակը գնահատելու լավ միջոց է:

Այս գծապատկերում դուք կարող եք տեսնել ալգորիթմի ժամանակային բարդությունների տարբեր տեսակների համար գործողությունների քանակը՝ համեմատած մուտքային տվյալների քանակի հետ: Ես դրանք ցուցադրելու համար օգտագործեցի լոգարիթմական սանդղակ: Այլ կերպ ասած, տվյալների քանակը արագորեն աճում է 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 գործողություն

O(1)-ի և O(n2-ի) միջև տարբերությունը մեծ է թվում (4 միլիոն վիրահատություն), բայց դուք կկորցնեք առավելագույնը 2 ms, պարզապես ձեր աչքերը թարթելու ժամանակն է: Իրոք, ժամանակակից պրոցեսորները կարող են մշակել հարյուր միլիոնավոր գործողություններ վայրկյանում. Սա է պատճառը, որ արդյունավետությունն ու օպտիմալացումը շատ ՏՏ նախագծերում խնդիր չեն:

Ինչպես ասացի, դեռևս կարևոր է իմանալ այս հայեցակարգը հսկայական քանակությամբ տվյալների հետ աշխատելիս: Եթե ​​այս անգամ ալգորիթմը պետք է մշակի 1 տարր (ինչը այնքան էլ շատ չէ տվյալների բազայի համար).

• O(1) ալգորիթմը ձեզ կարժենա 1 գործողություն
• O(log(n)) ալգորիթմը ձեզ կարժենա 14 գործողություն
• O(n) ալգորիթմը ձեզ կարժենա 1 գործողություն
• O(n*log(n)) ալգորիթմը ձեզ կարժենա 14 գործողություն
• O(n2) ալգորիթմը ձեզ կարժենա 1 գործողություն

Ես մաթեմատիկա չեմ արել, բայց կասեմ, որ O(n2) ալգորիթմով ժամանակ ունես սուրճ խմելու (նույնիսկ երկուսը): Եթե ​​տվյալների ծավալին ավելացնեք ևս 0, ապա ժամանակ կունենաք քնելու:

Եկեք ավելի խորանանք

Ձեր information:

• Հեշ աղյուսակի լավ որոնումը գտնում է տարր O(1-ում):
• Լավ հավասարակշռված ծառի որոնումը տալիս է O(log(n)) արդյունք:
• Զանգվածի որոնումը տալիս է O(n) արդյունք:
• Լավագույն տեսակավորման ալգորիթմներն ունեն բարդություն O(n*log(n)):
• Վատ տեսակավորման ալգորիթմը բարդություն ունի O(n2):

Նշում. Հետևյալ մասերում մենք կտեսնենք այս ալգորիթմները և տվյալների կառուցվածքները:

Ալգորիթմի ժամանակի բարդության մի քանի տեսակներ կան.

• միջին դեպքի սցենար
• լավագույն դեպքի սցենարը
• և ամենավատ սցենարը

Ժամանակի բարդությունը հաճախ ամենավատ սցենարն է:

Ես միայն խոսում էի ալգորիթմի ժամանակային բարդության մասին, բայց բարդությունը վերաբերում է նաև.

• ալգորիթմի հիշողության սպառումը
• սկավառակի I/O սպառման ալգորիթմ

Իհարկե, կան n2-ից ավելի վատ բարդություններ, օրինակ.

• N4: Սա սարսափելի է: Նշված ալգորիթմներից մի քանիսն ունեն այս բարդությունը։
• 3n. սա ավելի վատ է: Ալգորիթմներից մեկը, որը մենք կտեսնենք այս հոդվածի կեսին, ունի այս բարդությունը (և այն իրականում օգտագործվում է բազմաթիվ տվյալների բազաներում):
• factorial n. դուք երբեք չեք ստանա ձեր արդյունքները նույնիսկ փոքր քանակությամբ տվյալների դեպքում:
• nn. Եթե բախվում եք այս բարդության հետ, պետք է ինքներդ ձեզ հարցնեք՝ արդյոք սա իսկապես ձեր գործունեության ոլորտն է...

Նշում. Ես ձեզ չեմ տվել մեծ O նշանակման իրական սահմանումը, պարզապես գաղափար: Այս հոդվածը կարող եք կարդալ այստեղ Վիքիպեդիա իրական (ասիմպտոտիկ) սահմանման համար:

MergeSort

Ի՞նչ եք անում, երբ անհրաժեշտ է տեսակավորել հավաքածուն: Ինչ? Դուք կանչում եք sort() ֆունկցիան... Լավ, լավ պատասխան... Բայց տվյալների բազայի համար դուք պետք է հասկանաք, թե ինչպես է աշխատում այս տեսակավորման ֆունկցիան:

Կան մի քանի լավ տեսակավորման ալգորիթմներ, ուստի ես կկենտրոնանամ ամենակարևորների վրա. միաձուլման տեսակավորում. Դուք կարող եք չհասկանալ, թե ինչու է տվյալների տեսակավորումն օգտակար հենց հիմա, բայց պետք է հարցման օպտիմալացման մասից հետո: Ավելին, միաձուլման տեսակավորումը հասկանալը կօգնի մեզ հետագայում հասկանալ տվյալների բազայի միացման ընդհանուր գործողությունը, որը կոչվում է ընկղմել միանալ (միաձուլման ասոցիացիա).

Միաձուլել

Ինչպես շատ օգտակար ալգորիթմներ, միաձուլման տեսակավորումը հիմնված է հնարքի վրա. N/2 չափի 2 տեսակավորված զանգվածների միավորումը N-տարրով տեսակավորված զանգվածի մեջ արժե միայն N գործողություն: Այս գործողությունը կոչվում է միաձուլում:

Տեսնենք, թե դա ինչ է նշանակում պարզ օրինակով.

Այս նկարը ցույց է տալիս, որ վերջնական տեսակավորված 8-տարրանոց զանգվածը կառուցելու համար անհրաժեշտ է միայն մեկ անգամ կրկնել 2 4-տարրանոց զանգվածների վրա: Քանի որ երկու տարրից բաղկացած զանգվածներն էլ արդեն տեսակավորված են.

• 1) դուք համեմատում եք երկու ընթացիկ տարրերը երկու զանգվածներում (սկզբում ընթացիկ = առաջինը)
• 2) այնուհետև վերցրեք ամենափոքրը և տեղադրեք այն 8 տարրից բաղկացած զանգվածի մեջ
• 3) և անցեք զանգվածի հաջորդ տարրին, որտեղ վերցրել եք ամենափոքր տարրը
• և կրկնել 1,2,3, մինչև հասնես զանգվածներից մեկի վերջին տարրին։
• Այնուհետև վերցնում եք մյուս զանգվածի մնացած տարրերը, որպեսզի դրանք տեղադրեք 8 տարրանոց զանգվածի մեջ:

Սա աշխատում է, քանի որ երկու տարրից բաղկացած զանգվածներն էլ տեսակավորված են, և դուք պետք չէ «հետ գնալ» այդ զանգվածներում:

Այժմ, երբ մենք հասկանում ենք հնարքը, ահա իմ կեղծ կոդը միաձուլման համար.

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-տեղ (տեսակավորում առանց լրացուցիչ հիշողության):

• Դուք կարող եք փոխել այն՝ միաժամանակ օգտագործելու սկավառակի տարածություն և փոքր քանակությամբ հիշողություն՝ առանց սկավառակի I/O-ի զգալի ծախսերի: Գաղափարն այն է, որ հիշողության մեջ բեռնվեն միայն այն մասերը, որոնք ներկայումս մշակվում են: Սա կարևոր է, երբ դուք պետք է տեսակավորեք մի քանի գիգաբայթանոց աղյուսակը միայն 100 մեգաբայթանոց հիշողության բուֆերով:

Նշում. այս տեսակի ալգորիթմը կոչվում է արտաքին տեսակավորում.

• Դուք կարող եք փոխել այն, որպեսզի այն աշխատի մի քանի գործընթացների/թելերի/սերվերների վրա:

Օրինակ, բաշխված միաձուլման տեսակավորումը հիմնական բաղադրիչներից մեկն է Hadoop (որը կառույց է մեծ տվյալների մեջ):

• Այս ալգորիթմը կարող է կապարը վերածել ոսկու (իսկապես!):

Այս տեսակավորման ալգորիթմը օգտագործվում է տվյալների բազաների մեծ մասում (եթե ոչ բոլորում), բայց դա միակը չէ: Եթե ​​ցանկանում եք ավելին իմանալ, կարող եք կարդալ սա հետազոտական ​​աշխատանք, որը քննարկում է տվյալների բազայի տեսակավորման ընդհանուր ալգորիթմների դրական և բացասական կողմերը։

Զանգված, ծառ և հեշ աղյուսակ

Այժմ, երբ մենք հասկանում ենք ժամանակի բարդության և տեսակավորման գաղափարը, ես պետք է ձեզ պատմեմ 3 տվյալների կառուցվածքի մասին: Սա կարևոր է, քանի որ նրանք ժամանակակից շտեմարանների հիմքն են. Ներկայացնեմ նաև հայեցակարգը տվյալների բազայի ինդեքս.

Array

Երկչափ զանգվածը տվյալների ամենապարզ կառուցվածքն է: Աղյուսակը կարելի է պատկերացնել որպես զանգված: Օրինակ:

Այս երկչափ զանգվածը տողերով և սյունակներով աղյուսակ է.

• Յուրաքանչյուր տող ներկայացնում է մի էություն
• Սյունակները պահում են այն հատկությունները, որոնք նկարագրում են կազմակերպությունը:
• Յուրաքանչյուր սյունակ պահում է որոշակի տեսակի տվյալներ (ամբողջ թիվ, տող, ամսաթիվ...):

Սա հարմար է տվյալների պահպանման և վիզուալացման համար, սակայն, երբ անհրաժեշտ է գտնել որոշակի արժեք, դա հարմար չէ:

Օրինակ, եթե ցանկանում եք գտնել բոլոր տղաներին, ովքեր աշխատում են Միացյալ Թագավորությունում, դուք պետք է նայեք յուրաքանչյուր շարքը՝ որոշելու, թե արդյոք այդ շարքը պատկանում է Մեծ Բրիտանիային: Դա ձեզ կարժենա N գործարքՈրտեղ N - տողերի քանակը, ինչը վատ չէ, բայց կարո՞ղ է ավելի արագ ճանապարհ լինել: Հիմա ժամանակն է, որ մենք ծանոթանանք ծառերին։

Նշում. Ժամանակակից տվյալների բազաներից շատերն ապահովում են ընդլայնված զանգվածներ աղյուսակների արդյունավետ պահպանման համար՝ կույտով կազմակերպված աղյուսակներ և ինդեքսով կազմակերպված աղյուսակներ: Բայց սա չի փոխում սյունակների խմբում կոնկրետ պայման արագ գտնելու խնդիրը:

Տվյալների բազայի ծառ և ինդեքս

Երկուական որոնման ծառը երկուական ծառ է հատուկ հատկությամբ, յուրաքանչյուր հանգույցի բանալին պետք է լինի.

• ավելի մեծ, քան ձախ ենթածառում պահված բոլոր ստեղները
• պակաս, քան աջ ենթածառում պահված բոլոր ստեղները

Տեսնենք, թե ինչ է սա նշանակում տեսողականորեն

Գաղափար

Այս ծառն ունի N = 15 տարր: Ենթադրենք, ես փնտրում եմ 208:

• Ես սկսում եմ արմատից, որի բանալին 136 է։ Քանի որ 136<208, ես նայում եմ 136 հանգույցի աջ ենթածառին։
• 398>208 հետևաբար ես նայում եմ 398 հանգույցի ձախ ենթածառին
• 250>208 հետևաբար ես նայում եմ 250 հանգույցի ձախ ենթածառին
• 200<208, հետևաբար ես նայում եմ 200 հանգույցի աջ ենթածառին: Բայց 200-ը ճիշտ ենթածառ չունի, արժեքը գոյություն չունի (քանի որ եթե այն գոյություն ունի, այն կլինի աջ ենթածառի 200-ում):

Հիմա ասենք, որ ես փնտրում եմ 40

• Ես սկսում եմ արմատից, որի բանալին 136 է: Քանի որ 136 > 40, ես նայում եմ 136 հանգույցի ձախ ենթածառին:
• 80 > 40, հետևաբար ես նայում եմ 80 հանգույցի ձախ ենթածառին
• 40 = 40, հանգույց գոյություն ունի. Ես վերբերում եմ տողի ID-ն հանգույցի ներսում (նկարում պատկերված չէ) և աղյուսակում փնտրում եմ տվյալ տողի ID-ն:
• Տողի ID-ի իմացությունը թույլ է տալիս ինձ ճշգրիտ իմանալ, թե որտեղ են տվյալները աղյուսակում, այնպես որ ես կարող եմ անմիջապես առբերել դրանք:

Ի վերջո, երկու որոնումները ինձ կարժենան ծառի ներսում գտնվող մակարդակների քանակով: Եթե ​​ուշադիր կարդաք միաձուլման տեսակավորման մասին մասը, ապա պետք է տեսնեք, որ կան log(N) մակարդակներ: Պարզվում է, որոնման ծախսերի մատյան (N), վատ չէ!

Վերադառնանք մեր խնդրին

Բայց սա շատ վերացական է, ուստի վերադառնանք մեր խնդրին: Պարզ ամբողջ թվի փոխարեն պատկերացրեք մի տող, որը ներկայացնում է նախորդ աղյուսակում ինչ-որ մեկի երկիրը: Ենթադրենք, դուք ունեք ծառ, որը պարունակում է աղյուսակի «երկիր» դաշտը (սյունակ 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) հանգույցները), ինչը նշանակում է սկավառակի ավելի քիչ օգտագործում։ Եթե ​​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+ ծառը պետք է լիովին հավասարակշռված լինի:

Hashtable

Մեր վերջին կարևոր տվյալների կառուցվածքը հեշ աղյուսակն է: Սա շատ օգտակար է, երբ ցանկանում եք արագ որոնել արժեքները: Ավելին, հեշ աղյուսակը հասկանալը կօգնի մեզ հետագայում հասկանալ տվյալների բազայի միացման ընդհանուր գործողությունը, որը կոչվում է հեշ միացում ( 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 տող և ամսաթիվ (օրինակ՝ ազգանուն, անուն և ծննդյան ամսաթիվ)
• ...

Լավ հեշ ֆունկցիայի դեպքում հեշ աղյուսակի որոնումները արժե O(1).

Զանգված ընդդեմ հեշ աղյուսակի

Ինչու չօգտագործել զանգված:

Հմմ, լավ հարց է:

• Հեշ աղյուսակը կարող է լինել մասամբ բեռնված է հիշողության մեջ, իսկ մնացած հատվածները կարող են մնալ սկավառակի վրա։
• Զանգվածով դուք պետք է օգտագործեք հարակից տարածք հիշողության մեջ: Եթե ​​դուք բեռնում եք մեծ սեղան շատ դժվար է գտնել բավականաչափ շարունակական տարածք.
• Հեշ աղյուսակի համար կարող եք ընտրել ձեր ուզած բանալին (օրինակ՝ երկիրը և անձի ազգանունը):

Լրացուցիչ տեղեկությունների համար կարող եք կարդալ հոդվածը JavaHashMap, որը հեշ աղյուսակի արդյունավետ իրականացումն է; Ձեզ հարկավոր չէ Java-ն հասկանալ այս հոդվածում ընդգրկված հասկացությունները հասկանալու համար:

Source: www.habr.com