Enfilade (Xanadu) - Enfilade (Xanadu)

Enfiladlar sinfidir daraxt ma'lumotlar tuzilmalari ichida ishlatilgan Xanadu loyihasi 1970-80-yillarning "yashil" dizaynlari. Enfiladalar katta, o'zaro bog'langan gipermatnli ma'lumotlar bazasida tezkor tahrirlash, versiya, qidirish va taqqoslash operatsiyalarini amalga oshirishga imkon beradi. 1990-yillardan boshlab Xanadu "Gold" dizaynida tegishli ma'lumotlar tuzilmasi ishlatilgan Kirish.

Tuzilishi va xususiyatlari

Enfilad printsiplari har qanday daraxt ma'lumotlari tuzilmasida qo'llanilishi mumkin bo'lsa-da, Xanadu tizimida ishlatiladigan alohida tuzilma xuddi shunga o'xshash edi B-daraxt. Enfiladlarni ajratib turadigan narsa bu foydalanishdir dsps va tez daraxt tugunlari ichidagi indekslash ma'lumotlarida.

Dsplar - bu siljish, ofset yoki nisbiy kalitlar. DSP - bu o'z ichiga olgan tugun va subtree yoki bargning tugmachasi orasidagi farq. Masalan, xaritadagi panjara kvadratidagi barg bargning bir qismi bo'lgan kichik daraxt tomonidan ko'rsatilgan kattaroq panjaraga nisbatan ma'lum bir uzunlik va kenglik oralig'iga ega bo'lishi mumkin. Anfiladning har qanday bargining kaliti daraxtga tushgan yo'lda barcha dsplarni shu bargga birlashtirish orqali topiladi. DSP-lar bir vaqtning o'zida barcha subtree yoki tarkib oralig'iga yuqoridan pastga o'rnatilgan boshqa kontekst ma'lumotlari uchun ishlatilishi mumkin.

Kengliklar - kenglik, diapazon yoki cheklash qutilari. Wid - bu subtree yoki bargning kalitiga nisbatan, lekin subtree tarkibidagi barcha elementlarni o'z ichiga olgan bir qator manzillarni belgilaydi. Vidlar kam sonli manzil maydonlarining qiziqarli qismlarini aniqlaydi. Ba'zi bir enfiladlarda, berilgan tugun ostidagi kichik daraxtlarning vidalari bir-biriga to'g'ri kelishi mumkin va har qanday holatda, bir qator manzillar ichidagi ma'lumotlarni qidirish, vidalari qidiruv oralig'ini kesib o'tgan har qanday kichik daraxtlarga tashrif buyurishi kerak. Kengliklar daraxtning barglaridan yuqoriga qarab barcha qatlamlar orqali ildizgacha birlashtiriladi (garchi ular asta-sekin saqlanib turilsa ham). Vidlar, shuningdek, jami yoki maksimal darajadagi ma'lumotlar kabi boshqa xulosalarni o'z ichiga olishi mumkin.

Vidlar va dsplarning nisbiy tabiati subtretlarni enfilad ichida qayta tashkil etishga imkon beradi. Dspni subtree tepasida o'zgartirib, ostidagi barcha ma'lumotlarning kalitlari bilvosita o'zgartiriladi. Enfiladalarda tahrirlash operatsiyalari "kesish" yoki tegishli kirish yo'llari bo'ylab daraxtni ajratish, pastki daraxtlarni qo'shish, yo'q qilish yoki qayta tartiblash va bo'laklarni bir-biriga qaytarish orqali amalga oshiriladi. Kesish va birlashtirish operatsiyalari narxi odatda 1-o'lchovli daraxtlarda logga o'xshash va 2-o'lchovli daraxtlarda logga o'xshash va kvadrat ildizlarga o'xshashdir.

Daraxtlar, shuningdek, daraxtlar o'rtasida taqsimlanishi yoki daraxtning bir nechta joyidan bog'lanishi mumkin. Bu enfilatni to'liq qiladi doimiy ma'lumotlar tuzilishi tarkibni virtual nusxalash va versiyalash bilan. Subtree-ning har bir ishlatilishi dsps zanjiridan unga qadar turli xil kontekstni meros qilib oladi. Nusxadagi o'zgarishlar yangi tugunlarni faqat kesilgan yo'llar bo'ylab hosil qiladi va asl nusxasini joyida qoldiradi. Versiya uchun qo'shimcha xarajatlar juda kichik, yangi versiyaning daraxti muvozanatli va tezkor bo'lib, uni saqlash narxi faqat asl nusxadagi o'zgarishlarga bog'liq.

Bir o'lchovli fayllar massivlarning to'g'ridan-to'g'ri manzilliligi va bog'langan ro'yxatlarning kiritilishi, o'chirilishi va qayta joylashishi uchun qulayligi o'rtasida oraliqdir. Ko'p o'lchovli enfilatlar bo'shashgan, o'zgartirilishi mumkin, versiyaga o'xshaydi To'rtli daraxtlar, Okt daraxtlari yoki k-d daraxtlar.

Xanadudagi enfiladlarning turlari

The Model-T 1979 yilgacha Xanadu dizaynlarida ishlatilgan enfilade ma'lumot strukturasiga juda o'xshaydi Arqon. Belgilarning chiziqli ketma-ketliklarini osongina qo'shish, o'chirish, o'zgartirish va o'zgartirish bilan saqlaydi, lekin havolalar yoki versiyalar o'rtasida taqqoslash oson emas. Matn to'g'ridan-to'g'ri enfilad barglarida saqlanadi.

Keyinchalik Xanadu dizaynlari ko'proq bilvosita bo'ladi: istream (o'zgarmas oqim) deb nomlanuvchi, birlashtiriladigan kontent qismlarining o'sib boradigan to'plami foydalanuvchilar ko'radigan va ishlaydigan hujjatlarda, havolalarda va versiyalarda - virtual manzillarga ega. Enfilad turlari to'plami virtual va istream manzillari o'rtasida ikki tomonlama xaritalashni boshqaradi. Hujjatlar orasidagi yozishmalar va havolalarni izlash virtual, o'zgarmas va virtual manzillarga qaytarish orqali amalga oshiriladi. Shaxsiyatlarini eslab qoladigan va ularning barcha tashqi ko'rinishlarini kuzatib boradigan umumiy tarkibli qismlardan foydalangan holda hujjatlarni saqlash deyiladi Transklyuziya.

The POOMfilade (buyurtma matritsasining almashinishi) - bu a ni ifodalovchi 2 o'lchovli enfilad Permutatsion matritsa. Bu hujjat tarkibidagi birlashtirilgan tarkibdagi pozitsiyalarni istemol qilish uchun hujjatdagi virtual pozitsiyani xaritalaydi. POOM identifikatsiya matritsasini boshlaydi, keyin har bir hujjat qismiga tahrir qiladi va xaritaning gorizontal chiziqlarini qayta joylashtiradi. POOMni V-> I yoki I-> V yo'nalishlarida skvatsiyada, keng manzillar oralig'ida yoki baland bo'yli, tor joylarda qidirish orqali so'rash mumkin.

The Spanfilade hujjat yoki hujjatlar to'plami tomonidan foydalaniladigan istream tarkibidagi barcha oraliqlarni birlashtiradi. Span-setlarning kesishishini ikkita hujjat yoki hujjat versiyasidan olish hujjatlarni taqqoslashni tezlashtiradi. Xuddi shu mexanizm hujjat yoki unga havolalarni topish uchun ishlatiladi.

The Granfilad ushbu ma'lumotlarning barchasini disklarda va serverlar tarmog'ida saqlashni tashkil qiladi.

1999 yilgacha tijorat siri

Enfiladalar (ichki ma'lumotlar tuzilmalari) va istream manzillari Xanadu tashqi interfeyslariga ta'sir qilmaydi. Enfiladalar Xanadu kodi 1999 yilda ochiq manbaga ega bo'lgunga qadar tijorat sirlari bo'lgan va eslatib o'tilgan, ammo ba'zi nashrlarda shu vaqtgacha tushuntirilmagan, masalan.[1]

Xanadu tizimidagi mijoz-server aloqalarida vstream manzillari deb nomlangan formatda foydalaniladi stakanchalar.

Shuning uchun Enfilade atamasi bu erda aniq ko'rsatilmagan FeBe (Old end - Back end protokoli) hujjati, lekin uning o'rniga bilvosita qayd etilgan Xanalogik tuzilish va boshqa bir qator hujjatlar. Yuqorida aytib o'tilgan hujjatda, xu88 "Umumiy Enfilad nazariyasi" ga asoslanganligi ta'kidlangan.

Tarix

1972 yilda xu72 Enfilade kontseptsiyasini taqdim etdi. Bu "Model T Enfilade" deb nomlangan va so'zlarni qayta ishlash turi interfeysida ishlatilgan. 1976 yilda xu76 "mahkam bog'langan enfilade" ni amalga oshirdi. 1980 yilda xu80 tizimi versiyalash uchun mo'ljallangan enfilad deb ta'riflangan "ent" ni joriy qildi. 1988 yilda xu88 tizimida "Umumiy Enfilad nazariyasi" tushunchasi ishlatilgan Mark S. Miller, Styuart Grin va Rojer Gregori, "yuqoriga qarab tarqaladigan qidiruv xususiyati va bir vaqtning o'zida pastga yo'naltirilgan tuzilmaviy xususiyati bilan ma'lumotlarni boshqarish daraxtlarini yaratish" deb ta'riflangan. Xu88 shuningdek, Enfilade kontseptsiyasini tarqatilgan tarmoq orqali kengaytirdi, ikki o'lchovli Enfiladalarni taqdim etdi va butun qidirish algoritmini amalga oshirdi. hujjat Enfilade oralig'ini qoplash uchun. 1992 yilda xu92 entning zamonaviy kontseptsiyasini amalga oshirdi.[2]

Shuningdek qarang

Adabiyotlar

  1. ^ Adabiy mashinalar: Matnni qayta ishlash, elektron nashrlar, gipermatn, mutafakkirlar, ertangi kunning intellektual inqilobi va boshqa ba'zi mavzular, shu jumladan bilim, ta'lim va erkinlik haqida Xanadu loyihasi va uning hisoboti. (1981), Mindful Press, Sausalito, Kaliforniya.
  2. ^ Xanalogik tuzilish

Tashqi havolalar