Vale la pena provare a scrivere strutture di dati infallibili?

Question

Il problema

Dobbiamo archiviare i dati in modo simile a una tabella, ma abbiamo vincoli di spazio molto rigorosi (~ 1 MB per tabella di 10K+ righe). Archiviamo dati come questo:

ID | reviews | factor | score | interval | etc.
---+---------+--------+-------+----------+-----
 1 |     244 |    2.4 |    10 |     4268 | ...

In un semplice formato binario (un array unidimensionale di byte, in cui l'indice di ogni riga può essere calcolato semplicemente conoscendo la lunghezza di ogni riga, che è fissata).

Esiste solo una funzione che legge mai questi dati (ottiene una riga per il suo indice) e solo una funzione che aggiunge una nuova riga (fino alla fine). La rimozione degli elementi dalla tabella non sarà mai richiesta (la tabella è solo appendici). Entrambe le funzioni sono coperte con una discreta quantità di test unitari.

Il problema è il seguente: dobbiamo essere in grado di passare rapidamente le righe ordinato da diverse colonne. In altre parole, abbiamo bisogno che i dati vengano ordinati con almeno due colonne.

Una soluzione semplice

Per risolvere questo problema, implementeremmo indici che, ancora una volta, sarebbero blocchi di dati binari. Ora lo farei intuitivamente creando strutture di dati ordinate che elencano solo l'indice della riga nella tabella originale:

factor_index        score_index
------------        -----------
          6                  2
          2                  1
          3                  6
          1                  4
          .                  .

La funzione che aggiunge una nuova riga alla tabella dovrebbe essere aggiornata per far aggiornare anche gli indici.

ESEMPIO: Per ottenere il primo elemento ordinato per punteggio, cerchiamo solo il primo valore nella tabella di indice per il punteggio (2) e otteniamo la riga corrispondente dalla tabella originale (la terza riga se concordiamo che la tabella è indicizzata zero).

Tuttavia, mi è stato suggerito di adottare un approccio diverso.

Una versione più complessa ma presumibilmente più sicura

Invece di memorizzare solo gli indici, duplichiamo i campi ID in ciascuna tabella di indice:

factor_index | ID        score_index | ID
-------------+---        ------------+---
          6  | 46                  2 |  8
          2  |  8                  1 | 14
          3  | 91                  6 | 46
          1  | 14                  4 | 60
          .  |  .                  . |  .

Quindi mantenere la tabella originale ordinata per ID e utilizzare gli indici solo come posizione di partenza per una ricerca binaria nella tabella originale.

La funzione che aggiunge un nuovo record dovrà ora fare una ricerca binaria per ID per trovare dove inserire la nuova riga, e causare l'aggiornamento degli indici.

ESEMPIO: Per ottenere il primo elemento ordinato per punteggio, cerchiamo la prima riga nella tabella di indice per il punteggio (2, 8) e utilizziamo l'indice (2) come posizione di partenza per una ricerca binaria nella tabella. Se i dati sono validi, non abbiamo nemmeno bisogno di fare una ricerca binaria, perché in posizione 2 troveremo la riga con ID 8. Se, tuttavia, scopriamo che il record in posizione 2 ha un indice diverso, continuiamo Con una ricerca binaria per trovare quella giusta e registrare l'errore.

L'argomento per questo approccio è che funzionerà anche se l'indice punta alla riga sbagliata nella tabella.

Trovo difficile credere che questo approccio sia davvero migliore, per i seguenti motivi:

• Richiede una ricerca binaria, che può essere una nuova fonte di bug.
• Richiede che la tabella sia mantenuta in ordine, il che implica un inserto più complesso (al contrario di una semplice append).
• Non si protegge dalla tabella principale fuori servizio: se ciò accade, l'indice potrebbe persino non trovare il record tramite la ricerca binaria.
• Richiede un codice di scrittura (e test) che non è mai nemmeno destinato a essere eseguito.
• Utilizza più dati di quanto necessario.

La domanda

È una priorità molto alta per la nostra applicazione che i dati di cui sopra siano sempre validi. Ma ciò giustifica la scrittura di strutture di dati più complesse e meccanismi di ricerca per proteggersi da casi di bordo che possono o meno accadere? Il tempo e lo sforzo non dovrebbero invece essere dedicati a scrivere casi di test più robusti per una versione più semplice?