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 ?

[smyley]

Bah en fait dans mon système il y a un très grand nombre (la majorité) de flux qui ne font que quelques octets :
- nom de la node : ~10 octets
- taille totale du flux de données : un long
- quelques attributs.
Donc il me fallait de petits blocs pour éviter de trop perdre vu que cela constitue la majorité de mes données. Simplement il arrive que des fois j'ai beaucoup plus à stocker (genre un blob de 20 - 60 Mo, surtout dans le cadre des installations DreamShield) et c'est là mon problème.
Mais du coup, mes allocations se font par bloc et pas par page, (mon gestionnaire de bitmap me retourne par exemple le premier bloc libre ... quoiqu'il est capable de retourner le premier bloc libre dans une page ..) et donc on peut très bien avec un premier bloc dans la page 1, le deuxième dans la 3, le troisième dans la 1, le quatrième dans la 6 (même si j'essaye d'éviter ça...).
Donc voilà ... comment je m'en sort ?

[smyley]

Ah au fait je précise, mon système fonctionne en lecture/écriture comme système de fichiers, c'est pour ça que je ne peut pas m'assurer d'avoir une chaine formée de blocs contiguës ...

[wiztricks]

Si le SGDB est performant pour de petits enregistrements, pourquoi ne pas poser les gros fichiers "à côté" sur le file system avec un enregistrement d'indirection pour récupérer le nom du fichier dans la base?
- W

[smyley]

Parce que tout doit tenir dans un seul fichier. Il n'est pas fait pour faire une base de données au sens des gros providers (qui créent pleins de fichiers, des logs, des backups, etc..) mais quelque chose qui se rapproche des Compoud Files (Fichiers word, msi, etc...) où absolument tout tiens dans un seul et unique fichier (qui peut d'ailleurs être un stream) ... c'est pour moi obligatoire.

[SpiceGuid]

Dans ton cas une liste c'est trop naïf.

Solution par dichotomie:
liste → arbre binaire de recherche.

Chaque noeud-bloc possède:

• un sous-bloc gauche (left)
• un sous-bloc-droit (right)
• la clé (ou pivot) est le cardinal du noeud visité

Du coup le i-th bloc de l'arbre devient accessible en O(ln(n)) au lieu de O(n).

Pseudo code:
soit i la clé de recherche (l'indice du bloc recherché)

• si i=1 alors le bloc visité est le bloc recherché
• si i <= left.key alors rechercher i dans le sous-arbre left
• si i > left.key+1 alors rechercher la clé i-left.key-1 dans le sous-arbre right

edit: si je ne suis pas assez clair (c'est le cas paraît-il) alors n'importe quel tutoriel d'Algo/TAD devrait (a le devoir de) vous l'expliquer mieux que moi, et comme il y en a tout plein sur DVP je ne me fais pas particulièrement de soucis pour vous, bref

[wiztricks]

Il me semble assez lourd de segmenter les Mo dans des petits blocs de 64 bytes.
N'est il pas possible d'envisager de poser l'ensemble en contigu et de marquer d'une facon ou d'une autre l'usage de cet espace?
- W

[SpiceGuid]

@wiztricks

Tu peux "segmenter" une liste comme tu l'entends ça restera toujours une liste avec une performance déplorable en recherche du n-ième élément.

[smyley]

Solution par dichotomie:
liste → arbre binaire de recherche
...

Arbre binaire je crois que je gère maintenant (ça fait un bout de temps que je l'utilise pour faire la correspondance entre nom de la clef -> bloc qui la contient).

Par contre, pour un flux, comment j'obtiens le pivot ? les blocs je vais toujours les ajouter dans l'ordre et il seront donc tous à droite dans l'arbre ...

[wiztricks]

@wiztricks

Tu peux "segmenter" une liste comme tu l'entends ça restera toujours une liste avec une performance déplorable en recherche du n-ième élément.

Je ne dis pas le contraire...
Sinon que c'est lourd de traiter un fichier de xMo en segments de 64 bytes qui ne seront à priori même pas "bien" rangés.
Ce que je proposais était d'insérer le BLOB tel que.
- W

[SpiceGuid]

Excuse-moi, j'ai parlé de la recherche sans parler de l'insertion

Non seulement tu ne veux pas une liste (un arbre dégénéré) mais bien sûr tu veux un arbre équilibré.

Voilà comment tu procèdes à l'insertion:

• l'indice du bloc est converti en notation binaire
• tu lis les bits de lsb vers msb (donc de droite à gauche)
• pour chaque bit à 0 tu insères dans la branche gauche et pour chaque bit à 1 tu insères dans la branche droite

[smyley]

Là j'ai pas compris. Peut tu détailler s'il te plait ?

[SpiceGuid]

Tu comptes en binaire à partir de 1.
Tu inséres l'élément de clé 1, puis l'élément de clé 10, puis les clés 11, 100, 101, ...

Tu considères le nombre binaire comme une liste de bits que tu lis de droite à gauche.
C'est-à-dire tu retires le 1 frontal et tu mirroites la liste de bits restante, ça te donne le cheminement à suivre à partir de la racine:

• 1 est une liste vide []
• 10 est la liste [0] donc le chemin [gauche]
• 11 est la liste [1] donc le chemin [droite]
• 100 est la liste [0;0] donc le chemin [gauche;gauche]
• 101 est la liste [1;0] donc le chemin [droite;gauche]
• 110 est la liste [0;1] donc le chemin [gauche;droite]
• 111 est la liste [1;1] donc le chemin [droite;droite]

Le chemin c'est le parcours dans l'arbre binaire pour insérer ou rechercher une clé.
Pour 7 élements ça te donne l'arbre binaire parfait suivant:

Code :

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

1
2
3
4
5
6
 
         1
      /    \
    10      11   
   /  \    /  \  
 100  110 101 111

Comme tu auras toujours un arbre parfait ou pseudo-parfait tu n'auras jamais de dégradation de performance.

Remarque:

• maintenant que tu sais comment cheminer dans l'arbre pour une clé donnée tu n'as plus rien à apprendre
• tu peux oublier tout ce que j'ai dis sur les pivots car c'est redondant avec cette méthode

[smyley]

Wow, je commence à voir la puissance de la méthode
Je vais essayer d'implémenter celà (ça a l'air beaucoup plus efficace que les listes et autres) et je vous tiendrai au courant.

[smyley]

Tu comptes en binaire à partir de 1.

Je peut compter à partir de 0 ou il y a une raison au 1 ? (je dit ça parce que le point de départ d'un flux c'est la position 0 et pas la 1 ... ça m'éviterai de faire des magouilles ...)