[Basi di dati] da albero binario di ricerca a tabella
Qualcuno sa spiegarmi come un albero binario di ricerca puo essere stampato in forma di tabella quindi a matrice a array multidimensionale. Premetto che secondo me sono concetti diversi. Ma nei database esiste una rappresentazione tabellare dei dati e una in albero binario di ricerca. Non trovo e capisco la corrispondenza tra i due.
Risposte
Non sono sicuro a cosa tu ti riferisca in ambito dei database, ma il tuo albero può essere visitato in ordine ottenendo un array ordinato di elementi. Se ogni elemento è poi una tupla di valori allora puoi certamente visualizzarlo come una tabella in cui ad ogni riga corrisponde un elemento del tuo albero.
grazie per la risposta.
Intendo dire, io posso inserire tutti gli elementi di un array fatto da 3 righe * 5 colonne = 15 elementi in un albero binario di ricerca e cosi avrei tutta la tabella nell'albero.
Potrei soffermarmi solo nella creazione di indici cioè tutti i valori di una colonna della tabella gli inserisco nell'albero binario di ricerca. Cosi so che quelli sono dati di una colonna. Ma poi come faccio a fargli fare la JOIN con un'altra colonna sempre rappresentata con albero binario di ricerca. Cosa puo voler dire fare la JOIN tra due alberi binari di ricerca.
In C so implementare una struttura a puntatori che mi rappresenta la tabella che puo essere ridimensionata a piacere ed avere campi di diversi tipi interi, char* , float.
Questo compito mi serve per implementare un parser simile a sqlite che lavori sui dati in forma tabellare.
Ma leggevo che la struttura utilizzata da db è quella ad albero binario di ricerca: i B tree.
Intendo dire, io posso inserire tutti gli elementi di un array fatto da 3 righe * 5 colonne = 15 elementi in un albero binario di ricerca e cosi avrei tutta la tabella nell'albero.
Come faccio a implementare una visita (tra in ordine, pre ordine, post ordine) che mi invece mi stampa la cella0, la cella1, la cella2 se gli elementi sono inseriti anche in ordine sparso nell'albero come ad esempio cella3, cella1, cella4, cella2.
Potrei soffermarmi solo nella creazione di indici cioè tutti i valori di una colonna della tabella gli inserisco nell'albero binario di ricerca. Cosi so che quelli sono dati di una colonna. Ma poi come faccio a fargli fare la JOIN con un'altra colonna sempre rappresentata con albero binario di ricerca. Cosa puo voler dire fare la JOIN tra due alberi binari di ricerca.
In C so implementare una struttura a puntatori che mi rappresenta la tabella che puo essere ridimensionata a piacere ed avere campi di diversi tipi interi, char* , float.
Questo compito mi serve per implementare un parser simile a sqlite che lavori sui dati in forma tabellare.
Ma leggevo che la struttura utilizzata da db è quella ad albero binario di ricerca: i B tree.
Se hai una tabella con 5 colonne, l'albero sarà costruito a partire dal valore della chiave primaria e ogni riga e salvata come un blocco unico. C'è insomma differenza tra quella che è la chiave usata nell'albero di ricerca e i valori salvati nelle foglie corrispondenti alle specifiche chiavi. Nel tuo esempio ci saranno quindi solo 3 elementi nell'albero, non 15. Questo è però un discorso un po' generico perché non c'è alcuna restrizione sulla rappresentazione dei dati in memoria da parte di un DBMS. Altre rappresentazioni sono comuni e dipendono da cosa si vuole ottimizzare. Alcuni DBMS memorizzano per esempio le colonne separatamente mentre altri memorizzano ogni riga come un blocco unico. Se non ti interessa l'ordine puoi usare delle tabelle di hash per esempio invece di un albero o fregartene di strutture complesse e avere semplicemente un array.
Cosa intendi con parser simile a Sqlite. Un parser per SQL?
Cosa intendi con parser simile a Sqlite. Un parser per SQL?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo