X-stablo

U informatici, X-stablo (енгл. eXtended node tree) je struktura podataka koja podržava efikasnu obradu upita više dimenzionih podataka. Ideja je da X-stablo može da podrži i proširene prostorne podatke zbog čega koristi koncept preklapajućih regiona. X-stablo izbegava preklapanja kada god je to moguće bez mogućnosti degenerisanja stabla; inače, X-stablo koristi proširene, direktorijumske čvorove različitih veličina, takozvane superčvorove. Osim toga što pruža direktorijumsku organizaciju koja je pogodna za visoko-dimenzione podatke, X-stablo efikasnije koristi slobodnu glavnu memoriju (u poređenju sa korišćenjem keša).

X-stablo se može posmatrati kao hibrid nečega nalik linearnom nizu i hijerarhijskom R-stablu. Problem je dinamički organizovati stablo tako da delovi podataka koji dovode do velikih preklapanja budu organizovani linearno a oni koji mogu da se organizuju hijerarhijski bez većih preklapanja budu dinamički organizovani u hijerarhijsku formu. Algoritmi koji se koriste kod X-stabla su dizajnirani da automatski organizuju direktorijum hijerarhijski koliko je to moguće, što kao rezultat daje veoma efikasnu hibridnu organizaciju.

Struktura X-stabla

Struktura X-stabla
Primeri X-stabla različitih dimenzija

X-stablo se sastoji od tri vrste čvorova:

  • čvorova podataka
  • normalnih direktorijumskih čvorova
  • superčvorova.

Superčvorovi su veliki direktorijumski čvorovi različite veličine (umnožak uobičajene veličine bloka). Glavni cilj superčvorova je da izbegnu razdvajanja u direktorijumu koja kao rezultat imaju neefikasnu direktorijumsku strukturu. Alternativa korišćenja velikih čvorova su visoko preklapajući direktorijumski čvorovi koji zahtevaju pristup većini čvorova-sinova tokom procesa pretrage. Ovo je dosta neefikasnije od linearne pretrage velikih superčvorova. Napomena da je X-stablo potpuno drugačije od R-stabla sa većom veličinom bloka zbog toga što se X-stablo sastoji od većih čvorova samo na mestima gde je to potrebno. Superčvorovi se kreiraju tokom umetanja samo ako ne postoji drugi način da se izbegne preklapanje. Ako je dostupno dovoljno slobodne memorije, superčvorovi se čuvaju u glavnoj memoriji. U suprotnom, čvorovi koji se moraju zameniti se utvrđuju na osnovu funkcije za prioritet koja zavisi od nivoa, tipa (normalni čvor ili superčvor) i veličine čvora.

Pretpostavljajući da određena količina podataka zauzima blokova za maksimalno popunjen čvor, tada je istoj količini podataka potrebno blokova koristeći minimalno popunjen čvor. U proseku, superčvor koji skladišti istu količinu podataka zahteva blokova. Odatle dobijamo skladišnu iskorišćenost od što za veliko m iznosi znatno više od 66% (za normalne direktorijumske čvorove očekivana iskorišćenost za uniformno distribuirane podatke iznosi oko 66%). Na primer, za m=5 iznosi 88%.

Algoritmi

Najvažniji algoritam kod X-stabla je algoritam za umetanje. On utvrđuje strukturu X-stabla koja je pogodna kombinacija hijerarhijske i linearne strukture. Glavni cilj algoritma je da izbegne razdvajanja koja dovode do preklapanja. Algoritam prvo utvrđuje minimalni obuhvatni pravougaonik (MBR енгл. minimum bounding rectangle) u koji se potencijalno umeće podatak i rekurzivno se poziva algoritam za stvarno umetanje podatka u odgovarajući čvor. Ako ne dodje do razdvajanja tokom rekurzivnog umetanja, samo se veličina odgovarajućeg MBR-a ažurira. U slučaju razdvajanja podčvora dodatni MBR se mora dodati terenutnom čvoru koji može izazvati prekoračenje u čvoru. U tom slučaju trenutni čvor poziva algoritam razdvajanja koji prvo pokušava da pronađe razdvajanje čvora na osnovu topoloških i geometrijskih osobina MBR-a. Ako rezultati topološkog razdvajanja dovode do preklapanja, algoritam razdvajanja pokušava da utvrdi sledeće razdvajanje sa minimalnim preklapanjem što se utvrđuje na osnovu istorije razdvajanja.

Kod algoritma za umetanje: 

int X_DirectoryNode::insert(DataObject obj, X_Node **new_node)
{
  SET_OF_MBR *s1, *s2;
  X_Node *follow, *new_son;
  int return_value;
  follow = choose_subtree(obj); // bira se čvor-sin u koji se umeće objekat
  return_value = follow->insert(obj, &new_son); // umeće se objekat u podstablo
  update_mbr(follow->calc_mbr()); // ažurira se MBR starog čvor-sina
  if (return_value == SPLIT)
  {
    add_mbr(new_son->calc_mbr()); // umeće se mbr novog čvor-sina u trenutni čvor
    if (num_of_mbrs() > CAPACITY) // u slučaju prekoračenja
    {
      if (split(mbrs, s1, s2) == TRUE)// u slučaju ako rezltati topološkog razdvajanja ne dovode do preklapanja
      {
        set_mbrs(s1);
        *new_node = new X_DirectoryNode(s2);
        return SPLIT;
      }
      else // u slučaju da nema zadovoljavajućih razdvajanja
      {
        *new_node = new X_SuperNode();
        (*new_node)->set_mbrs(mbrs);
        return SUPERNODE;
      }
    }   
  } else if (return_value == SUPERNODE){ // čvor ‘follow’ postaje superčvor
    remove_son(follow);
    insert_son(new_son);
  }
  return NO_SPLIT;
}

Kod algoritma razdvajanja: 

bool X_DirectoryNode::split(SET_OF_MBR *in, SET_OF_MBR *out1, SET_OF_MBR *out2)
{
  SET_OF_MBR t1, t2;
  MBR r1, r2;
  // prvo pokušava topološko razdvajanje koje kao rezultat ima dva seta MBR-a t1 i t2
  topological_split(in, t1, t2);
  r1 = t1->calc_mbr(); r2 = t2->calc_mbr();
  // proverava preklapanja
  if (overlap(r1, r2) > MAX_OVERLAP)
  {
    // topološko preklapanje neuspešno -> pokušava razdvajanje sa minimalnim preklapanjem
    overlap_minimal_split(in, t1, t2);
    // proverava da li postoje nebalansirani čvorovi
    if (t1->num_of_mbrs() < MIN_FANOUT || t2->num_of_mbrs() < MIN_FANOUT)
    // razdvajanje sa minimalnim preklapanjem takođe neuspešno (-> pozivaoc mora da kreira superčvor)
      return FALSE;
  }
  *out1 = t1; *out2 = t2;
  return TRUE;
}

Performanse

Na osnovu obimnih procena performansa X-stabla i upoređivanja sa TV-stablom i R*-stablom koristeći do 100 MB linearnih i prostornih podataka pokazalo se da je X-stablo nadmašilo TV-stablo i R*-stablo i do nekoliko redova veličine za upite najbližeg suseda i najbliže tačke sa sintetičkim kao i sa realnim podacima.

Upoređivanje X-stabla i R*-stabla na osnovu pristupa stranicama (levo) i procesorskog vremena(desno)
Ubrzanje X-stabla nad R*-stablom u odnosu na sintetičke podtake (levo) i realne prostorne podatke (desno)
Upoređivanje X-stabla i R*-stabla na osnovu vremena obrade upita u zavisnosti od veličine podataka (levo) i upoređivanje X-stabla, TV-stabla i R*-stabla u odnosu na sintetičke podatke(desno)

Vidi još

Literatura