Che cosa è un array ordinato di ricerca del database?

Question

Sto cercando un database che supporta le seguenti funzionalità:

1) i Record del database sono come Python dizionari o Perl hash.Per esempio, un "acquisto" record potrebbe assomigliare a questo:

<purchase 5436> = { product: "BMX Bike", price: 99.50, city: "Springfield" }

2) I record sono memorizzati in un array di lunghezza variabile.Il database contiene un sacco di queste matrici.Per esempio, l'acquisto di una tabella potrebbe assomigliare a questo:

purchase array 1: [ <purchase 5436>, <purchase 54>, <purchase 112> ]
purchase array 2: [ <purchase 76>, <purchase 5984>, <purchase 1102>, <purchase 12> ]
...
purchase array 658: [ <purchase 10142>, <purchase 35>, <purchase 6458>, <purchase 23> ]

3) voglio essere in grado di fare due tipi di query sul database:

3a) Contare il numero di record che corrispondono a diversi criteri.Per esempio, quanti di acquisto è stato fatto con un valore di oltre 50?Conosco un sacco di database che supportano questa.

3b) Contare il numero di volte in cui vengono visualizzati i record in un certo ordine.Per esempio, quante matrici sono un acquisto superiore a 50 è stata fatta e quindi un acquisto in "Springfield" è stata fatta?Non so che tipo di database che è possibile utilizzare per fare questo.

edit:La risposta di Steve Haigh:Mi hanno detto che la velocità è importante, e questo database ha bisogno di supporto gigabyte di dati.Per esempio, ci potrebbe essere 1.000.000.000 di acquisto matrici, e voglio contare quanti di loro hanno un acquisto in "Springfield", seguito da un acquisto in "Patria" (nota che l'ordine è importante).Forse mi sbaglio, ma credo che un DB relazionale sarebbe troppo lento per questo scopo.

Answer 1

Sei sicuro che non si può fare questo con un DB relazionale utilizzando una tabella di collegamento o raccordo?

Si avrebbe una colonna di ordini, una colonna di prodotti e un tavolo da ordinare prodotti che ha una riga per ogni prodotto per ordine.

Credo che questo probabilmente esprime meglio di me poteva.

Answer 2

  

Per esempio, ci potrebbe essere   1.000.000.000 di array di acquisto, ed io   voler contare quanti di loro hanno un   acquistare in "Springfield" seguito da   un acquisto in "Città" (si noti che   ordine è importante). Forse sto sbagliando,   ma penso che un DB relazionale sarebbe   troppo lento per questo scopo.

Ciò che si descrive sono tipici magazzino , e per quanto ne so questi sono di solito implementato utilizzando relazionale DB, anche se quelli che sono ottimizzati per la comunicazione, piuttosto che per l'elaborazione delle transazioni concorrente. Tuttavia, non credo che la differenza di velocità sarà di estrema se si utilizza un RDBMS "regolare". Naturalmente, se avete abbastanza soldi, si potrebbe andare per uno speciale DBMS data warehouse.

L'influenza più importante sulla velocità sta andando l'essere 1) una tecnologia ottimizzata per quering grandi insiemi di dati basati su disco - questo è esattamente quello che tutti "reale" offerta DMBSs, e 2) i dati organizzati nel modo giusto.

  

3b) Contare il numero di volte record   apparire in un certo ordine. Per   esempio, quante matrici sono lì   sono stati un acquisto superiore a 50 è stata fatta e   poi un acquisto in "Springfield" era   fatto? Non so che tipo di   banca dati si può usare per fare questo.

Si potrebbe usare un DB relazionale con uno schema progettato per supportare questo tipo di interrogazione . Si sta andando ad avere per dare il vostro preconcetto di come i dati devono essere rappresentati.

Answer 3

Non avete davvero bisogno di un database relazionale come solo tasto->coppie di valori raggruppati in collezioni, si avrebbe bisogno di join tra le due tabelle (una per il record, uno per le collezioni) per scorrere i record nella raccolta e nel tuo caso non vale il costo.

Per i requisiti di prestazioni, di che cosa avete bisogno è quello di assicurarsi che l'intera struttura si inserisce in memoria e non richiedono l'accesso al disco.Potrebbe essere necessario più di un server a fare questo, e un master che invia le ricerche per gli altri server (supponendo che le dimensioni della struttura è più grande di una ragionevole quantità di memoria che un moderno server in grado di gestire, e che la velocità dei requisiti sono così grandi che non si può permettere disco di impaginazione.

Per il tipo di query che hai citato, l'opzione migliore è di avere un po ' di ridondanza dei dati.Su inserimenti, si dovrebbe tenere traccia di chi conta.La ridondanza dei dati tende a freak out persone solo leggendo il nome, ma a volte è necessario.Basta essere molto attenti con i vostri attuazione e di investire una buona quantità di unità di test qui.

Ci potrebbe essere, però, un qualche tipo di query, che non saranno mai in grado di fare, in tempo reale, in una manciata di millisecondi, e che sulla ricerca di acquisti con una condizione seguita da acquisti con un'altra condizione sembra che questo.O si trova un modo di mantenere un monitoraggio in tempo reale di questi numeri durante l'inserimento/cancellazione/modifica, o si dovrà realtà scorrere milioni di matrici, c'è modo di evitare che.È necessario considerare come i recenti dati deve essere, e forse pre-calcolare ogni poche ore per generare le statistiche e quindi essere in grado di accedervi in O(1) con chiavi di ricerca.

In sintesi, il tuo problema è al di là della tecnologia si decide di utilizzare per risolvere il problema.

Answer 4

Non sono sicuro che capisco perfettamente quello che stai cercando, ma hai guardato CouchDB ? . Il suo documento orientato e lo schema gratuito

Answer 5

Quello che si sta descrivendo è abbastanza simile a MUMPS anche se ho qualche dubbio circa la capacità di definire le query in cui l'ordine di "record" nelle matrici è possibile.

Date un'occhiata al link, ci sono anche attuali versioni commerciali di questo, come si vedrà.