Please enable JavaScript.
Coggle requires JavaScript to display documents.
Ricerca Esterna - Coggle Diagram
Ricerca Esterna
Ricerca di Vario Tipo
Chiave
Corrispondenze Parziali
Chiavi Multiple
Other(Rango,...)
Paginazione Alberi Binari
Metodo Sequenziale
inserisci nodi prima pagina
attivo un altra pagina solo quando piena
utilizzo ottimale della memoria
n medio di accessi a pagina
poco più di 2 per ogni ricerca
si potrebbe tenere la pagina della radice
sempre in memoria per diminuire il costo
Metodo Raggruppato
si alloca il nodo nella pagina del padre
se ci sono posizioni libere
si crea nuova pagina altrimenti
si spreca + spazio
n° di accessi a pagina crolla drasticamente
Metodo delle pagine attive
Inizializzo q pagine attive
Se il padre è in una pagina attiva,
metto lì il nodo
Altrimenti, seleziona la pagina attiva più vuota e lo posiziona lì
Fissare un n° q di pagine attive
Quando si riempie una pagina ne attivo un altra
n° pagine alloccate: max p+q
n° medio accessi: diminuisce al crescere di q
non la + efficiente
SOLUZIONE:
ALBERI BILANCIATI
alberi 2-3
ogni nodo può avere 2 chiavi e 3 figli
le foglie sono TUTTE sullo stesso livello
Strutture Ricerca Esterna
Catena Doppia non ordinata
Ram-Search : O(N)
Insert e Delete: O(1)
EM Search O(N/B)
Array ordinato
Ram: Insert Delete O(N)
Search O(log N)
EM: Search O(log_2 N)
Insert e Delete O(N/B)
Alberi Bilanciati
Ram: insert delete Search O(log_2 N)
EM: O(log_2 N)
Elementi
Pagine
blocchi contigui di dati
il primo accesso ad una pagina
è detto sondagggio
Indice
sovrastuttura che permette
di recuperare velocemente
il riferimento ad un dato elemento
contenente chiavi
e riferimenti agli elementi
permette operazioni:
Range Query
Next
modifica base di dati
(ricerca, inserimento, cancellazione)
primario
o
secondario
primario= riflette la struttura dei dati
secondario= non riflette la struttura dei dati
ordine diverso dall'indice primario
Tecniche di Indicizzazione
Record
t valori per altrettanti attributi
il valore di ciascun attributo
appartiene ad un dominio specifico
Chiave
sottoinsiemi di attributi su cui
è definito un ordinamento totale
primaria se non ammette duplicati,
secondaria altrimenti