Хөөе Хабр! Би нийтлэлийн орчуулгыг та бүхэнд толилуулж байна
"Харилцааны мэдээллийн сан хэрхэн ажилладаг вэ".

Харилцааны мэдээллийн сангийн тухайд би ямар нэг зүйл дутуу байна гэж бодохоос өөр аргагүй. Тэдгээрийг хаа сайгүй ашигладаг. Жижиг, хэрэгцээтэй 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)) тэрбум өгөгдөлтэй байсан ч бага хэвээр байна.
Хамгийн хэцүү бэрхшээл - 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 мс алдах болно, зүгээр л нүдээ анив. Үнэхээр орчин үеийн процессорууд боловсруулах боломжтой секундэд хэдэн зуун сая үйлдэл хийдэг. Тийм ч учраас гүйцэтгэл, оновчлол нь мэдээллийн технологийн олон төслүүдэд асуудал биш юм.

Миний хэлсэнчлэн асар их хэмжээний өгөгдөлтэй ажиллахдаа энэ ойлголтыг мэдэх нь чухал хэвээр байна. Хэрэв энэ удаад алгоритм 1 элементийг боловсруулах шаардлагатай бол (энэ нь мэдээллийн сангийн хувьд тийм ч их биш):

O(1) алгоритм нь танд 1 үйлдэл хийхэд зарцуулагдана
O(log(n)) алгоритм нь танд 14 үйлдэл хийхэд зарцуулагдана
O(n) алгоритм нь танд 1 үйлдлийн зардал гарна
O(n*log(n)) алгоритм нь танд 14 үйлдэл хийх болно.
O(n2) алгоритм нь танд 1 үйлдэл хийх болно.

Би тооцоо хийгээгүй ч 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 нэгтгэх хэрэгтэй

Лог(N) алхамууд байгаа тул, нийт зардал Н * log(N) үйлдлүүд.

Нэгтгэх төрлийн давуу тал

Энэ алгоритм яагаад ийм хүчирхэг вэ?

Учир нь:

Та шинэ массив үүсгэхгүй, харин оролтын массивыг шууд өөрчлөхийн тулд санах ойн хэмжээг багасгахын тулд үүнийг өөрчилж болно.

Анхаар: энэ төрлийн алгоритмыг нэрлэдэг in-газар (нэмэлт санах ойгүйгээр эрэмбэлэх).

Та дискний зай болон бага хэмжээний санах ойг нэгэн зэрэг ашиглахын тулд дискний оролт гаралтын нэмэлт зардал гаргахгүйгээр үүнийг өөрчлөх боломжтой. Санах ойд зөвхөн одоо боловсруулж байгаа хэсгүүдийг ачаалах санаа юм. Зөвхөн 100 мегабайт санах ойн буфер бүхий олон гигабайт хүснэгтийг эрэмбэлэх шаардлагатай үед энэ нь чухал юм.

Анхаар: энэ төрлийн алгоритмыг нэрлэдэг гадаад төрөл.

Та үүнийг олон процесс/thread/server дээр ажиллуулахаар өөрчилж болно.

Жишээлбэл, тархсан нэгтгэх төрөл нь гол бүрэлдэхүүн хэсгүүдийн нэг юм Hadoop (энэ нь том өгөгдлийн бүтэц юм).

Энэ алгоритм нь хар тугалгыг алт болгон хувиргаж чадна (үнэхээр!).

Энэхүү эрэмбэлэх алгоритмыг ихэнх (бүгд биш бол) мэдээллийн санд ашигладаг боловч энэ нь цорын ганц биш юм. Хэрэв та илүү ихийг мэдэхийг хүсвэл үүнийг уншиж болно судалгааны ажил, нийтлэг мэдээллийн санг эрэмбэлэх алгоритмуудын давуу болон сул талуудыг авч үздэг.

Массив, мод, хэш хүснэгт

Одоо бид цаг хугацааны нарийн төвөгтэй байдал, эрэмбэлэх санааг ойлгож байгаа тул би 3 өгөгдлийн бүтцийн талаар танд хэлэх ёстой. Энэ нь чухал учир нь тэд орчин үеийн мэдээллийн сангийн үндэс суурь болдог. Би мөн үзэл баримтлалыг танилцуулах болно мэдээллийн сангийн индекс.

массив

Хоёр хэмжээст массив нь хамгийн энгийн өгөгдлийн бүтэц юм. Хүснэгтийг массив гэж ойлгож болно. Жишээлбэл:

Энэхүү 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, зангилаа байдаг. Би зангилаа доторх мөрийн ID-г (зураг дээр биш) авч, өгөгдсөн мөрийн ID-г хүснэгтээс харна уу.
Мөрийн ID-г мэдэх нь хүснэгтэд байгаа өгөгдөл яг хаана байгааг мэдэх боломжийг олгодог тул би үүнийг шууд татаж авах боломжтой.

Эцсийн эцэст, хайлт хоёулаа модны доторх түвшний тоогоор надад үнэтэй байх болно. Хэрэв та нэгтгэх ангилах хэсгийг анхааралтай уншвал log(N) түвшин байгааг харах хэрэгтэй. Энэ нь болж байна, хайлтын зардлын бүртгэл(N), муугүй шүү!

Асуудал руугаа буцъя

Гэхдээ энэ бол маш хийсвэр зүйл тул асуудалдаа эргэн оръё. Энгийн бүхэл тооны оронд өмнөх хүснэгтэд байгаа хэн нэгний улсыг төлөөлөх тэмдэгт мөрийг төсөөлөөд үз дээ. Хүснэгтийн "улс" талбарыг (3-р багана) агуулсан мод байна гэж бодъё:

Их Британид хэн ажилладагийг мэдэхийг хүсвэл
Их Британийг төлөөлж буй зангилааг авахын тулд та модыг хар
"UKnode" дотроос та Их Британийн ажилчдын бүртгэлийн байршлыг олох болно.

Хэрэв та массивыг шууд ашиглавал энэ хайлт нь N үйлдлийн оронд log(N) үйлдлүүдийн өртөгтэй болно. Таны сая танилцуулсан зүйл мэдээллийн сангийн индекс.

Түлхүүрүүдийг (өөрөөр хэлбэл талбарын бүлгүүдийг) харьцуулах функцтэй л бол та аль ч бүлэг талбарт (мөр, тоо, 2 мөр, тоо ба мөр, огноо...) индексийн мод үүсгэж болно. түлхүүрүүдийн дунд захиалга хийх (энэ нь мэдээллийн сангийн аливаа үндсэн төрлүүдэд тохиолддог).

B+TreeIndex

Энэ мод нь тодорхой үнэ цэнийг авахын тулд сайн ажилладаг боловч танд хэрэгтэй үед ТОМ асуудал гардаг хоёр утгын хооронд олон элемент авах. Энэ нь O(N) үнэтэй байх тул та модны зангилаа бүрийг харж, эдгээр хоёр утгын хооронд байгаа эсэхийг шалгах хэрэгтэй (жишээ нь, модыг эрэмбэлэн гүйлгэх). Үүнээс гадна, та модыг бүхэлд нь унших хэрэгтэй тул энэ үйлдэл нь дискний оролт гаралтын горимд тохирохгүй. Бид үр дүнтэй хэрэгжүүлэх арга замыг олох хэрэгтэй хүрээний хүсэлт. Энэ асуудлыг шийдэхийн тулд орчин үеийн мэдээллийн сангууд өмнөх модны B+Tree нэртэй өөрчлөгдсөн хувилбарыг ашигладаг. B + модны модонд:

зөвхөн хамгийн доод зангилаанууд (навчнууд) мэдээллийг хадгалах (холбогдох хүснэгт дэх мөрүүдийн байршил)
үлдсэн зангилаанууд энд байна чиглүүлэлтийн хувьд зөв зангилаа руу хайлтын үеэр.

Таны харж байгаагаар энд илүү олон зангилаа байдаг (хоёр удаа). Үнэн хэрэгтээ танд зөв зангилаа олоход туслах нэмэлт зангилаа, "шийдвэрийн зангилаанууд" байдаг (энэ нь холбогдох хүснэгтэд мөрийн байршлыг хадгалдаг). Гэхдээ хайлтын нарийн төвөгтэй байдал нь O(log(N)) хэвээр байна (зөвхөн нэг түвшин байна). Том ялгаа нь үүнд л байгаа юм доод түвшний зангилаанууд нь залгамжлагчтайгаа холбогддог.

Хэрэв та 40-100 хүртэлх утгыг хайж байгаа бол энэ B + Tree-ийн тусламжтайгаар:

Та өмнөх модтой адил 40 (эсвэл 40 байхгүй бол 40-өөс хойшхи хамгийн ойрын утгыг) хайх хэрэгтэй.
Дараа нь 40 хүрэх хүртлээ шууд өв залгамжлагчийн холбоосыг ашиглан 100 өв залгамжлагчийг цуглуул.

Та M залгамжлагчийг олсон ба мод нь N зангилаатай гэж үзье. Тодорхой зангилаа олоход өмнөх мод шиг лог(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

Бидний хамгийн сүүлийн чухал өгөгдлийн бүтэц бол хэш хүснэгт юм. Хэрэв та утгыг хурдан хайхыг хүсвэл энэ нь маш хэрэгтэй. Нэмж дурдахад, хэш хүснэгтийг ойлгох нь бидэнд хэш нэгтгэх (хэш нэгтгэх) гэж нэрлэгддэг өгөгдлийн сангийн нэгдсэн үйлдлийг хожим ойлгоход тусална. хэш нэгдэх). Энэхүү өгөгдлийн бүтцийг мэдээллийн сан зарим дотоод зүйлсийг хадгалахад ашигладаг (жишээ нь: цоож ширээ буюу буфер сан, бид эдгээр хоёр ойлголтыг дараа нь харах болно).

Хэш хүснэгт нь элементийг түлхүүрээр нь хурдан олдог өгөгдлийн бүтэц юм. Хэш хүснэгт үүсгэхийн тулд та дараахь зүйлийг тодорхойлох хэрэгтэй.

гарын авлага таны элементүүдийн хувьд
хэш функц түлхүүрүүдийн хувьд. Тооцоолсон түлхүүр хэшүүд нь элементүүдийн байршлыг өгдөг (гэж нэрлэдэг сегментүүд ).
товчлууруудыг харьцуулах функц. Та зөв сегментийг олсны дараа энэ харьцуулалтыг ашиглан сегмент дотроос хайж буй элементээ олох ёстой.

Энгийн жишээ

Тодорхой жишээ авъя:

Энэ хэш хүснэгт нь 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 хэлийг ойлгох шаардлагагүй.

Эх сурвалж: www.habr.com

Харилцааны мэдээллийн сан хэрхэн ажилладаг вэ (1-р хэсэг)