kostaskol / external-merge-sort Goto Github PK

Εργασία 2 - Υλοποίηση Συστημάτων Βάσεων Δεδομένων
Α.Μ.: 1115201200066
Ονοματεπώνυμο: Κωνσταντίνος Κολυβάς

Υλοποίηση:
  1. Το κάθε block του αρχικού αρχείου, ταξινομείται με τον αλγόριθμο
     merge sort.

  2. Στο πρώτο block των heap files, διατηρούνται οι παρακάτω πληροφορίες:
    α. Αν είναι heap file
    β. Αν το heap file είναι ταξινομημένο
    γ. Αν είναι ταξινομημένο, κατά ποιο field number έχει ταξινομηθεί.

    Κατά την αναζήτηση αλλά και τον έλεγχο ταξινόμησης, γίνονται οι απαραίτητοι
    έλεγχοι ώστε το/τα αποτέλεσμα/τα να είναι σωστά

  3. Κατά την αναζήτηση, χρησιμοποιείται ο αλγόριθμος της δυαδικής αναζήτησης
     για τον έλεγχο των blocks (της πρώτης εγγραφής του κάθε block) και σειριακή
     αναζήτηση εντός του κάθε block (βλ. source/sorted.cpp:503)

  4. Κατά την ταξινόμηση, δημιουργούνται temporary αρχεία, τα οποία
     αποθηκεύονται στον φάκελο tmp_files. Μετά το κάθε run, τα αρχεία εισόδου
     διαγράφονται (έχουμε ήδη διατηρήσει τις εγγραφές στα αρχεία εξόδου).
     Στο τέλος της ταξινόμησης, διαγράφεται και ο φάκελος tmp_files.

  5. Οι απαραίτητοι φάκελοι (io_files - tmp_files) δημιουργούνται κατά την
     εκτέλεση του προγράμματος και δεν είναι απαραίτητη η δημιουργία τους
     manually

Γνωστά λάθη (για την διόρθωση των οποίων δεν υπήρχε χρόνος):
  1. Ενίοτε, αν η τιμή του πεδίου κατά το οποίο ψάχνουμε δεν υπάρχει,
     προκαλείται assertion error στην source/record.cpp:100
     και το πρόγραμμα κλείνει.

  2. Σε κάποιες εγγραφές αποκόπτονται οι τελευταίοι χαρακτήρες της πόλης.

Παρατηρήσεις:
  1. Για ακριβή περιγραφή για το πως λειτουργεί ο κώδικας, παρακαλώ διαβάστε
     τα comments πριν από και μέσα στην κάθε συνάρτηση, όπου περιγράφεται
     αναλυτικά η λογική και διαδικασία της

  2. Η ανάγνωση αρχείων δεν γίνεται μέσω redirection ("<"), αλλά απλά περνώντας
     το όνομα του αρχείου ως console argument κατά την εκτέλεση

  3. Μετά την εκτέλεση του make, το binary αρχείο βρίσκεται στον φάκελο output
    (εντολή: output/external_sort datasets/1xxx.csv)

  4. Στον φάκελο io_files βρίσκονται τα αποτελέσματα 2 ενδεικτικών εκτελέσεων
     με input το 1000.csv και ταξινόμηση κατά:
     α. ID (starting_file_Sorted_0)
     β. Όνομα (starting_file_Sorted_1)