Mi chiedo come funzionano le query di intervallo e la soluzione standard è utilizzare gli alberi B +. Tuttavia, sono un fan dei tentativi come una struttura generale dei dati e vorrei sapere se essi (o varianti di essi) possono fare tutte le cose che gli alberi B + possono fare. Cioè, se possono supportare l'intervallo veloce / tra le query alla pari con gli alberi B +, e se ci sono altre limitazioni dei tentativi rispetto agli alberi B +.
Un B-Tree è una struttura ad albero bilanciata che assicura una ricerca in tempo logaritmico ed efficiente attraversamento ordinato. Ogni nodo ha più di due figli. Questo aiuta a ottenere prestazioni più elevate rispetto agli alberi binari, perché riduce il numero di accessi al disco e il loro layout di archiviazione può trarre vantaggio da bloccare i dispositivi .
Un trie d'altra parte è una struttura che si adatta alle corrispondenze esatte. La complessità è proporzionale alla dimensione della chiave . È possibile implementare un attraversamento ordinato, se si prende la precauzione di ordinare i figli di ciascun nodo. L'archiviazione di grandi tentativi è il punto debole. O si utilizzano elenchi di dimensioni variabili per i bambini (e quindi è costoso aggiungere un nuovo elemento, in particolare sui dischi) oppure si prealloca l'allocazione per ogni spazio del nodo per ogni possibile lettera dell'alfabeto. Quindi è il consumo esponenziale di storage (accettabile per ascii, ma una cattiva idea per unicode).
Potresti essere interessato a una ricerca relativamente recente su una struttura combinata chiamata b-trie , per quali algoritmi esistono per renderli più adatti all'archiviazione su disco.
Leggi altre domande sui tag data-structures query trees indexing trie