Discussion :

[smyley]

J'ai un problème, enfin, une sorte de problème. Je suis en train de refaire une des parties de ma "pseudo" base de données. La dernière fois que j'avais eu un problème avec c'était pour une histoire de BTree mais maintenant c'est encore un niveau en dessous : Mon fichier est découpé en blocs de 64 octets chacuns. Tous les 512 blocs forment une page et le moteur charge à chaque fois une page en mémoire. Toute cette partie fonctionne nikel (je me suis même débrouillé pour faire des caches et tout et tout). Le niveau juste au dessus c'est pouvoir organiser les blocs pour pouvoir "émuler" un flux de données (pouvant faire largement plus que 64 octets) et pour l'organisation j'ai du mal.

Ce que je faisait c'était une liste de blocs chainés (les 8 derniers octets indiquent le numéro du bloc suivant) et ainsi de suite. Cependant pour un flux de 24 Mo pour faire un seek à la position du byte commençant le 23e Mo je me retrouve à devoir lire tous le fichier pour pouvoir y arriver. Y'a t'il donc des documents ou des méthodes sur les méthodes les plus "pratiques" pour stocker l'adresse d'une série de blocs (sachant que cette liste elle aussi doit être contenue dans les blocs ...) ?

[pseudocode]

Pourquoi ne pas utiliser des blocs de pointeurs en plus de blocs de données (comme dans ext2 avec "inode" et "data") ?

[smyley]

Donc j'aurai un truc genre :

ptr vers un bloc de données
ptr vers un bloc de données
...
ptr vers un bloc de données
ptr vers le bloc suivant

Mais du coup, pour faire un seek il faut quand même que je lise de manière séquentielle chaque block d'index non ?

[pseudocode]

Les blocs d'index ne sont pas obligatoirement structurés en liste chainée : ils peuvent être stucturés sous forme d'arbre pour accélerer les seek (bien sur, au détriment de l'accès purment sequentiel qui necessite un parcours d'arbre)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
Index (00-2F)
-----
00-0F ---> Index (00-0F)
10-1F      -----     
20-2F      00-03 ---> Index (00-03)
next       04-07      -----
           08-0B      00 -----> data (00)
 |         0C-0F      01 -----> data (01)
 |                    02 -----> data (02)
 |                    03 -----> data (03)
\|/
 
Index (30-5F)
-----
30-3F
40-4F
50-5F
next

Regarde les specs sur ext2 pour plus détail.

[smyley]

Je vais essayer d'implémenter ça :

* Pour chaque morceau :
* ulong : ptr vers données ( 64 octets )
* ulong : ptr vers données ( 64 octets )
* ulong : ptr vers données ( 64 octets )
* ulong : ptr vers données ( 64 octets )
* ulong : ptr vers données ( 64 octets )
* ulong : ptr vers indirect index ( 512 octets )
* ulong : ptr vers double indirect index ( 4096 octets )
* ulong : ptr vers next
*
* indirect index :
* ulong : ptr vers données ( 64 octets ) x 8
*
* double indirect index :
* ulong : ptr vers indirect index ( 512 octets ) x 8

l'index utilise beaucoup d'espace mais à chaque déplacement dans la chaine je bouge de ~4,5 Ko (contre 64 octets avec une simple liste chainée ...). Sur le papier ça a l'air déjà cool, maintenant je vais en baver pour le faire ...

edit: tain, pour arriver à 25 Mo il me faudra quand même plus de 5000 blocs lus ...

[pseudocode]

edit: tain, pour arriver à 25 Mo il me faudra quand même plus de 5000 blocs lus ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
* Pour chaque morceau :
* ulong : ptr vers données ( 64 octets )
* ulong : ptr vers données ( 64 octets )
...

Pourquoi faire des nodes de données de seulement 64 octets ? Pourquoi ne pas pointer vers une page entiere (512 blocs x 64 octets = 32ko) ?

Bien sur, tu auras des pages qui ne seront pas remplies totalement mais est-ce un problème de perdre quelques ko ?