[C] Cosa sono i B-tree ???

[_sys/sid]

Da titolo... Lascio la domanda libera...
Approfondiro' dopo... :-)

Cosa sono i B-Tree e come sono costruiti ?

Grazie.

[mondobimbi]

B-tree=albero binario
è una struttura dati molto efficiente quando bilanciata.
Un nodo della struttura contiene una chiave, il puntatore ai dati e un puntatore ai nodi figli, destro e sinistro.
Nel sottoalbero sx vanno inseriti i nodi la cui chiava è minore della chiave del nodo di riferimento, nel sottoalbero dx quelli con chiave maggiore.
Un esempio di nodo in c++

class TNode {

char * key ;
void * data;

TNode * left;
TNode * right;

public:

...
...

}

[internet]

Originariamente inviato da _sys/sid
Da titolo... Lascio la domanda libera...
Approfondiro' dopo... :-)

Cosa sono i B-Tree e come sono costruiti ?

Grazie.

E' difficile spiegarlo in poche righe, ti posso dire che sono alberi auto-bilancianti i cui nodi contengono un numero variabile di elementi (chiavi), e sono diversi come struttura dagli alberi binary (binary trees).

http://cs.hbg.psu.edu/courses/comp419.taw.s97/btree.gif

La maggiorparte dei DBMS ne fa uso per la memorizzazione degli indici (creati esplicitamente in SQL tramite CREATE INDEX http://www.postgresql.org/docs/curre...eateindex.html)

per maggiori info
http://www.bluerwhite.org/btree
http://sky.fit.qut.edu.au/~maire/bao...ure/sld001.htm

una demo in java
http://www.geocities.com/SiliconVall...ile/btree.html

[_sys/sid]

Grazie Mille...
(Per adesso sono aposto...)

[_sys/sid]

Cosa vuol dire Struttura Bilanciata ???

[Luc@s]

Originariamente inviato da _sys/sid
Cosa vuol dire Struttura Bilanciata ???

at rigth < n
at center n
at left > n

Questo è bilanciato

[internet]

Originariamente inviato da _sys/sid
Cosa vuol dire Struttura Bilanciata ???

Il bilanciamento a cui si riferisce quel link, è una proprietà di questi alberi, in cui nessuna foglia è più lontana dalla radice rispetto alle altre foglie. (la definizione esatta tiene conto della lunghezza di ogni cammino dalla radice a una foglia, e dipende dal tipo di alberi)

http://www.nist.gov/dads/HTML/balancedtree.html

albero non bilanciato

  [a]
    \
    [b]
      \
      [c]
        \
        [d]
          \
          [e]

albero bilanciato

    [c]
    / \
  [b] [d]
  /     \
[a]     [e]

[_sys/sid]

Ok... Per il Momento risposte e link, sembrano piu' che soddisfacenti...

Grazie Mille a tutti.