Пређи на садржај

X-стабло

С Википедије, слободне енциклопедије

U informatici, X-stablo (енгл. eXtended node tree) је структура података која подржава ефикасну обраду упита више димензионих података. Идеја је да X-стабло може да подржи и проширене просторне податке због чега користи концепт преклапајућих региона. X-стабло избегава преклапања када год је то могуће без могућности дегенерисања стабла; иначе, X-стабло користи проширене, директоријумске чворове различитих величина, такозване суперчворове. Осим тога што пружа директоријумску организацију која је погодна за високо-димензионе податке, X-стабло ефикасније користи слободну главну меморију (у поређењу са коришћењем кеша).

X-стабло се може посматрати као хибрид нечега налик линеарном низу и хијерархијском Р-стаблу. Проблем је динамички организовати стабло тако да делови података који доводе до великих преклапања буду организовани линеарно а они који могу да се организују хијерархијски без већих преклапања буду динамички организовани у хијерархијску форму. Алгоритми који се користе код X-стабла су дизајнирани да аутоматски организују директоријум хијерархијски колико је то могуће, што као резултат даје веома ефикасну хибридну организацију.

Структура X-стабла[уреди | уреди извор]

Структура X-стабла
Примери X-стабла различитих димензија

X-стабло се састоји од три врсте чворова:

  • чворова података
  • нормалних директоријумских чворова
  • суперчворова.

Суперчворови су велики директоријумски чворови различите величине (умножак уобичајене величине блока). Главни циљ суперчворова је да избегну раздвајања у директоријуму која као резултат имају неефикасну директоријумску структуру. Алтернатива коришћења великих чворова су високо преклапајући директоријумски чворови који захтевају приступ већини чворова-синова током процеса претраге. Ово је доста неефикасније од линеарне претраге великих суперчворова. Напомена да је X-стабло потпуно другачије од Р-стабла са већом величином блока због тога што се X-стабло састоји од већих чворова само на местима где је то потребно. Суперчворови се креирају током уметања само ако не постоји други начин да се избегне преклапање. Ако је доступно довољно слободне меморије, суперчворови се чувају у главној меморији. У супротном, чворови који се морају заменити се утврђују на основу функције за приоритет која зависи од нивоа, типа (нормални чвор или суперчвор) и величине чвора.

Претпостављајући да одређена количина података заузима блокова за максимално попуњен чвор, тада је истој количини података потребно блокова користећи минимално попуњен чвор. У просеку, суперчвор који складишти исту количину података захтева блокова. Одатле добијамо складишну искоришћеност од што за велико м износи знатно више од 66% (за нормалне директоријумске чворове очекивана искоришћеност за униформно дистрибуиране податке износи око 66%). На пример, за м=5 износи 88%.

Алгоритми[уреди | уреди извор]

Најважнији алгоритам код X-стабла је алгоритам за уметање. Он утврђује структуру X-стабла која је погодна комбинација хијерархијске и линеарне структуре. Главни циљ алгоритма је да избегне раздвајања која доводе до преклапања. Алгоритам прво утврђује минимални обухватни правоугаоник (МБР енгл. minimum bounding rectangle) у који се потенцијално умеће податак и рекурзивно се позива алгоритам за стварно уметање податка у одговарајући чвор. Ако не додје до раздвајања током рекурзивног уметања, само се величина одговарајућег МБР-а ажурира. У случају раздвајања подчвора додатни МБР се мора додати теренутном чвору који може изазвати прекорачење у чвору. У том случају тренутни чвор позива алгоритам раздвајања који прво покушава да пронађе раздвајање чвора на основу тополошких и геометријских особина МБР-а. Ако резултати тополошког раздвајања доводе до преклапања, алгоритам раздвајања покушава да утврди следеће раздвајање са минималним преклапањем што се утврђује на основу историје раздвајања.

Код алгоритма за уметање: 

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;
}

Код алгоритма раздвајања: 

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;
}

Перформансе[уреди | уреди извор]

На основу обимних процена перформанса X-стабла и упоређивања са ТВ-стаблом и Р*-стаблом користећи до 100 МБ линеарних и просторних података показало се да је X-стабло надмашило ТВ-стабло и Р*-стабло и до неколико редова величине за упите најближег суседа и најближе тачке са синтетичким као и са реалним подацима.

Упоређивање X-стабла и Р*-стабла на основу приступа страницама (лево) и процесорског времена(десно)
Убрзање X-стабла над Р*-стаблом у односу на синтетичке подтаке (лево) и реалне просторне податке (десно)
Упоређивање X-стабла и Р*-стабла на основу времена обраде упита у зависности од величине података (лево) и упоређивање X-стабла, ТВ-стабла и Р*-стабла у односу на синтетичке податке(десно)

Види још[уреди | уреди извор]

Литература[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=X-stablo&oldid=26792601”