Xeshing-ma'lum bir xususiyatga EGA bo'lmagan pastki to'plamlarda (elementlarning to'plamlari) bir nechta kalitlarni (odatda saqlash elementlarini va odatda matn satrlari yoki raqamlar shaklida taqdim etilgan) ajratish


Kengaytirilgan xeshing (kengaytirilgan xeshing)



Download 62,22 Kb.
bet4/9
Sana15.11.2022
Hajmi62,22 Kb.
#866865
1   2   3   4   5   6   7   8   9
Bog'liq
Mavzu Xesh jadvallari va funktsiyalari

Kengaytirilgan xeshing (kengaytirilgan xeshing)
Kengaytirilgan xeshing dinamikaga yaqin. Ushbu usul, shuningdek, ma'lumotlar bazasi o'sib borayotganligi sababli bloklarning o'lchamlarini o'zgartirishni ham o'z ichiga oladi, ammo bu joydan optimal foydalanish bilan qoplanadi. Chunki bir vaqtning o'zida bir blokdan ortiq emas, yuqoridagi xarajatlar juda kichik [9].
Ikkilik daraxtning o'rniga kengayadigan xeshing elementlari bloklarga bog'langan ro'yxatni taqdim etadi. Elementlarning o'zi bir nechta i bitli psevdo-kalitga qaratilgan (rasmga qarang). Qidiruvda men psevdo-kalitning bitlarini qabul qilaman va ro'yxat (directory)orqali kerakli blokning manzili. Elementlarni qo'shish yanada qiyinlashadi. Birinchidan, qidiruvga o'xsxesh protsedura amalga oshiriladi. Agar blok to'liq bo'lmasa, unga va ma'lumotlar bazasiga kirish qo'shiladi. Agar blok to'ldirilgan bo'lsa, u ikkiga bo'linadi, yozuvlar yuqorida tavsiflangan algoritmga muvofiq qayta taqsimlanadi. Bunday holda, murojaat qilish uchun zarur bo'lgan bit sonini ko'paytirish mumkin. Bunday holda, ro'yxatning hajmi ikki barobar ko'payadi va yangi yaratilgan har bir elementga uning ota-onasini o'z ichiga olgan ko'rsatgich beriladi. Shunday qilib, bir nechta elementlar bir xil blokda ko'rsatilganda vaziyat bo'lishi mumkin. Shuni ta'kidlash kerakki, bir operatsiyani bajarish uchun qo'shimchalar bir blokdan ortiq bo'lmagan qiymatlarni qayta hisoblab chiqadi. Olib tashlash bir xil algoritm bilan amalga oshiriladi, aksincha. Bloklar, o'z navbatida, yopishtirilishi mumkin va ro'yxat ikki barobar kamayadi.


Shunday qilib, kengayadigan xeshingning asosiy afzalligi yuqori samaradorlik bo'lib, u ma'lumotlar bazasi hajmini oshirishda tushmaydi. Bundan tashqari, saqlash qurilmasidagi joy oqilona sarflanadi, chunki bloklar faqat mavjud bo'lgan ma'lumotlar uchun ajratiladi va bloklar uchun ko'rsatgichlar ro'yxati ushbu bloklar sonini aniqlash uchun minimal darajada talab qilinadi. Ushbu imtiyozlar uchun ishlab chiquvchi dastur kodining qo'shimcha murakkabligi bilan to'lanadi.
Kalitlarning tartibini saqlaydigan vazifalar (Xesh funktsiyalarini saqlash tartibi)
Kalitlarning tartibini saqlaydigan Xesh funktsiyalari klassi mavjud [11]. Boshqacha aytganda, u amalga oshiriladi
K1 < K2  h(K1) < h(K2)
Ushbu xususiyatlar har qanday qo'shimcha ishni talab qilmaydigan tartiblash uchun foydalidir. Boshqacha qilib aytganda, biz ko'plab taqqoslashlardan qochamiz, chunki ob'ektlarni oshirish uchun tartiblashtirish uchun Xesh stolini chiziqli ravishda skanerlash kifoya.

Asosan, siz har doim bunday funktsiyani yaratishingiz mumkin, agar xesh jadvali kalit maydonidan kattaroq bo'lsa. Biroq, to'g'ri Xesh funktsiyasini topish vazifasi ahamiyatsiz. Albatta, bu muayyan vazifaga juda bog'liq. Bundan tashqari, Xesh funktsiyasiga o'xsxesh cheklov uning ishlashiga salbiy ta'sir ko'rsatishi mumkin. Shuning uchun, tez-tez ketma-ket namuna olish jarayoni tez-tez sodir bo'lishini oldindan bilmasa, bunday Xesh funktsiyasini izlash o'rniga indekslashga murojaat qiling.





Download 62,22 Kb.

Do'stlaringiz bilan baham:
1   2   3   4   5   6   7   8   9




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish