SQL Duombazeje saugomo medžio algoritamas jūsų teismui
Viskas anot mano kvailumo yra paprasta:
jei laikytume medį funkcija, ji galima būtų pavaizduoti IV ketvirtyje. Jei laikytume kiekvieną eilutę (duombazės) tašku, jis turėtų dvi koordinates : x ir y.
X gali būti diskretus, nes medis "nukrypsta į dešinę" tik savo kartų skaičiumi (angl. gali būti level).
Jei Y (angl. gali būti sorting_order) būtų diskretus, turėtume problemą su įterpimais - t.y. kad įterptume elementą kur norime, reikėtų didinti visų sekančių eilučių Y koordinatę. Tuo tarpu, jei Y yra diskretus turėdami dviejų elementų Y galėtume tarp jų įterpti kiek norime eilučių.. pvž. aš pasirinkau tam laipsninę rodiklinę funkciją, kurios pagrindas skaičius a, 0
Įterpimas, atnaujinimas max. 3 užklausos (aš saugau objektą su amsyvu sesijoje, tad man ten viena : 'INSERT...').
Trinimas viena užklausa.
Laukių jūsų komentarų, kritikos...
Links:
Algoritmas be Y anologiškumo (ne diskretumo):Работа с MySQL
Daug algoritmų: Four ways to work with hierarchial data
Nuorodą į teisingą kelią:Trees in SQL
O gi mintys atėjo pritaikant dvimatį masyva ne mano js cascading menus scriptui:)
paveiksliukas turbūt copyright www.sitepoint.com
Comments
errr... o tipo ne paprasciau duombazes irase saugot tevinio iraso id?
tipo
id, parent_id, name
ir kai reikia iterpti, tai darai
oldChild = get parent child
newId = insert parentId, name
update oldChild set parent_id = newId
Posted by: mic | January 4, 2004 3:00 AM
Taip, bet kai reikia iš tokios duomenų padaryti medį, tai užtrunka...truputi laiko(kiek supratau medžio sudarimas, tai grafikas children, o tas tik su parent_id algoritmas vadinasi "Adjacency Lists"), o parent_id čia irgi neatsisakoma... galima atsisakyti tik pačio objekto id, nes sorting_order ( Y ) yra individualus... Beto su Adjacency Lists negalima nusakyti objekto vietos, tarp children...
(_E=mc^2_)
Posted by: Maksim | January 4, 2004 11:14 AM
aga, as taip pat toki rasiau, kazkur klase voliojas ;))
lft ir rgt papildomi irasai prie mazgo, o po to jau vartai kaip nori - nuo current mazgo viso medzio isrinkimas, su leveliu skaiciukais vienas selectas ;)
Posted by: Lakunas | January 4, 2004 2:31 PM
Sorry, gal kažko nesuprantu, bet.. Kaip tokiu atveju išrenkami tam tikro item'o sub-itemai?
Posted by: wikiz | January 4, 2004 5:27 PM
Lakunai, tu naudoji 'Nested sets' algoritmą, o aš kalbėjau apie 'Adjacency lists' patobulinimą:)
wikiz: Mano atvėju išrenkami visi elementai su ne didesne 'level' reikshme, nei duota, su mažesne sort_order reikšme nei duota, ir visi likusieji kur 'level'.
Lakuno atvėju, jei ne klystu, išrenkami visi elementrai kurie turiu mažesnes arba lygias rgt reikšmes už duoto elemento rgt. Toliau open mic perduodamas Lakunui į šitą algoritmą nesigilinau:), bet tuoj jaučiu reikes.
Posted by: Maksim | January 4, 2004 7:06 PM
isrinkimas tada atrodo taip:
vieno mazgo pasiimam lft ir rgt
SELECT lft, rgt FROM {$tree_table} WHERE id=$some_id
pasiimam eiliskumo tvarka:
SELECT * FROM {$tree_table} WHERE lft BETWEEN {$lft} AND {$rgt} ORDER BY lft ASD
kadanors damusiu ta klase ir galesiu public padeti teismuj kitu zmogenu :)
Posted by: Lakunas | January 4, 2004 7:19 PM
va:
http://www.sitepoint.com/article/1105/1
Posted by: Lakunas | February 17, 2004 11:33 AM