Hierarchy — elementlar parent–child munosabatida darajalarga joylashadigan ma’lumot tuzilmasi. Root elementning parenti bo‘lmaydi, leaf elementning childi yo‘q. Tashkilot bo‘limlari, fayl katalogi, mahsulot kategoriyasi va ruxsatlar daraxti iyerarxik modelga misol bo‘ladi.
Daraxt va graph chegarasi
Qat’iy daraxtda rootdan tashqari har node aynan bitta parentga ega va cycle mavjud emas. Node bir nechta parentga ega bo‘lsa directed acyclic graph bo‘lishi mumkin. Cycle paydo bo‘lsa, “ajdod” va “avlod” yurishi cheksiz takrorlanishi ehtimoli bor.
Model talabi boshidan aniqlanadi. Fayl katalogi odatda bitta parentli, mahsulot esa bir nechta kategoriyada ko‘rinishi mumkin. Daraxt deb qabul qilingan modelga multi-parent kiritish path, unique nom va deletion semantikasini buzadi.
Adjacency list
Relational databasedagi eng sodda model har qatorda parent_id saqlaydi:
CREATE TABLE categories (
id bigint PRIMARY KEY,
parent_id bigint REFERENCES categories(id),
name text NOT NULL
);
Bevosita parent yoki childni topish oson. Barcha avlodlarni yurish recursive CTE talab qiladi. parent_id indexi child qidiruvini tezlashtiradi. Foreign key mavjud parentni kafolatlaydi, ammo odatda uzoq cycle’ni to‘liq cheklamaydi.
Boshqa saqlash modellari
Materialized path har node’da rootdan kelgan yo‘lni saqlaydi. Prefix bo‘yicha subtree qidirish oson, lekin node ko‘chirilganda barcha avlod pathlari yangilanadi. Path segmentlarini escape qilish va 1/11 bilan 1/110ni ajratish qoidasi kerak.
Nested sets chap va o‘ng chegara bilan subtree’ni range queryda tez oladi. Insert va ko‘chirish ko‘p chegarani yangilashi mumkin. Closure table har ancestor–descendant juftini, ko‘pincha depth bilan saqlaydi; o‘qish tez, storage va write amplification kattaroq.
Yurish va tartib
Traversal depth-first yoki breadth-first bo‘lishi mumkin. “Birinchi daraja” rootni 0 yoki 1 deb hisoblashga qarab farq qiladi; API contractda aniq belgilanadi. Siblinglar tartibi alohida position ustunida saqlanmasa, nom yoki ID bo‘yicha tasodifiy ko‘rinish biznes tartibi bo‘lib qolmasligi kerak.
Path output qurishda bir xil nomli siblinglar va o‘zgargan nomlar hisobga olinadi. Stable identity sifatida ID, ko‘rsatish uchun name ishlatiladi. Faqat display pathga foreign key kabi tayanish rename’ni qimmatlashtiradi.
O‘zgartirish va o‘chirish
Nodeni boshqa parentga ko‘chirishdan oldin yangi parent uning o‘z avlodi emasligi tekshiriladi. Concurrent ko‘chirishlar cycle yoki yo‘qolgan update yaratmasligi uchun transaction va locking strategiyasi talab qilinadi.
Parent o‘chirilganda childlar cascade o‘chishi, parentga ko‘tarilishi yoki amal rad etilishi mumkin. Har tanlov biznes ma’noga ega. Katta subtree cascade delete uzoq lock va katta WAL yaratishi mumkin; batch va audit kerak.
Qo‘llanish xavflari
Ruxsat iyerarxiyasida child parent policy’ni meros olishi mumkin. Deny va allow precedence, inheritance uzilishi va multi-parent conflict aniq belgilanadi. Cache qilingan subtree schema o‘zgarganda invalidation talab qiladi. Testlar root, leaf, chuqur path, cycle urinish, orphan va parallel move holatlarini qamraydi.
Hajm va taqdimot
Juda chuqur hierarchy foydalanuvchi interfeysida ham muammo yaratadi. Barcha tree’ni birdan yuklash o‘rniga childlar lazy loading bilan olinadi, breadcrumb esa ajdod pathini ko‘rsatadi. Node soni va maksimal depth limitlari API abuse’ni cheklaydi. Search natijasi faqat nomni emas, uni ajratadigan parent pathini ham beradi. Daraxtni JSONga recursive serialize qilish stack depth va payload hajmini oshirishi mumkin; iterative traversal yoki sahifalangan endpoint ishlatiladi.
Bog‘liq tushunchalar
Tree, Graph, Parent-child relation, Recursive CTE, Adjacency list, Materialized path, Closure table, Cycle detection