Structure de la base de données & amp; Disque dur chercher la confusion du temps

Question

Quelqu'un pourrait-il m'aider à essayer de comprendre comment fonctionne la recherche d'un disque dur?

J'ai un petit fichier de base de données binaire dont les performances en lecture sont absolument essentielles. Si j'ai besoin de sauter quelques octets dans le fichier, est-il plus rapide d'utiliser seek () ou read (), puis d'éliminer les données indésirables?

Si le temps de recherche moyen d'un disque dur est de 10 ms et que la vitesse de lecture est de 300 Mo / s, j'ai calculé qu'il était plus rapide de lire () que de chercher () avec une valeur inférieure à 3 Mo. Est vrai? Existe-t-il une surcharge lors d’une nouvelle recherche que la lecture d’un flux existant n’a pas?

Selon vous, quelle structure de fichier convient le mieux à un index?

Entry1:Value:PointerIntoToData
Entry2:Value:PointerIntoToData
Entry3:Value:PointerIntoToData
Data, Data, Data

Or

Entry1:Value:Data
Entry2:Value:Data
Entry3:Value:Data

Lors de la lecture d'une entrée, si la valeur n'est pas correcte, elle sera ignorée. Ainsi, lors de la diffusion du fichier, est-il plus rapide de: 1. quand une entrée n'est pas nécessaire, utilisez seek () pour la sauter 2. lorsqu'une entrée n'est pas nécessaire, lisez-la puis supprimez les données 3. ou la structure use first, lorsqu'une entrée est requise, search () à la fin d'un référentiel de données.

L'entrée est de 4 octets, la valeur de 8 octets & amp; les données sont de 12 Ko

A bientôt

Answer 1

Tout l'appel système chercher ne modifie une position dans le fichier à la prochaine lecture. Cela ne déplace pas la tête d'entraînement. Les têtes de lecteurs bougent lorsque les données sont lues ou écrites et que vous n’avez pas le contrôle direct de ce que le système d’exploitation fera ensuite.

La lecture d'un grand nombre de données dont vous n'aurez pas besoin aura un impact, car toutes les données lues ont besoin d'espace dans les tampons du système d'exploitation et entraînent l'élimination des données plus anciennes. Par conséquent, l’utilisation de la recherche sur les gros fichiers perturbera moins le cache du système de fichiers.

Tout ce que j'écris ci-dessous suppose que vous ne pouvez pas stocker toute la base de données en mémoire. Si vous le pouvez, faites-le. Lisez tout et essayez d’ajouter les nouvelles données et les données modifiées à la fin du fichier. Ne vous inquiétez pas de la perte d’espace, faites juste un peu de compactage de temps en temps.

Si votre base de données est trop grande:

Les données sont lues et écrites sur le lecteur physique par blocs (ou pages). De la même manière, l'unité de base de l'IO de disque dans votre système d'exploitation est la page. Si le système d'exploitation met en cache les données du disque, elles se trouvent également dans des pages entières. Il est donc peu logique de penser que vous ayez besoin d'avancer de quelques octets en utilisant search ou read. Si vous souhaitez accélérer le processus, vous devez prendre en compte le fonctionnement réel des E / S de disque.

Tout d’abord, déjà mentionné par nobugz, localité de référence. Si les données que vous utilisez dans chaque opération sont proches les unes des autres dans un fichier, votre système d'exploitation devra lire ou écrire moins de pages. Par contre, si vous répartissez vos données, de nombreuses pages devront être lues ou écrites en même temps, ce qui sera toujours lent.

En ce qui concerne la structure de données pour l'index. Généralement, ils sont organisés en arbres B . C'est une structure de données spécialement conçue pour la recherche efficace de grandes quantités de données stockées en mémoire avec des lectures et écritures paginées.

Et les deux stratégies d’organisation des données sont utilisées dans la pratique. Par exemple, MS SQL Server stocke les données par défaut de la première manière: les données sont stockées séparément et les index ne contiennent que les données des colonnes indexées et les adresses physiques des lignes de données dans les fichiers. Mais si vous définissez un index clusterisé, toutes les données seront stockées dans cet index. Tous les autres index pointeront sur les données via une clé d'index clusterisé au lieu d'une adresse physique. La première méthode est plus simple, mais l’autre peut s'avérer beaucoup plus efficace si vous analysez souvent des plages de données en fonction d’un index clusterisé.

Answer 2

Comment " absolument essentiel " est chercher l'accès? Avez-vous déjà testé votre application avec une solution non optimale? Au cours de ces tests, avez-vous effectué une analyse comparative pour déterminer où se trouvaient les goulets d'étranglement réels ? Sinon, vous serez surpris des résultats.

Ensuite, essayez différentes méthodes et comparez les temps d'exécution. Testez sous différentes charges du système (c'est-à-dire lorsque le système est inactif, à l'exception de votre application, et lorsqu'il est occupé).

Considérez que vos optimisations basées sur votre disque dur actuel peuvent devenir incorrectes lorsqu'un nouveau disque dur plus rapide comporte différentes optimisations internes qui jettent votre travail par la fenêtre.

Answer 3

Une lecture séquentielle est toujours plus rapide qu'une lecture nécessitant une recherche de tête (pas de recherche de position). La performance typique du disque dur pour la lecture séquentielle est de 50 à 60 Mo / s, ce qui en fait une baisse allant jusqu'à 0,4 Mo / s dans le pire des cas. Une fois les têtes d'entraînement positionnées, vous obtenez essentiellement les données dans le cylindre gratuitement. Le cache du système de fichiers tire parti de cela en lisant au préalable les secteurs d’un cylindre.

Cependant, vous n’avez aucun contrôle sur l’emplacement de vos données sur les cylindres de disque. Vous ne pouvez pas non plus deviner la géométrie du disque. Notez que le débit peut s’aggraver considérablement avec le temps lorsque le volume est fragmenté. Vous aurez besoin de chercher perf en mettant en cache des données en mémoire. À ce stade, vous vous inquiétez de la localité de référence.

Answer 4

Vous pouvez toujours mapper le fichier en mémoire, puis y accéder par le biais de pointeurs, etc. Cela devrait généralement simplifier vos accès et .