22. Qidiruv algoritmlarida indekslash nima?

41. Ma’lumotlarni saralash diskda qo’llaydigan algoritm nima deyiladi?

Agar fayllarning oraliq indekslash hajmi mavjud tezkor xotira hajmiga teng bo'lsa, muammoni siqish texnikasi yordamida hal qilish mumkin. Ammo ko'plab yirik to'plamli fayllar siqilgandan keyin ham xotiraga sig'maydi.

Agar tezkor xotira hajmi etarli bo'lmasa, tashqi tartiblash algoritmi (external sorting algorithm) kerak, ya'ni diskda qo’llaydigan algoritm. Kutilgan tezlikka erishish uchun saralash vaqtida bunday algoritm disk bo'ylab disk kallakchasining tasodifiy harakatlanish sonini minimallashtirishi kerak - natijada ma'lumotlarni o'qish tezlashadi (4.1-bo'limga qarang). Ushbu muammoning echimlaridan biri bu saralashga asoslangan blok indekslash algoritmi (blocked sort-based indexing), yoki BSBI, 4.2-rasmda ko’rsatilganidek. BSBI algoritmi 1) to'plamni teng qismlarga ajratadi; 2) har bir qismning "termID-docID" juftlarini xotirada saralaydi, 3) oraliq tartiblangan natijalarni diskka saqlaydi va 4) barcha oraliq natijalarni yakuniy indeksga birlashtiradi.