Δυαδικό δέντρο στον δίσκο.

[babaliaris]

Καλησπέρα.

Στην σχολή που σπουδάζω, στο συγκεκριμένο εξάμηνο ασχολούμαστε με δομές δεδομένων.
Αν και επικεντρονόμαστε πως να τα κάνουμε στην κεντρική μνήμη εγώ θέλω να μάθω
να τα κάνω και στον δίσκο.

Λοιπόν χωρίς να έχω βοήθεια από κανέναν, προσπαθούσα να σκεφτώ πως να κάνω ένα δυαδικό δέντρο στον δίσκο.
Στην αρχή προσπαθούσα να το κάνω μόνο σε ένα αρχείο αν και τα κατάφερα, το μόνο που δεν μπορούσα να κάνω
ήταν η διαγραφή. Δεν μπορούσα να βρω τρόπο να διαγράψω bytes μέσα από ένα αρχείο χωρίς να ξανά δημιουργήσω από
την αρχή ολόκληρο το αρχείο, που βέβαια για πολλά δεδομένα αυτός ο τρόπος είναι πάρα πολύ αργός.

Τελικά σκέφτηκα το εξής:
Θα δημιουργώ ξεχωριστά αρχεία τα οποία θα είναι οι κόμβοι του δέντρου μου, όπως γίνεται και στην κεντρική μνήμη.
Το κάθε αρχείο θα αποθηκεύει έναν ακέραιο αριθμό 4 bytes που θα είναι το κλειδί αλλά και το δεδομένο μου ταυτόχρονα
και 2 συμβολοσειρές το πολύ 20 bytes η κάθε μία. Άρα κάθε αρχείο θα έχει μέγεθος το πολύ 4+20+20 = 44 bytes.
Η συμβολοσειρές θα περιέχουν ονόματα αρχείων με τα οποία θα γίνεται η σύνδεση με άλλα αρχεία με τον τρόπο του
δυαδικού δέντρου. Δηλαδή σε μια εισαγωγή, αν το κλειδί είναι μικρότερο από το κλειδί του συγκεκριμένου κόμβου
τότε πάω αριστερά (δηλαδή ανοίγω το αρχείο με το όνομα που υπάρχει στην πρώτη συμβολοσειρά) εάν είναι μεγαλύτερο
πάω δεξιά (δεύτερη συμβολοσειρά). Επομένως τώρα εάν θέλω να διαγράψω έναν κόμβο του δέντρου απλός διαγράφω το
αρχείο που περιέχει το κλειδί που θέλω να διαγράψω (κάνοντας την ίδια διαδικασία διαγραφής όπως και σε ένα δυαδικό δέντρο
στην κεντρική μνήμη).

Το ερώτημά μου είναι το εξής:
Η ταχύτητα του ανοίγματος ενός αρχείου από το λειτουργικό εξαρτάτε από το πλήθος των αρχείων που υπάρχουν σε έναν φάκελο; (θεωρούμε
ότι όλα τα αρχεία που θα δημιουργηθούν βρίσκονται στον ίδιο φάκελο). Διότι εάν αυτήν η υποψία μου είναι σωστή, τότε η μέθοδος που σκέφτηκα
δεν θα κάνει τίποτα, πάλι θα έχω μια δομή που θα είναι αργή.

Ευχαριστώ πολύ.

- - - Updated - - -

Βασικά είπα χαζομάρα. Εάν γινόταν αυτό τότε δεν θα χρειαζόταν καν να κάνω κάποια δομή δεδομένων. Απλός θα δημιουργούσα ένα αρχείο για κάθε δεδομένο και θα του έδινα για όνομα το κλειδί με το οποίο γίνεται η αναζήτηση των δεδομένων και έτσι κάθε φορά που κάνω αναζήτηση απλός
θα άνοιγα το αρχείο :p

[WAntilles]

Εγώ δεν κατάλαβα ακριβώς ποιό είναι το ερώτημα.


Αν και επικεντρονόμαστε πως να τα κάνουμε στην κεντρική μνήμη εγώ θέλω να μάθω
να τα κάνω και στον δίσκο.

Δεν έχει διαφορά.

Η ξύπνια προσέγγιση είναι να κάνεις όλη τη δουλειά στη μνήμη, και μετά με τη μία εγγραφή στο δίσκο.


Δεν μπορούσα να βρω τρόπο να διαγράψω bytes μέσα από ένα αρχείο χωρίς να ξανά δημιουργήσω από
την αρχή ολόκληρο το αρχείο, που βέβαια για πολλά δεδομένα αυτός ο τρόπος είναι πάρα πολύ αργός.

Βλ. παραπάνω.


Η ταχύτητα του ανοίγματος ενός αρχείου από το λειτουργικό εξαρτάτε από το πλήθος των αρχείων που υπάρχουν σε έναν φάκελο; (θεωρούμε
ότι όλα τα αρχεία που θα δημιουργηθούν βρίσκονται στον ίδιο φάκελο).

Εξαρτάται βασικά από το file system.

Επίσης για πολλά μικρά αρχεία, θα έχει χαοτική διαφορά στην ταχύτητα ένας SSD από έναν μηχανικό δίσκο.

[zardoz]

Φίλε μου έχεις μπεί σε χαοτικό κεφάλαιο, αλλά είναι καλό που την ψάχνεις, γιατί έτσι μαθαίνει κανείς,
μια και η γνώση που αποκτάς μόνος σου μένει για πάντα. Απλά googlαρεις ή ρωτάς (εδώ) για tips

Αν και απάντησες μόνος σου το ερώτημά σου, τα δυαδικά δέντρα, και τα Β+ Β* έχουν πολύ ψωμί για
διάβασμα, ειδικά όσον αφορά τον ισοσκελισμό (http://www.stoimen.com/blog/2012/07/03/computer-algorithms-balancing-a-binary-search-tree/) τους κλπ κλπ

Ξέρε πάντως ότι, όλες οι μοντέρνες δομές δεδομένων, είτε μορφής βάσης ή δέντρου ή οτιδήποτε, συνήθως δεν
σβήνουν ΠΟΤΕ τίποτε αλλά το μαρκάρουν σβησμένο και - αργότερα - το κάνουν garbage collect. Για να γίνω λίγο
πιό τεχνικός λειτουργούν με LOGS, δηλαδή αρχεία καταγραφών μεταβολών, όπου οι μεταβολές/διαγραφές απλά
καταγράφονται και αργότερα μονιμοποιούνται στη δομή (πχ στο δέντρο) όταν υπάρχει "ελεύθερος χρόνος". Κατά
την αναζήτηση, πρώτα αναζητείται στο LOG (με αντίστροφη χρονική σειρά) και αν πχ ο κόμβος βρεθεί "σβησμένος"
το μαθαίνεις αμέσως. Αν δεν βρεθεί entry στο LOG, ψάχνει στη δομή.

Όταν το σύστημα έχει ελέυθερο χρόνο (CPU ή DISK idle κλπ) μέρος του LOG τελικά περνά και μονιμοποιείται στη
δομή με ορθή χρονολογική σειρά, και γίνεται truncate μέχρι έκεί που πέρασε. Τα LOGS βοηθούν ακόμα και
στο concurrency όταν πολλοί χρήστες αρχίσουν να κάνουν αλλαγές και φυσικά στο transactional / rollback ζήτημα

Γενικά διάβασε - έχει πολύ ζουμί και ότι μάθει κανείς χρήσιμο είναι.

[babaliaris]

Για να τα κάνω απλά τα πράματα. Ας πούμε ότι έχω ένα αρχείο και θέλω να διαγράψω κάποια bytes από αυτό. Ο μόνος τρόπος που ξέρω είναι
να δημιουργήσω ένα δεύτερο αρχείο, να αντιγράψω σε αυτό όλα τα bytes από το πρώτο αρχείο εκτός από αυτά που θέλω να διαγραφούν
και στην συνέχεια να διαγράψω το πρώτο αρχείο.

Ας πούμε τώρα ότι έχω ένα αρχείο 10 τέρα, και θέλω να αφαιρέσω τα 4 τελευταία bytes τα οποία αναπαριστούν έναν ακέραιο αριθμό.
Θα δημιουργήσω ένα δεύτερο αρχείο στο οποίο θα αντιγράψω 10 τέρα - 4 bytes από το πρώτο, και μετά θα διαγράψω το πρώτο;

Αυτό θα πάρει χρόνια μέχρι να γίνει. Σίγουρα υπάρχει κάτι που δεν ξέρω.
Δεν ξέρω και πως ακριβός δουλεύουν τα αρχεία για αυτό δεν μπορώ να βγάλω άκρη.

- - - Updated - - -


Φίλε μου έχεις μπεί σε χαοτικό κεφάλαιο, αλλά είναι καλό που την ψάχνεις, γιατί έτσι μαθαίνει κανείς,
μια και η γνώση που αποκτάς μόνος σου μένει για πάντα. Απλά googlαρεις ή ρωτάς (εδώ) για tips

Αν και απάντησες μόνος σου το ερώτημά σου, τα δυαδικά δέντρα, και τα Β+ Β* έχουν πολύ ψωμί για
διάβασμα, ειδικά όσον αφορά τον ισοσκελισμό (http://www.stoimen.com/blog/2012/07/03/computer-algorithms-balancing-a-binary-search-tree/) τους κλπ κλπ

Ξέρε πάντως ότι, όλες οι μοντέρνες δομές δεδομένων, είτε μορφής βάσης ή δέντρου ή οτιδήποτε, συνήθως δεν
σβήνουν ΠΟΤΕ τίποτε αλλά το μαρκάρουν σβησμένο και - αργότερα - το κάνουν garbage collect. Για να γίνω λίγο
πιό τεχνικός λειτουργούν με LOGS, δηλαδή αρχεία καταγραφών μεταβολών, όπου οι μεταβολές/διαγραφές απλά
καταγράφονται και αργότερα μονιμοποιούνται στη δομή (πχ στο δέντρο) όταν υπάρχει "ελεύθερος χρόνος". Κατά
την αναζήτηση, πρώτα αναζητείται στο LOG (με αντίστροφη χρονική σειρά) και αν πχ ο κόμβος βρεθεί "σβησμένος"
το μαθαίνεις αμέσως. Αν δεν βρεθεί entry στο LOG, ψάχνει στη δομή.

Όταν το σύστημα έχει ελέυθερο χρόνο (CPU ή DISK idle κλπ) μέρος του LOG τελικά περνά και μονιμοποιείται στη
δομή με ορθή χρονολογική σειρά, και γίνεται truncate μέχρι έκεί που πέρασε. Τα LOGS βοηθούν ακόμα και
στο concurrency όταν πολλοί χρήστες αρχίσουν να κάνουν αλλαγές και φυσικά στο transactional / rollback ζήτημα

Γενικά διάβασε - έχει πολύ ζουμί και ότι μάθει κανείς χρήσιμο είναι.

Γνωρίζω b και b+ trees. Τα έχω δουλέψει όμως μόνο στην μνήμη.

- - - Updated - - -

Κατάλαβα τη εννοείς. Έχω κάνει δομές στον δίσκο, πχ τώρα έχουμε να κάνουμε τον δυναμικό κατακερματισμό (dynamic hashing) στον δίσκο.
Μπορώ να την φτιάξω την δομή στο δίσκο διατάσσοντας τα δεδομένα μου με σελίδες δίσκου. Ο καθηγητής μας είπε "Αποθηκεύστε τα δεδομένα στον
δίσκο σε σελίδες δίσκου 128 bytes και κρατήστε την δομή του hashing στην μνήμη". Δηλαδή η δομή θα βρίσκεται στην μνήμη και απλώς θα με λέει
ποια σελίδα από το αρχείο πρέπει να διαβάσω για να συλλέξω το δεδομένο μου. Επίσης στην διαγραφεί μας είπε απλός να μαρκάρουμε στην δομή
ότι αυτό έχει διαγραφεί, και να μην το διαγράφουμε.

Το θέμα είναι πως απελευθερώνεις χώρο από τον δίσκο εάν δεν διαγράψει κάτι;

[zardoz]

Ας πούμε τώρα ότι έχω ένα αρχείο 10 τέρα, και θέλω να αφαιρέσω τα 4 τελευταία bytes τα οποία αναπαριστούν έναν ακέραιο αριθμό.
Θα δημιουργήσω ένα δεύτερο αρχείο στο οποίο θα αντιγράψω 10 τέρα - 4 bytes από το πρώτο, και μετά θα διαγράψω το πρώτο;
Αυτό θα πάρει χρόνια μέχρι να γίνει. Σίγουρα υπάρχει κάτι που δεν ξέρω.


Είναι κρυμένη η απάντηση μέσα σε αυτό που σου έγραψα.
Αντί να σβήσεις τα 4 bytes σε ένα αρχείο 10 τέρα κάνεις ένα εκ των δύο:

1. Τα μαρκάρεις "σβησμένα" εκεί που βρίσκονται, χωρίς να αντιγράψεις το αρχείο καθόλου. Να ξέρεις ότι σε μεταβολές μέσα σε
αρχεία, όλα τα filesystems (χμ, σχεδόν) απλά γράφουν μόνο το sector/cluster που έχει υποστεί αλλαγή. Άρα το "σβήσιμο" 4 bytes
θα ισοδυναμίσει με "μαρκάρισμα" 4 bytes άρα γράψιμο ενός sector ή cluster (πχ 512bytes ώς 4Κ τίποτε δηλαδή).
To μαρκάρισμα μπορεί να γίνει και απλά με ένα bit, ή ένα code που δεν επιτρέπεται στο δέντρο (πχ 0000)

2. O "κυριλέ" τρόπος είναι ούτε καν να ασχοληθείς με τις διαγραφές αυτές, και να κάνεις LOG ή κάνε deletion LOG μόνο:
Eίναι ένα μικρό αρχείο που μαζεύει τί ΔΙΑΓΡΑΦΗΚΕ, δηλαδή εκεί γράφεις ότι "ΑΥΤΟ ΤΟ ΜΕΡΟΣ ΤΟΥ 10Τερα αρχείου διαγράφηκε"
Αν γίνουν και άλλες διαγραφές, απλά τις βάζεις εκεί, με timespamp στην ορθή χρονολογική σειρά.
Αν κάποιος ψάξει ΓΙΑ ΟΤΙΔΗΠΟΤΕ, πρώτα κοιτάς το LOG με αντιστροφη χρονολογική σειρά, μήπως σβήστικε αυτό που ψάχνει, και μετά στο 10Tερα αρχείο
Όταν το σύστημα είναι idle, παίρνεις το LOG και πας στο ΒΗΜΑ 1 μαρκάροντας στο πραγματικό αρχείο τις διαγραφές και
ξεφορτώνεσαι το LOG μια και το "υλοποίησες" (λέγεται truncate)

Και στις δυο περιπτώσεις, τίποτε δεν αντιγράφεται.
Αν θέλεις backup όμως ΠΕΡΝΕΙΣ ΚΑΙ ΤΗ ΔΟΜΗ ΚΑΙ ΤΟ LOG (αν δεν έγινε truncate)

[babaliaris]

Είναι κρυμένη η απάντηση μέσα σε αυτό που σου έγραψα.
Αντί να σβήσεις τα 4 bytes σε ένα αρχείο 10 τέρα κάνεις ένα εκ των δύο:

1. Τα μαρκάρεις "σβησμένα" εκεί που βρίσκονται, χωρίς να αντιγράψεις το αρχείο καθόλου. Να ξέρεις ότι σε μεταβολές μέσα σε
αρχεία, όλα τα filesystems (χμ, σχεδόν) απλά γράφουν μόνο το sector/cluster που έχει υποστεί αλλαγή. Άρα το "σβήσιμο" 4 bytes
θα ισοδυναμίσει με "μαρκάρισμα" 4 bytes άρα γράψιμο ενός sector ή cluster (πχ 512bytes ώς 4Κ τίποτε δηλαδή).
To μαρκάρισμα μπορεί να γίνει και απλά με ένα bit, ή ένα code που δεν επιτρέπεται στο δέντρο (πχ 0000)

2. O "κυριλέ" τρόπος είναι ούτε καν να ασχοληθείς με τις διαγραφές αυτές, και να κάνεις LOG ή κάνε deletion LOG μόνο:
Eίναι ένα μικρό αρχείο που μαζεύει τί ΔΙΑΓΡΑΦΗΚΕ, δηλαδή εκεί γράφεις ότι "ΑΥΤΟ ΤΟ ΜΕΡΟΣ ΤΟΥ 10Τερα αρχείου διαγράφηκε"
Αν γίνουν και άλλες διαγραφές, απλά τις βάζεις εκεί, με timespamp στην ορθή χρονολογική σειρά.
Αν κάποιος ψάξει ΓΙΑ ΟΤΙΔΗΠΟΤΕ, πρώτα κοιτάς το LOG με αντιστροφη χρονολογική σειρά, μήπως σβήστικε αυτό που ψάχνει, και μετά στο 10Tερα αρχείο
Όταν το σύστημα είναι idle, παίρνεις το LOG και πας στο ΒΗΜΑ 1 μαρκάροντας στο πραγματικό αρχείο τις διαγραφές και
ξεφορτώνεσαι το LOG μια και το "υλοποίησες" (λέγεται truncate)

Και στις δυο περιπτώσεις, τίποτε δεν αντιγράφεται.
Αν θέλεις backup όμως ΠΕΡΝΕΙΣ ΚΑΙ ΤΗ ΔΟΜΗ ΚΑΙ ΤΟ LOG (αν δεν έγινε truncate)

Δεν μπορώ να καταλάβω ακριβώς τη εννοείς :(
Αν πχ έχω ένα αρχείο το οποίο έχει 6 σελίδες τον 128 bytes δηλαδή συνολικά 6x128 = 768 bytes
και θέλω να μαρκάρω ως σβησμένη την 3 σελίδα, πως θα το κάνω προγραμματιστηκά;

file.seek(3 * 128) για να βρω την σελίδα μέσα στο αρχείο.
Μετά τη κάνω;
Δηλαδή που κάνω το μαρκάρισμα και πως το κάνω;

[zardoz]

Δεν μπορώ να καταλάβω ακριβώς τη εννοείς :(
Αν πχ έχω ένα αρχείο το οποίο έχει 6 σελίδες τον 128 bytes δηλαδή συνολικά 6x128 = 768 bytes
και θέλω να μαρκάρω ως σβησμένη την 3 σελίδα, πως θα το κάνω προγραμματιστηκά;

file.seek(3 * 128) για να βρω την σελίδα μέσα στο αρχείο.
Μετά τη κάνω;
Δηλαδή που κάνω το μαρκάρισμα και πως το κάνω;

Το παραπάνω το είχα γράψει ΠΡΙΝ κάνεις την ανάλυση του τί ακριβώς σου ζητήθηκε.

Ο καθηγητής σας είπε ήδη: τη διαγραφή θα τη μαρκάρετε στη ΔΟΜΗ που είναι στη μνήμη,
οπότε όταν ψάξεις πχ την σελίδα, η δομή στη μνήμη θα σου πεί ΤΣΑΜΠΑ την ψάχνεις έχει
διαγραφεί. Στο δίσκο όμως θα παραμείνει.. κάτι σαν το facebook που σβήνεις όλο το προφίλ
σου και όλα τα αρχεία παραμένουν στους servers της :)

Τώρα, αν από τις 6 σελίδες, διαγράψεις πχ 4 και θέλεις κάποια στιγμή να κάνεις reclaim
το χώρο στο αρχείο των 6x128, συνήθως δεν το κάνεις. Απλά τις αφήνεις εκεί περιμένοντας
το hash ή το b-tree να φέρει κάποια νέα σελίδα να πέσει πάνω στην υπάρχουσα διεγραμμένη.

edit: αν φυσικά σας τα πρήξει και θέλει και φυσικές διαγραφές (reclaim χώρου), πρέπει να
κάνεις copy τα ενεργά 128άρια της δομής, να κάνεις skip (με seek φυσικά) τα διεγραμμένα
κομμάτια και να αλλάξεις και το hash στη δομή στη μνήμη να κάνει reflect το νέο σου αρχείο.
Πίκρα δηλαδή, αλλά συνήθως γίνεται σε idle στιγμές

[babaliaris]

Απλά τις αφήνεις εκεί περιμένοντας
το hash ή το b-tree να φέρει κάποια νέα σελίδα να πέσει πάνω στην υπάρχουσα διεγραμμένη.


Αυτό ακούγεται καλό, αλλά γίνεται να ανοίξω ένα αρχείο και να πάνω-γράψω μια σελίδα δίσκου;
Από'τι γνωρίζω κάθε φορά που ανοίγεις ένα αρχείο για εγγραφεί αυτό δημιουργήτε πάλι από την αρχή.

[zardoz]

Αυτό ακούγεται καλό, αλλά γίνεται να ανοίξω ένα αρχείο και να πάνω-γράψω μια σελίδα δίσκου;
Από'τι γνωρίζω κάθε φορά που ανοίγεις ένα αρχείο για εγγραφεί αυτό δημιουργήτε πάλι από την αρχή.

OXI. Δεν ξέρω σε τι γλώσσα γράφεις, αλλά οι γλώσσες στηρίζονται από τις κλήσεις λειτουργικού.

Πχ στα windows, όταν ανοίγεις ένα υπάρχον αρχείο σε RW mode, κάνεις seek
σε ένα ΟΠΟΙΟΔΗΠΟΤΕ offset (πχ 100.000) και γράψεις ΕΝΑ ΒΥΤΕ αυτό που κάνει
είναι ΑΚΡΙΒΩΣ το εξής:


Βρίσκει σε ποιό cluster βρίσκεται το offset 100.000 διαιρώντας με το disk clustersize,
πχ σε NTFS συνήθως 4096 οπότε ξέρει ότι το offset 100.000 είναι στο cluster 24
Φορτώνει όλο το cluster (και τα 4096 bytes)
Πάει στο offset 1696 γιατί ξέρει (100.000 - 24*4096) ότι εκεί είναι το ΕΝΑ byte που θέλεις
Το αλλάζει
Αν και μόνο αν κλείσεις το αρχείο, γράφει όλο το cluster πίσω εκεί που ήταν


Δηλαδή για να αλλάξεις ένα byte, διαβάζει και γράφει 4096 (στο παράδειγμα) αλλά πολύ
λιγότερα από ότι νόμιζες. Υπάρχουν και άλλα που απέκρυψα (βελτιστοποιήσεις, dirty/non dirty
sectors κλπ κλπ) αλλά δεν είναι επί του παρόντος

[babaliaris]

170264

Εγώ περίμενα το αποτέλεσμα "kalio nwris para pote" αλλά όπως βλέπεις πήρα
το αποτέλεσμα " nwris".

Συνήθως χρησιμοποιώ java, αλλά τώρα το έκανα σε python για γρήγορα.
Επίσης δοκίμασα να γράψω και ένα byte (το nwris είναι 5 :p ) αλλά και πάλι με κάνει τα ίδια.

[zardoz]

170264

Εγώ περίμενα το αποτέλεσμα "kalio nwris para pote" αλλά όπως βλέπεις πήρα
το αποτέλεσμα " nwris".

Συνήθως χρησιμοποιώ java, αλλά τώρα το έκανα σε python για γρήγορα.

rw <- όχι w

[babaliaris]

rw <- όχι w

Δούλεψε!!!!!!

Ωραία, τώρα κατάλαβα τα πάντα!!
Πραγματικά σε ευχαριστώ πάρα πολύ, σήμερα με έκανες πραγματικά μάθημα και με έμαθες τρομερά πράγματα
που δεν γνώριζα!

Αυτά αρκούν για τώρα. Στο μέλλον θα μάθω περισσότερα.