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.