Visai neseniai susidūriau su tokia, atrodytų paprasta problemėle. Reikia atvaizduoti, saugoti ir turėti galimybę manipuliuoti hierarchinės struktūros duomenimis, saugant duomenis MySQL duomenų bazėje. “Kame problema?” – pirmas kylantis klausimas. Visas įdomumas atsiranda tada, kai reikalinga galimybė keisti medžio lapų eiliškumą. Na, gal apie viską iš eilės.

Tam, kad saugoti hierarchinio medžio struktūrą pakanka vieno papildomo lentelės stulpelio, kuris nurodytų tėvinį įrašo elementą. Pavyzdžiui, turint lentelę su kategorijomis, kurios aprašomos atributais `id` ir `pavadinimas`, galime sukurti papildomą lauką `tėvo_id`, kuris nurodys kurios kategorijos vaikas yra einamoji kategorija. O tam, kad iš tokių duomenų suformuoti medį, užtenka paprastos rekursyvios funkcijos (įmanoma ir duomenų bazės valdymo sistemos lygyje). Tačiau naudojant tokią struktūrą, nėra galimybės rūšiuot medžio lapų kokia nors specifine tvarka. Geriausia, ką galima padaryti, tai išrūšiuoti pagal identifikatorių, pavyzdžiui taip, kad anksčiau sukurti lapai būtų kairiau, o vėliau – dešiniau, einamojo lapo lygyje. Vaizdas gali gautis panašus į tokį:

Įsivaizduokime, kad norime 2 ir 6 lapą apkeisti vietomis, kartu su visais tų lapo vaikais. O jeigu įterpti naują 1 vaiką, bet taip, kad jis būtų tarp 3 ir 6 lapų? Šitoje vietoje ir prasidėjo. Neilgai pagooglinęs ir prisiminęs pirmą universiteto kursą, radau kelis problemos sprendimo būdus.

Left-Right medis

Šiuo atveju kiekvienam iš medžio lapų yra priskiriami 2 atributai – left ir atitinkamai right. Šiomis reikšmėmis ir yra aprašomi sąryšiai tarp medžio lapų. Pavyzdžiui, imame kokį nors medžio lapą A su reikšmėmis left1 ir right1. Visi lapai, kurie būtų lapo A vaikai, anukai ir t.t. privalo turėti reikšmę left didesnę, negu left1 ir reikšmę right didesnę, negu right1 (lefti > left1 ir righti < right1).

Paveikslėlis: Gijs Van Tulder

Štai čia vieno iš tokių medžių pavyzdys. Tokio saugojimo būdo privalumas yra tas, kad beveik visus veiksmus su medžiu galima atlikti pasinaudojus viena užklausa. Jį gerai naudoti, kai medis yra “platus” – viename lygyje gali būti daug elementų. Tokia technika yra plačiai naudojama dėl savo privalumų – pavyzdžiui, CakePHP karkasas turi integruotą modelių elgseną, pavadinimu “Tree“, kuri naudoja būtent left-right tree. Algoritmas veikia labai greitai, kai pagrindinis veiksmas su medžiu yra jo “išgavimas” iš duomenų bazės, tačiau jis turi ir minusų – tam, kad atnaujinti duomenis (pavyzdžiui, sukeisti šakas vietomis) reikia atlikti daug sudėtingų veiksmų. Plačiau apie šį saugojimo būdą galima paskaityti pavyzdžiui čia.

Skaitinis rikiavimas su intervalais

Šis būdas yra visiškai kitoks. Naudojama technika, kuri leidžia rikiuoti elementus norima tvarka. Kalbant trumpai – kiekvienam elementui yra priskiriama tam tikra order skaitinė reikšmė, su tam tikru kuo įmanoma didesniu intervalu. Gaunant duomenis iš duomenų bazės yra rikiuojama pagal šią reikšmę ir gaunamas išrūšiuotas sąrašas. Kai reikia elementus apkeisti vietomis tai tiesiog sukeičiamos šių elementų order reikšmės. Jeigu reikia įterpti elementą tarp dviejų kitų – imama vidurinė order reikšmė tarp dvejų kaimyninių elementų. Pavyzdžiui, turima lentelė:

id name order
1 Petras 0
2 Jonas 10
3 Antanas 20
4 Juozas 30
5 Mantas 40

Kadangi, kaip galima pastebėti, order žingsnis yra lygus 10, pridedant naują įrašą į sąrašo pabaigą jam būtų priskirta order reikšmė 50. Sekančiam įrašui – 60 ir t.t.

Atsiradus situacijai, kai įrašą reikia įterpti tarp dviejų elementų, pavyzdžiui, tarp 3 ir 4 įrašų, imama vidurinė reikšmė tarp tų įrašų order reikšmių – (20 + 30)/2 = 25. Todėl pridedamas įrašas su order reikšme 25. Į akį iškarto krenta problema – o kas bus, kai tokios reikšmės pasibaigs? Pavyzdžiui, kai reikia įterpti elementą tarp tokių įrašų, kurių order reikšmės skiriasi tik vienetu. Bandant kuo labiau atidėti tokių situacijų atsiradimą, naudojamas kuo įmanoma didesnis order žingsnis. Tačiau tai nepašalina problemos, o tik ją atideda. Bet kuriuo atveju ateis tas momentas, kai reikės atnaujinti visų įrašų order reikšmes, kad atsirastų vietos naujų įrašų įterpimui. Tai ir yra šio metodo didžiausias trūkumas.

"+1" metodas

Tai ir buvo mano pasirinktas realizacijos būdas. Šiuo atveju irgi egzistuoja order laukas, tačiau jis priskiriamas be jokių intervalų – tiesiog iš eilės einantys skaičiai. Elementų vietomis apkeitimas – order reikšmių apkeitimas. O įterpiant elementą tarp dviejų elementų reikia įvykdyti vieną papildomą užklausą. Ji turėtų atnaujinti rikiavimo reikšmes tiems elementams, kurie eina po norimos įterpimo vietos. Pavyzdžiui, norint įterpti įrašą tarp jau esamų 4 ir 5 įrašo, reikėtų atnaujinti visų įrašų, kurie eina po 4-ojo, order reikšmes pridedant jiems po 1 (+1):

UPDATE `items` SET `order` = `order` + 1 WHERE `order` > 4

Kalbant apie medžio struktūrą, tokiu atveju reikėtų atnaujinti tik tuos įrašus, kurie yra tam pačiam lygyje, į kurį bandoma įterpti įrašą, todėl atnaujinamų įrašų skaičius dar labiau sumažėja.

Kodėl pasirinkau būtent šitą metodą? Mano atveju buvo numatyta, kad elementų įterpimas, jų apkeitimas vietomis ir kitas manipuliavimas medžiu bus dažnas procesas. Prie to, medis numatomas ne platus, bet aukštas (t.y. bus daug lygių, kiekviename iš kurių nebus labai daug elementų). Antras metodas iškarto atkrito – reikėtų naudoti didelius žingsnius (o reiškia ir didelius skaičius, kas reikalauja daug resursų) ir palyginus dažnai vykdyti duomenų bazės “pertvarkimą”, kai pasibaigia įterpimo variantai. Besirenkant tarp pirmo ir trečio metodų atsižvelgiau į medžio specifiką. Left-right tree būdas yra labai geras ir pritaikytas būtent tokių medžių saugojimui, bet reikalauja daugiau veiksmų, kai norima atlikti mano atveju svarbius ir dažnai naudojamus veiksmus. Todėl šiai konkrečiai situacijai tiko būtent trečias metodas. Tačiau tai nereiškia, kad jis yra geriausias – manau, kad nei vieno iš šių metodų negalima pavadinti “geriausiu“, o kurį iš jų taikyti visiškai priklauso nuo situacijos ir numatomų medžio savybių.