Vaut-il la peine d'essayer d'écrire des structures de données infaillibles?

Question

Le problème

Nous devons stocker des données d'une manière en forme de table, mais nous avons des contraintes d'espace très strictes (~ 1 Mo par table de lignes 10k +). Nous stockons des données comme ceci:

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

Dans un format binaire simple (un tableau unidimensionnel d'octets, où l'indice de chaque ligne peut être calculé simplement en connaissant la longueur de chaque ligne, qui est fixe).

Il n'y a qu'une seule fonction qui lit ces données (obtient une ligne par son index), et une seule fonction qui ajoute une nouvelle ligne (jusqu'à la fin). La suppression des éléments de la table ne sera jamais nécessaire (le tableau est uniquement annexe). Les deux fonctions sont couvertes d'une quantité décente de tests unitaires.

Le problème est les suivants: nous devons être en mesure de passer rapidement par les lignes ordonné par différentes colonnes. En d'autres termes, nous avons besoin que les données soient triées d'au moins deux colonnes.

Une solution simple

Pour résoudre ce problème, nous implémenterions des index qui, encore une fois, seraient des morceaux de données binaires. Maintenant, je le ferais intuitivement en créant des structures de données ordonnées qui ne répertorient que l'index de la ligne dans le tableau d'origine:

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

La fonction qui ajoute une nouvelle ligne à la table devrait être mise à jour pour provoquer également la mise à jour des index.

EXEMPLE: Pour obtenir le premier élément commandé par score, nous recherchons simplement la première valeur du tableau d'index pour le score (2) et obtenons la ligne correspondante de la table d'origine (la troisième ligne si nous convenons que le tableau est indexé zéro).

Cependant, j'ai été suggéré de adopter une approche différente.

Une version plus complexe mais probablement plus sûre

Au lieu de stocker uniquement les index, nous reproduisons les champs d'ID dans chaque tableau d'index:

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

Gardez ensuite la table d'origine triée par ID et utilisez les index uniquement comme position de départ pour une recherche binaire dans la table d'origine.

La fonction qui ajoute un nouvel enregistrement devra désormais faire une recherche binaire par ID pour trouver où insérer la nouvelle ligne, et entraîner la mise à jour des index.

EXEMPLE: Pour obtenir le premier élément commandé par score, nous recherchons la première ligne de la table d'index pour le score (2, 8), et utilisons l'index (2) comme position de départ pour une recherche binaire dans le tableau. Si les données sont valides, nous n'avons même pas besoin de faire une recherche binaire, car à la position 2, nous trouverons la ligne avec ID 8. Si, cependant, nous constatons que l'enregistrement en position 2 a un index différent, nous continuons avec une recherche binaire pour trouver la bonne et enregistrer l'erreur.

L'argument pour cette approche est qu'il fonctionnera même si l'index pointe vers la mauvaise ligne du tableau.

J'ai du mal à croire que cette approche soit vraiment meilleure, pour les raisons suivantes:

• Il nécessite une recherche binaire, qui peut être une nouvelle source de bugs.
• Il faut conserver le tableau dans l'ordre, ce qui implique un insert plus complexe (par opposition à une simple appen).
• Il ne se prémène pas contre le tableau principal étant en panne: si cela se produit, l'index pourrait même ne pas trouver l'enregistrement via la recherche binaire.
• Il nécessite un code d'écriture (et de test) qui n'est même jamais censé être exécuté.
• Il utilise plus de données que ce qui est nécessaire.

La question

Il est très élevé pour notre application que les données ci-dessus sont toujours valides. Mais cela justifie-t-il l'écriture de structures de données et de mécanismes de recherche plus complexes pour se prémunir contre les cas de bord qui peuvent ou non se produire? Le temps et les efforts ne devraient-ils pas être mis en écriture sur des cas de test plus robustes pour une version plus simple?