b-daraxtlar

DOC 13 стр. 1,3 МБ Бесплатная загрузка

13 стр.

FaylHub.uz

Скачать через Telegram

Размер 1,3 МБ

Тип файла DOC

Страницы 13

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 13

3-ma’ruza. b-daraxtlar b-daraxt tushunchasi bilan tanishish uchun qattiq disklarda ma’lumotlar qanday saqlanishi haqida to’xtalib o’taylik. shu orqali b-daraxt tushunchasi yaxshiroq o’rganishga harakat qilamiz. qattiq disk (hdd) - bu konsentrik doiralarda - treklar (tracks) da saqlanadigan plastinlar (platters) yig‘indisi.  ma'lumotlar golovkalar (heads) tomonidan o'qiladi / yoziladi  plastinlar va golovkalar dvigatellar tomonidan boshqariladi  sektor (sector) - trekning bir qismi (qattiq diskning minimal adreslanadigan birligi)  klaster (klaster) - bu trekdagi sektorlar to'plami  silindr (silindr) - bir nechta plastinlar bir joyiga qo'yilgan yo'llar to'plami sektorga kirish vaqti (seek time) plastinlar aylanish tezligiga bog'liq bir daqiqada aylanishlar (rpm) kirish vaqti (rotational latency) 5400 rpm 0.011 s. 7200 rpm 0.008 s. 15 000 rpm 0.004 s. operativ xotiraga kirish vaqti (≈ 10 ns) diskka kirish vaqtidan 105 baravar kam. solid state drives (ssd) qattiq holatdagi disk (flesh-disk, ssd) - bu xotira chiplariga asoslangan mexanik bo'lmagan saqlash moslamasi ssd-da qidirish vaqtini bloklash …

2 / 13

0 · google gmail foydalanuvchilari soni (2012 yil iyun): · 425,000,000 · vkontakte foydalanuvchilari soni (2013 yil fevral): · 43,000,000 · yechim: tashqi xotiradan foydalaning - hdd / ssd disklari, tarmoq xotirasi b-daraxt (b-tree) b-daraxt - bu tugunlari tashqi xotirada saqlanadigan (masalan, hdd / ssd-da) muvozanatli qidiruv daraxti. har qanday vaqtda, b daraxtining faqat bir qismi operativ xotirada (daraxtning kattaligi operativ xotira miqdoridan sezilarli darajada oshib ketishi mumkin) ·  b-daraxtlar fayl tizimlarida va ma'lumotlar bazasini boshqarish tizimlarida (mbbt) ishlatiladi · rud rudolf bayer va edvard m. makkreyt tomonidan boeing tadqiqot laboratoriyalari, aqsh, 1971 yilda yaratilgan. ·  b daraxtlari nomidagi "b" harfi: boeing, bayer, ... · b daraxtining balandligi o(logn) dan oshmaydi, bu erda n - daraxtdagi tugunlar soni ·  b-daraxt tugunlarida ko'plab avlod tugunlari bo'lishi mumkin - · mingtagacha ·  b daraxtining har bir tugunida 1 tadan ortiq kalit bo'lishi mumkin ·   agar ichki …

3 / 13

a oladi - har bir tugun maksimal 2t - 1 kalitni va maksimal 2t avlod tugunini o'z ichiga oladi (barglar bundan mustasno) - tugun to'liq (full) deyiladi, agar u 2t - 1 kalitni o'z ichiga olsa. 2-3-4 daraxt t = 2, har bir tugunda 2, 3 yoki 4 ta tugun bo'lishi mumkin b-daraxt balandligi n-1 kalitlari va minimal darajasi t-2 bo'lgan b daraxtining balandligi eng yomon holatda logt((n + 1) / 2) dan oshmaydi. b-daraxtlar ustida amallar  barcha amallarda biz quyidagilarni qabul qilamiz: - b daraxtining ildizi doimo operativ xotirada bo'ladi - diskread va diskwrite protseduralari diskka ma'lumotlarni o'qish va yozish uchun ishlatiladi b daraxti tashqi xotiraga murojaatlar sonini minimallashtiradi (diskread, diskwrite-ga) elementni izlash (lookup) 1) biz daraxtning ildizidan qidirishni boshlaymiz. berilgan k kaliti uchun joriy tugunning kalitlari orasida key1 ≤ key2 ≤… ≤keyn uchun biz birinchi keyi ni topamiz, masalan k ≤ keyi 2) k = keyi bo'lsa, …

4 / 13

o'rta kalitni ajratuvchi 4) median kalit ajdod tuguniga kiritiladi. agar ajdod tugun to'la bo'lsa, u bo'linadi va protsedura yuqorida aytib o'tilganidek takrorlanadi. daraxtga ko'tarilish ildizigacha davom etishi mumkin. daraxtning ildizidan kerakli bargga o'tayotganda biz o'tadigan barcha to'ldirilgan tugunlarni ajratamiz (split) (shu jumladan barg).  bu tugunni ajratish kerak bo'lsa, uning ajdodi to'ldirilmasligini ta'minlaydi. tugunni ajratish (split) eng yomon holatda b daraxtiga kalitni kiritishning hisoblash murakkabligi (biz har bir darajadagi tugunlarni ajratamiz): 𝑇 = 𝑂 𝑡ℎ = 𝑂(𝑡 log𝑡 𝑛) diskdagi amallar soni: 𝑇𝐷𝑖𝑠𝑘 = 𝑂 ℎ = 𝑂(log𝑡 𝑛) b-daraxt turlari b+-daraxt (b+-tree) - bu faqat barglarda ma'lumotni o'z ichiga oladigan va ichki tugunlarda faqat kalitlarni saqlaydigan b daraxti.  b *-daraxt (b * -tree) - unda har bir tugun (ildizdan tashqari) b daraxtidagi kabi 1/2 emas, balki kamida 2/3 kalitni o'z ichiga olishi kerak. 2-3-4-b-daraxtlarni realizatsiya qilish b-daraxtni realizatsiya qilish bitta kalit ikkita kalit ikkita kalit kalit tugun uch …

5 / 13

Хотите читать дальше?

Скачайте все 13 страниц бесплатно через Telegram.

Скачать полный файл

О "b-daraxtlar"

3-ma’ruza. b-daraxtlar b-daraxt tushunchasi bilan tanishish uchun qattiq disklarda ma’lumotlar qanday saqlanishi haqida to’xtalib o’taylik. shu orqali b-daraxt tushunchasi yaxshiroq o’rganishga harakat qilamiz. qattiq disk (hdd) - bu konsentrik doiralarda - treklar (tracks) da saqlanadigan plastinlar (platters) yig‘indisi.  ma'lumotlar golovkalar (heads) tomonidan o'qiladi / yoziladi  plastinlar va golovkalar dvigatellar tomonidan boshqariladi  sektor (sector) - trekning bir qismi (qattiq diskning minimal adreslanadigan birligi)  klaster (klaster) - bu trekdagi sektorlar to'plami  silindr (silindr) - bir nechta plastinlar bir joyiga qo'yilgan yo'llar to'plami sektorga kirish vaqti (seek time) plastinlar aylanish tezligiga bog'liq bir daqiqada aylanishlar (rpm) kirish vaqti (rotational...

Этот файл содержит 13 стр. в формате DOC (1,3 МБ). Чтобы скачать "b-daraxtlar", нажмите кнопку Telegram слева.

Теги: b-daraxtlar DOC 13 стр. Бесплатная загрузка Telegram