O‘ZBEKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI MUHAMMAD-AL XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI “Axborot texnologiyalari” kafedrasi
“ELEKTRON HUKUMAT” TIZIMINI BOSHQARISH YO’NALISHI 203-21 GURUH MAGISTRANTI
JUMANOV BAHROMJONNING ALGORITM LOYIHALASH VA TAHLIL QILISH FANIDAN
“B -DARAXTLAR” MAVZUSIDA TAYYORLAGAN
MUSTAQIL ISHI Reja:
B-daraxtlar haqida.
B-daraxtlar bilan ishlash algoritmi.
B-darxtlardan foydalanish muammolari.
B-tree (ing tilida B-tree deb talaffuz qilinadi) — maʼlumotlar strukturasi, qidiruv daraxti. Tashqi mantiqiy vakillik nuqtai nazaridan - muvozanatli, yuqori tarvaqaylab ketgan daraxt. Ko'pincha ma'lumotlarni tashqi xotirada saqlash uchun ishlatiladi. B-daraxtlardan foydalanish birinchi marta 1970 yilda R. Bayer va E. Makkreyt tomonidan taklif qilingan. Balanslangan degani, ildizdan barglargacha bo'lgan har qanday ikkita yo'lning uzunligi birdan ko'p bo'lmagan farqni anglatadi. Daraxtning shoxlanishi - har bir daraxt tugunining ko'p sonli avlod tugunlariga murojaat qilish xususiyati.
B-daraxtdan qattiq diskdagi (odatda metama'lumotlar) ma'lumotlarni tuzish (indekslash) uchun foydalanish mumkin. Qattiq diskdagi ixtiyoriy blokga kirish vaqti juda uzoq (millisekundlar tartibida), chunki u diskning aylanish tezligi va boshning harakati bilan belgilanadi. Shuning uchun, har bir operatsiyada skanerlangan tugunlar sonini kamaytirish muhimdir.
B-DARAXTLAR ISHLASH STRUKTURASI Tasodifiy blokni topish uchun har safar ro'yxat qidiruvidan foydalanish ushbu blokdan oldingi barcha elementlardan ketma-ket o'tish zarurati tufayli diskka kirishning haddan tashqari ko'p sonini keltirib chiqarishi mumkin, B-daraxtda qidirish esa xususiyatlar tufayli. muvozanat va yuqori dallanish, bunday operatsiyalar sonini sezilarli darajada kamaytirishi mumkin.
Tuzilishi va qurilish tamoyillari B-daraxt - bu quyidagi xususiyatlarga javob beradigan daraxt:
Har bir tugundagi kalitlar odatda oson kirish uchun buyurtma qilinadi. Ildiz 1 dan 2t-1 gacha kalitlarni o'z ichiga oladi.
Har qanday boshqa tugun t-1 dan 2t-1 gacha kalitlarni o'z ichiga oladi. Barglar bu qoidadan istisno emas. Bu erda t - kamida 2 bo'lgan daraxt parametri (va odatda 50 dan 2000 gacha qiymatlarni oladi).
public class IntBalancedSet implements Cloneable { private static final int MINIMUM = 200; private static final int MAXIMUM = 2*MINIMUM; int dataCount; int[ ] data = new int[MAXIMUM + 1]; int childCount; IntBalancedSet[] subset = new IntBalancedSet[MAXIMUM + 2]; // Constructor: initialize an empty set public IntBalancedSet() // add: add a new element to this set, if the element was already in the set, then there is no change. public void add(int element) // clone: generate a copy of this set. public IntBalancedSet clone() // contains: determine whether a particular element is in this set pubic boolean contains(int target) // remove: remove a specified element from this set public boolean remove(int target) }
"Tugunning har bir bolasi kichikroq B daraxtining ildizidir" B-DARAXTLARGA MISOLLAR Kalitni olib tashlash Agar ildiz ham barg bo'lsa, ya'ni daraxtda faqat bitta tugun bo'lsa, biz bu tugundan kalitni olib tashlaymiz. Aks holda, avval kalitni o'z ichiga olgan tugunni topamiz, unga yo'lni eslaymiz. Bu tugun {\displaystyle x}x bo'lsin.
Agar {\displaystyle x}x barg bo'lsa, u yerdan kalitni olib tashlang. Agar {\displaystyle x}x tugunida kamida {\displaystyle t-1}t-1 tugmalari qolgan boʻlsa, biz shu yerda toʻxtab qolamiz. Aks holda, biz ikkita qo'shni birodar tugunlaridagi kalitlar soniga qaraymiz. Agar qo‘shni o‘ng tugun bo‘lsa va uning hech bo‘lmaganda {\displaystyle t}t tugmalari bo‘lsa, u bilan qo‘shni o‘ng tugun o‘rtasida ajratuvchi kalitni {\displaystyle x}x ga qo‘shamiz va bu kalit o‘rniga birinchisini qo‘yamiz. qo'shni o'ng tugunning kaliti, keyin biz to'xtatamiz.
Asosiy afzalliklari Barcha holatlarda ikkilamchi saqlash joyidan foydali foydalanish 50% dan ortiq. Xotiradan foydalanish ortishi bilan xizmat sifati pasaymaydi. Yozuvga tasodifiy kirish kichik miqdordagi kichik operatsiyalar (fizik bloklarga havolalar) orqali amalga oshiriladi. O'rtacha hisobda yozuvlarni qo'shish va o'chirish operatsiyalari juda samarali amalga oshiriladi; ketma-ket ishlov berish uchun kalitlarning tabiiy tartibini saqlab turishda, shuningdek, tez tasodifiy tanlab olishni ta'minlash uchun daraxtning tegishli balansi.
Kalit bo'yicha o'zgarmas tartib partiyalarni samarali qayta ishlash imkonini beradi.
B-daraxtlarning asosiy kamchiligi shundaki, ular tanlangan kalitdan boshqa xususiyat tomonidan buyurtma qilingan ma'lumotlarni olishning samarali vositalariga ega emas (ya'ni daraxtni kesib o'tish usuli).
E’TIBORINGIZ UCHUN RAHMAT!
FOYDALANILGAN INTERNET RESURSLARI:
