Sto usando il database dynamodb nosql di Amazon e di conseguenza ho bisogno di pensare ad alcuni modi per fare certe operazioni per adattarle ai loro limiti (es. limite di articoli 4k, non posso combinare piccoli articoli nella stessa operazione di lettura, ecc.) .
Uno di questi problemi avrò un attributo di database che conterrà una stringa lunga (la stringa avrà un aspetto simile a questo: [username1], [username2], [username200]). Da questa stringa dovrò essere in grado di cercare un utente, aggiungere un utente ed eliminare un utente. Se un utente viene aggiunto o eliminato, sarà necessario creare nuovamente una stringa in modo che possa essere caricata di nuovo nel database.
Scriverò questo in Java e quindi la mia idea è di analizzare la stringa in una struttura dati e quindi interagire con questa struttura dati per essere in grado di trovare e modificare gli utenti. La prima idea che mi è venuta in mente è quella di usare un arraylist e usare il metodo 'contains' della raccolta di Java per vedere se esiste un nome utente, ma funzionerà nel tempo O (n).
Stavo cercando di vedere se tenevo gli articoli ordinati (anche se da un punto di vista del fabbisogno non ho bisogno di ordinare gli utenti) se questo sarebbe d'aiuto, ma sembra che il contenuto sia sempre O (n).
Stavo guardando gli hash, ma l'overhead della CPU per calcolare gli hash credo sarà costoso perché questo scenario di manipolazione della stringa avverrà abbastanza spesso. Quale sarebbe una buona struttura dati da utilizzare per essere in grado di:
- Verifica se esiste un utente
- Aggiungi un utente alla struttura che deve quindi essere aggiunto alla stringa
- Elimina un utente dalla struttura che non deve quindi essere aggiunto alla stringa.
Farò più recuperi di inserimenti / aggiornamenti, quindi ho letto un file avl per essere un'opzione possibile, poiché la mia struttura dati è piccola (200 elementi) e la maggior parte delle operazioni funzionerà in O (log (n) ) C'è una struttura migliore o qualche pro / contro nell'usare alberi AV?