Γεια σου Χαμπρ! Σας παρουσιάζω τη μετάφραση του άρθρου
"Πώς λειτουργεί μια σχεσιακή βάση δεδομένων".

Όταν πρόκειται για σχεσιακές βάσεις δεδομένων, δεν μπορώ παρά να σκεφτώ ότι κάτι λείπει. Χρησιμοποιούνται παντού. Υπάρχουν πολλές διαφορετικές βάσεις δεδομένων διαθέσιμες, από το μικρό και χρήσιμο SQLite μέχρι το ισχυρό Teradata. Αλλά υπάρχουν μόνο λίγα άρθρα που εξηγούν πώς λειτουργεί η βάση δεδομένων. Μπορείτε να αναζητήσετε τον εαυτό σας χρησιμοποιώντας το "howdoesarelationaldatabasework" για να δείτε πόσο λίγα είναι τα αποτελέσματα. Επιπλέον, αυτά τα άρθρα είναι σύντομα. Αν ψάχνετε για τις πιο πρόσφατες buzzy τεχνολογίες (BigData, NoSQL ή JavaScript), θα βρείτε πιο αναλυτικά άρθρα που εξηγούν πώς λειτουργούν.

Είναι οι σχεσιακές βάσεις δεδομένων πολύ παλιές και πολύ βαρετές για να εξηγηθούν εκτός πανεπιστημιακών μαθημάτων, ερευνητικών εργασιών και βιβλίων;

Ως προγραμματιστής, μισώ να χρησιμοποιώ κάτι που δεν καταλαβαίνω. Και αν οι βάσεις δεδομένων χρησιμοποιούνται για περισσότερα από 40 χρόνια, πρέπει να υπάρχει λόγος. Με τα χρόνια, έχω ξοδέψει εκατοντάδες ώρες για να κατανοήσω πραγματικά αυτά τα περίεργα μαύρα κουτιά που χρησιμοποιώ καθημερινά. Σχεσιακές βάσεις δεδομένων πολύ ενδιαφέρον γιατί βασίζονται σε χρήσιμες και επαναχρησιμοποιήσιμες έννοιες. Εάν ενδιαφέρεστε να κατανοήσετε μια βάση δεδομένων, αλλά δεν είχατε ποτέ το χρόνο ή την τάση να εμβαθύνετε σε αυτό το ευρύ θέμα, θα πρέπει να απολαύσετε αυτό το άρθρο.

Αν και ο τίτλος αυτού του άρθρου είναι σαφής, Ο σκοπός αυτού του άρθρου δεν είναι να κατανοήσει πώς να χρησιμοποιήσετε τη βάση δεδομένων. Ως εκ τούτου, θα πρέπει να γνωρίζετε ήδη πώς να γράψετε ένα απλό αίτημα σύνδεσης και βασικά ερωτήματα ΘΕΡΜΟΣ; διαφορετικά μπορεί να μην καταλαβαίνετε αυτό το άρθρο. Αυτό είναι το μόνο που πρέπει να ξέρεις, θα σου εξηγήσω τα υπόλοιπα.

Θα ξεκινήσω με ορισμένα βασικά στοιχεία της επιστήμης των υπολογιστών, όπως η χρονική πολυπλοκότητα των αλγορίθμων (BigO). Ξέρω ότι ορισμένοι από εσάς μισείτε αυτήν την έννοια, αλλά χωρίς αυτήν δεν θα μπορείτε να κατανοήσετε τις περιπλοκές μέσα στη βάση δεδομένων. Επειδή αυτό είναι ένα τεράστιο θέμα, Θα επικεντρωθώ σε τι νομίζω ότι είναι σημαντικό: πώς επεξεργάζεται η βάση δεδομένων SQL запрос. Απλώς θα παρουσιάσω βασικές έννοιες της βάσης δεδομένωνέτσι ώστε στο τέλος του άρθρου να έχετε μια ιδέα για το τι συμβαίνει κάτω από την κουκούλα.

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

Για τους πιο ενημερωμένους από εσάς, αυτό το άρθρο χωρίζεται σε 3 μέρη:

• Επισκόπηση στοιχείων χαμηλού και υψηλού επιπέδου βάσης δεδομένων
• Επισκόπηση της διαδικασίας βελτιστοποίησης ερωτημάτων
• Επισκόπηση της διαχείρισης συναλλαγών και buffer Pool

Πίσω στα βασικά

Πριν από χρόνια (σε έναν γαλαξία πολύ, πολύ μακριά...), οι προγραμματιστές έπρεπε να γνωρίζουν ακριβώς τον αριθμό των λειτουργιών που κωδικοποιούσαν. Γνώριζαν τους αλγόριθμους και τις δομές δεδομένων τους από έξω γιατί δεν είχαν την πολυτέλεια να σπαταλήσουν τη CPU και τη μνήμη των αργών υπολογιστών τους.

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

O(1) έναντι O(n2)

Σήμερα, πολλοί προγραμματιστές δεν ενδιαφέρονται για τη χρονική πολυπλοκότητα των αλγορίθμων... και έχουν δίκιο!

Αλλά όταν έχετε να κάνετε με πολλά δεδομένα (δεν μιλάω για χιλιάδες) ή αν δυσκολεύεστε σε χιλιοστά του δευτερολέπτου, είναι κρίσιμο να κατανοήσετε αυτήν την έννοια. Και όπως μπορείτε να φανταστείτε, οι βάσεις δεδομένων πρέπει να αντιμετωπίσουν και τις δύο καταστάσεις! Δεν θα σας κάνω να αφιερώσετε περισσότερο χρόνο από όσο χρειάζεται για να καταλάβετε το θέμα. Αυτό θα μας βοηθήσει να κατανοήσουμε αργότερα την έννοια της βελτιστοποίησης βάσει κόστους (κόστος βασίζονται βελτιστοποίηση).

Έννοια

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

Για παράδειγμα, όταν λέω "αυτός ο αλγόριθμος έχει πολυπλοκότητα O(some_function())", σημαίνει ότι ο αλγόριθμος απαιτεί λειτουργίες some_function(a_certain_amount_of_data) για την επεξεργασία ενός συγκεκριμένου όγκου δεδομένων.

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

Σε αυτό το γράφημα μπορείτε να δείτε τον αριθμό των πράξεων σε σχέση με τον αριθμό των δεδομένων εισόδου για διαφορετικούς τύπους χρονικής πολυπλοκότητας αλγορίθμων. Χρησιμοποίησα μια λογαριθμική κλίμακα για να τα εμφανίσω. Με άλλα λόγια, ο όγκος των δεδομένων αυξάνεται γρήγορα από 1 σε 1 δισεκατομμύριο. Μπορούμε να δούμε ότι:

• Η O(1) ή σταθερή πολυπλοκότητα παραμένει σταθερή (αλλιώς δεν θα ονομαζόταν σταθερή πολυπλοκότητα).
• O(κούτσουρο(n)) παραμένει σε χαμηλά επίπεδα ακόμη και με δισεκατομμύρια δεδομένα.
• Η χειρότερη δυσκολία - O(n2), όπου ο αριθμός των λειτουργιών αυξάνεται γρήγορα.
• Οι άλλες δύο επιπλοκές αυξάνονται εξίσου γρήγορα.

παραδείγματα

Με έναν μικρό όγκο δεδομένων, η διαφορά μεταξύ O(1) και O(n2) είναι αμελητέα. Για παράδειγμα, ας υποθέσουμε ότι έχετε έναν αλγόριθμο που πρέπει να επεξεργαστεί 2000 στοιχεία.

• Ο αλγόριθμος O(1) θα σας κοστίσει 1 λειτουργία
• Ο αλγόριθμος O(log(n)) θα σας κοστίσει 7 πράξεις
• Ο αλγόριθμος O(n) θα σας κοστίσει 2 πράξεις
• Ο αλγόριθμος O(n*log(n)) θα σας κοστίσει 14 πράξεις
• Ο αλγόριθμος O(n2) θα σας κοστίσει 4 πράξεις

Η διαφορά μεταξύ O(1) και O(n2) φαίνεται μεγάλη (4 εκατομμύρια επεμβάσεις), αλλά θα χάσετε το πολύ 2 ms, μόλις πρέπει να ανοιγοκλείσετε τα μάτια σας. Πράγματι, οι σύγχρονοι επεξεργαστές μπορούν να επεξεργαστούν εκατοντάδες εκατομμύρια λειτουργίες ανά δευτερόλεπτο. Αυτός είναι ο λόγος για τον οποίο η απόδοση και η βελτιστοποίηση δεν αποτελούν πρόβλημα σε πολλά έργα πληροφορικής.

Όπως είπα, εξακολουθεί να είναι σημαντικό να γνωρίζουμε αυτήν την έννοια όταν εργάζεστε με τεράστιες ποσότητες δεδομένων. Εάν αυτή τη φορά ο αλγόριθμος πρέπει να επεξεργαστεί 1 στοιχεία (κάτι που δεν είναι τόσο μεγάλο για μια βάση δεδομένων):

• Ο αλγόριθμος O(1) θα σας κοστίσει 1 λειτουργία
• Ο αλγόριθμος O(log(n)) θα σας κοστίσει 14 πράξεις
• Ο αλγόριθμος O(n) θα σας κοστίσει 1 πράξεις
• Ο αλγόριθμος O(n*log(n)) θα σας κοστίσει 14 πράξεις
• Ο αλγόριθμος O(n2) θα σας κοστίσει 1 πράξεις

Δεν έχω κάνει τα μαθηματικά, αλλά θα έλεγα ότι με τον αλγόριθμο O(n2) έχεις χρόνο να πιεις έναν καφέ (έστω και δύο!). Εάν προσθέσετε άλλο 0 στον όγκο δεδομένων, θα έχετε χρόνο να πάρετε έναν υπνάκο.

Ας πάμε πιο βαθιά

Για την ενημέρωσή σας:

• Μια καλή αναζήτηση πίνακα κατακερματισμού βρίσκει ένα στοιχείο στο O(1).
• Η αναζήτηση ενός καλά ισορροπημένου δέντρου παράγει αποτελέσματα σε O(log(n)).
• Η αναζήτηση ενός πίνακα παράγει αποτελέσματα σε O(n).
• Οι καλύτεροι αλγόριθμοι ταξινόμησης έχουν πολυπλοκότητα O(n*log(n)).
• Ένας κακός αλγόριθμος ταξινόμησης έχει πολυπλοκότητα O(n2).

Σημείωση: Στα ακόλουθα μέρη θα δούμε αυτούς τους αλγόριθμους και τις δομές δεδομένων.

Υπάρχουν διάφοροι τύποι χρονικής πολυπλοκότητας αλγορίθμου:

• μέσο σενάριο περίπτωσης
• το καλύτερο σενάριο
• και το χειρότερο σενάριο

Η πολυπλοκότητα του χρόνου είναι συχνά το χειρότερο σενάριο.

Μίλησα μόνο για τη χρονική πολυπλοκότητα του αλγορίθμου, αλλά η πολυπλοκότητα ισχύει και για:

• κατανάλωση μνήμης του αλγορίθμου
• αλγόριθμος κατανάλωσης I/O δίσκου

Φυσικά, υπάρχουν επιπλοκές χειρότερες από το n2, για παράδειγμα:

• n4: αυτό είναι τρομερό! Μερικοί από τους αναφερόμενους αλγόριθμους έχουν αυτή την πολυπλοκότητα.
• 3n: αυτό είναι ακόμα χειρότερο! Ένας από τους αλγόριθμους που θα δούμε στη μέση αυτού του άρθρου έχει αυτή την πολυπλοκότητα (και στην πραγματικότητα χρησιμοποιείται σε πολλές βάσεις δεδομένων).
• παραγοντικό n: δεν θα λάβετε ποτέ τα αποτελέσματά σας ακόμη και με μικρό όγκο δεδομένων.
• nn: Εάν αντιμετωπίζετε αυτήν την πολυπλοκότητα, θα πρέπει να αναρωτηθείτε αν αυτό είναι πραγματικά το πεδίο δραστηριότητάς σας...

Σημείωση: Δεν σας έδωσα τον πραγματικό ορισμό του χαρακτηρισμού μεγάλου Ο, απλώς μια ιδέα. Μπορείτε να διαβάσετε αυτό το άρθρο στο Wikipedia για τον πραγματικό (ασυμπτωτικό) ορισμό.

MergeSort

Τι κάνετε όταν χρειάζεται να ταξινομήσετε μια συλλογή; Τι? Καλείτε τη συνάρτηση sort()... Εντάξει, καλή απάντηση... Αλλά για μια βάση δεδομένων, πρέπει να καταλάβετε πώς λειτουργεί αυτή η συνάρτηση sort().

Υπάρχουν αρκετοί καλοί αλγόριθμοι ταξινόμησης, οπότε θα εστιάσω στα πιο σημαντικά: συγχώνευση ταξινόμησης. Μπορεί να μην καταλαβαίνετε γιατί η ταξινόμηση δεδομένων είναι χρήσιμη αυτήν τη στιγμή, αλλά θα πρέπει να το κάνετε μετά το τμήμα βελτιστοποίησης ερωτήματος. Επιπλέον, η κατανόηση της ταξινόμησης συγχώνευσης θα μας βοηθήσει να κατανοήσουμε αργότερα την κοινή λειτουργία σύνδεσης βάσης δεδομένων που ονομάζεται συγχώνευση ενταχθούν (σύλλογος συγχωνεύσεων).

Συγχώνευση

Όπως πολλοί χρήσιμοι αλγόριθμοι, η συγχώνευση ταξινόμησης βασίζεται σε ένα τέχνασμα: ο συνδυασμός 2 ταξινομημένων πινάκων μεγέθους N/2 σε έναν πίνακα ταξινομημένο σε στοιχεία N κοστίζει μόνο N λειτουργίες. Αυτή η λειτουργία ονομάζεται συγχώνευση.

Ας δούμε τι σημαίνει αυτό με ένα απλό παράδειγμα:

Αυτό το σχήμα δείχνει ότι για να δημιουργήσετε τον τελικό ταξινομημένο πίνακα 8 στοιχείων, χρειάζεται μόνο να επαναλάβετε μία φορά πάνω από τους 2 πίνακες 4 στοιχείων. Δεδομένου ότι και οι δύο πίνακες 4 στοιχείων είναι ήδη ταξινομημένοι:

• 1) συγκρίνετε και τα δύο τρέχοντα στοιχεία σε δύο πίνακες (στην αρχή ρεύμα = πρώτο)
• 2) μετά πάρτε το μικρότερο για να το βάλετε σε έναν πίνακα 8 στοιχείων
• 3) και μετακινηθείτε στο επόμενο στοιχείο του πίνακα όπου πήρατε το μικρότερο στοιχείο
• και επαναλάβετε το 1,2,3 μέχρι να φτάσετε στο τελευταίο στοιχείο ενός από τους πίνακες.
• Στη συνέχεια, παίρνετε τα υπόλοιπα στοιχεία του άλλου πίνακα για να τα τοποθετήσετε σε έναν πίνακα 8 στοιχείων.

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

Τώρα που καταλάβαμε το κόλπο, εδώ είναι ο ψευδοκώδικάς μου για συγχώνευση:

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;

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

• Φάση διαίρεσης, όπου ο πίνακας χωρίζεται σε μικρότερους πίνακες
• Η φάση ταξινόμησης είναι όπου μικροί πίνακες συνδυάζονται (χρησιμοποιώντας ένωση) για να σχηματίσουν έναν μεγαλύτερο πίνακα.

Φάση διαίρεσης

Στο στάδιο της διαίρεσης, ο πίνακας χωρίζεται σε ενιαίους πίνακες σε 3 βήματα. Ο επίσημος αριθμός βημάτων είναι log(N) (αφού N=8, log(N) = 3).

Πώς το ξέρω αυτό;

Είμαι ιδιοφυΐα! Με μια λέξη - μαθηματικά. Η ιδέα είναι ότι κάθε βήμα διαιρεί το μέγεθος του αρχικού πίνακα με 2. Ο αριθμός των βημάτων είναι ο αριθμός των φορών που μπορείτε να διαιρέσετε τον αρχικό πίνακα σε δύο. Αυτός είναι ο ακριβής ορισμός του λογάριθμου (βάση 2).

Φάση ταξινόμησης

Στη φάση της ταξινόμησης, ξεκινάτε με ενιαίους (μονοστοιχειακούς) πίνακες. Κατά τη διάρκεια κάθε βήματος εφαρμόζετε πολλαπλές λειτουργίες συγχώνευσης και το συνολικό κόστος είναι N = 8 πράξεις:

• Στο πρώτο στάδιο έχετε 4 συγχωνεύσεις που κοστίζουν 2 πράξεις η καθεμία
• Στο δεύτερο βήμα έχετε 2 συγχωνεύσεις που κοστίζουν 4 πράξεις η καθεμία
• Στο τρίτο βήμα έχετε 1 συγχώνευση που κοστίζει 8 πράξεις

Εφόσον υπάρχουν βήματα log(N), συνολικό κόστος Ν * Λειτουργίες log(N)..

Πλεονεκτήματα της ταξινόμησης συγχώνευσης

Γιατί αυτός ο αλγόριθμος είναι τόσο ισχυρός;

Επειδή:

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

Σημείωση: αυτός ο τύπος αλγόριθμου ονομάζεται in-θέση (ταξινόμηση χωρίς πρόσθετη μνήμη).

• Μπορείτε να το αλλάξετε ώστε να χρησιμοποιεί ταυτόχρονα χώρο στο δίσκο και μικρή ποσότητα μνήμης χωρίς να επιβαρύνετε σημαντικά το δίσκο εισόδου/εξόδου. Η ιδέα είναι να φορτωθούν στη μνήμη μόνο εκείνα τα μέρη που επεξεργάζονται αυτήν τη στιγμή. Αυτό είναι σημαντικό όταν χρειάζεται να ταξινομήσετε έναν πίνακα πολλών gigabyte με προσωρινή μνήμη μόνο 100 megabyte.

Σημείωση: αυτός ο τύπος αλγόριθμου ονομάζεται εξωτερική ταξινόμηση.

• Μπορείτε να το αλλάξετε ώστε να εκτελείται σε πολλαπλές διεργασίες/νήματα/διακομιστές.

Για παράδειγμα, η κατανεμημένη ταξινόμηση συγχώνευσης είναι ένα από τα βασικά στοιχεία Hadoop (που είναι μια δομή στα μεγάλα δεδομένα).

• Αυτός ο αλγόριθμος μπορεί να μετατρέψει τον μόλυβδο σε χρυσό (πραγματικά!).

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

Πίνακας Array, Tree και Hash

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

Массив

Ένας δισδιάστατος πίνακας είναι η απλούστερη δομή δεδομένων. Ένας πίνακας μπορεί να θεωρηθεί ως πίνακας. Για παράδειγμα:

Αυτός ο δισδιάστατος πίνακας είναι ένας πίνακας με γραμμές και στήλες:

• Κάθε γραμμή αντιπροσωπεύει μια οντότητα
• Οι στήλες αποθηκεύουν ιδιότητες που περιγράφουν την οντότητα.
• Κάθε στήλη αποθηκεύει δεδομένα συγκεκριμένου τύπου (ακέραιος, συμβολοσειρά, ημερομηνία...).

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

Για παράδειγμα, αν θέλετε να βρείτε όλα τα παιδιά που εργάζονται στο Ηνωμένο Βασίλειο, θα πρέπει να κοιτάξετε κάθε σειρά για να προσδιορίσετε εάν αυτή η σειρά ανήκει στο Ηνωμένο Βασίλειο. Θα σας κοστίσει N συναλλαγέςΌπου N - αριθμός γραμμών, που δεν είναι κακό, αλλά θα μπορούσε να υπάρξει πιο γρήγορος τρόπος; Τώρα ήρθε η ώρα να γνωριστούμε με τα δέντρα.

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

Δέντρο και ευρετήριο βάσης δεδομένων

Ένα δυαδικό δέντρο αναζήτησης είναι ένα δυαδικό δέντρο με μια ειδική ιδιότητα, το κλειδί σε κάθε κόμβο πρέπει να είναι:

• μεγαλύτερο από όλα τα κλειδιά που είναι αποθηκευμένα στο αριστερό υποδέντρο
• λιγότερο από όλα τα κλειδιά που είναι αποθηκευμένα στο δεξί υποδέντρο

Ας δούμε τι σημαίνει αυτό οπτικά

Ιδέα

Αυτό το δέντρο έχει N = 15 στοιχεία. Ας πούμε ότι ψάχνω για το 208:

• Ξεκινάω από τη ρίζα της οποίας το κλειδί είναι 136. Από το 136<208, κοιτάζω το δεξί υποδέντρο του κόμβου 136.
• 398>208 επομένως κοιτάζω το αριστερό υποδέντρο του κόμβου 398
• 250>208 επομένως κοιτάζω το αριστερό υποδέντρο του κόμβου 250
• 200<208, επομένως κοιτάζω το δεξί υποδέντρο του κόμβου 200. Αλλά το 200 δεν έχει δεξί υποδέντρο, αξία δεν υπάρχει (γιατί αν υπάρχει, θα βρίσκεται στο δεξί υποδέντρο 200).

Τώρα ας πούμε ότι ψάχνω για 40

• Ξεκινάω από τη ρίζα της οποίας το κλειδί είναι 136. Από 136 > 40, κοιτάζω το αριστερό υποδέντρο του κόμβου 136.
• 80 > 40, επομένως κοιτάζω το αριστερό υποδέντρο του κόμβου 80
• 40= 40, υπάρχει κόμβος. Ανακτώ το αναγνωριστικό γραμμής μέσα στον κόμβο (δεν φαίνεται στην εικόνα) και αναζητώ στον πίνακα το αναγνωριστικό της συγκεκριμένης σειράς.
• Γνωρίζοντας το αναγνωριστικό της σειράς, μπορώ να γνωρίζω ακριβώς πού βρίσκονται τα δεδομένα στον πίνακα, ώστε να μπορώ να τα ανακτήσω αμέσως.

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

Ας επιστρέψουμε στο πρόβλημά μας

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

• Αν θέλετε να μάθετε ποιος εργάζεται στο Ηνωμένο Βασίλειο
• κοιτάζετε το δέντρο για να πάρετε τον κόμβο που αντιπροσωπεύει τη Μεγάλη Βρετανία
• μέσα στο "UKnode" θα βρείτε τη θέση των αρχείων εργαζομένων στο Ηνωμένο Βασίλειο.

Αυτή η αναζήτηση θα κοστίσει λειτουργίες log(N) αντί για λειτουργίες N εάν χρησιμοποιείτε απευθείας τον πίνακα. Αυτό που μόλις παρουσίασες ήταν ευρετήριο βάσης δεδομένων.

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

B+TreeIndex

Ενώ αυτό το δέντρο λειτουργεί καλά για να πάρει μια συγκεκριμένη τιμή, υπάρχει ένα ΜΕΓΑΛΟ πρόβλημα όταν το χρειάζεστε λάβετε πολλαπλά στοιχεία μεταξύ δύο τιμών. Αυτό θα κοστίσει O(N) επειδή θα πρέπει να κοιτάξετε κάθε κόμβο στο δέντρο και να ελέγξετε αν βρίσκεται μεταξύ αυτών των δύο τιμών (π.χ. με μια διατεταγμένη διέλευση του δέντρου). Επιπλέον, αυτή η λειτουργία δεν είναι φιλική προς το δίσκο I/O αφού πρέπει να διαβάσετε ολόκληρο το δέντρο. Πρέπει να βρούμε έναν τρόπο αποτελεσματικής εκτέλεσης αίτημα εμβέλειας. Για την επίλυση αυτού του προβλήματος, οι σύγχρονες βάσεις δεδομένων χρησιμοποιούν μια τροποποιημένη έκδοση του προηγούμενου δέντρου που ονομάζεται B+Tree. Σε ένα δέντρο B+Tree:

• μόνο οι χαμηλότεροι κόμβοι (φύλλα) αποθήκευση πληροφοριών (τοποθεσία σειρών στον σχετικό πίνακα)
• οι υπόλοιποι κόμβοι είναι εδώ για δρομολόγηση στον σωστό κόμβο κατά την αναζήτηση.

Όπως μπορείτε να δείτε, υπάρχουν περισσότεροι κόμβοι εδώ (δύο φορές). Πράγματι, έχετε επιπλέον κόμβους, "κόμβους απόφασης", που θα σας βοηθήσουν να βρείτε τον σωστό κόμβο (ο οποίος αποθηκεύει τη θέση των σειρών στον σχετικό πίνακα). Αλλά η πολυπλοκότητα αναζήτησης εξακολουθεί να είναι O(log(N)) (υπάρχει μόνο ένα ακόμη επίπεδο). Η μεγάλη διαφορά είναι ότι οι κόμβοι στο κατώτερο επίπεδο συνδέονται με τους διαδόχους τους.

Με αυτό το B+Tree, αν ψάχνετε για τιμές μεταξύ 40 και 100:

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

Ας υποθέσουμε ότι βρίσκετε M διαδόχους και το δέντρο έχει N κόμβους. Η εύρεση ενός συγκεκριμένου κόμβου κοστίζει log(N) όπως το προηγούμενο δέντρο. Αλλά μόλις λάβετε αυτόν τον κόμβο, θα λάβετε διαδόχους M στις λειτουργίες M με αναφορές στους διαδόχους τους. Αυτή η αναζήτηση κοστίζει μόνο M+log(N) πράξεις σε σύγκριση με N πράξεις στο προηγούμενο δέντρο. Επιπλέον, δεν χρειάζεται να διαβάσετε το πλήρες δέντρο (μόνο κόμβοι M+log(N), που σημαίνει λιγότερη χρήση δίσκου. Αν το M είναι μικρό (π.χ. 200 σειρές) και το N είναι μεγάλο (1 σειρές), θα υπάρχει ΜΕΓΑΛΗ διαφορά.

Αλλά υπάρχουν νέα προβλήματα εδώ (και πάλι!). Εάν προσθέσετε ή διαγράψετε μια σειρά στη βάση δεδομένων (και επομένως στο σχετικό ευρετήριο B+Tree):

• πρέπει να διατηρήσετε την τάξη μεταξύ των κόμβων μέσα σε ένα B+Tree, διαφορετικά δεν θα μπορείτε να βρείτε τους κόμβους μέσα σε ένα μη ταξινομημένο δέντρο.
• πρέπει να διατηρήσετε τον ελάχιστο δυνατό αριθμό επιπέδων στο B+Tree, διαφορετικά η χρονική πολυπλοκότητα O(log(N)) γίνεται O(N).

Με άλλα λόγια, το B+Tree πρέπει να είναι αυτοδιατεταγμένο και ισορροπημένο. Ευτυχώς, αυτό είναι δυνατό με τις έξυπνες λειτουργίες διαγραφής και εισαγωγής. Αλλά αυτό έχει ένα κόστος: οι εισαγωγές και οι διαγραφές σε ένα δέντρο B+ κοστίζουν O(log(N)). Γι' αυτό κάποιοι από εσάς το έχετε ακούσει Η χρήση πάρα πολλών ευρετηρίων δεν είναι καλή ιδέα. Πραγματικά, επιβραδύνετε τη γρήγορη εισαγωγή/ενημέρωση/διαγραφή μιας σειράς σε έναν πίνακαεπειδή η βάση δεδομένων πρέπει να ενημερώσει τα ευρετήρια του πίνακα χρησιμοποιώντας μια ακριβή λειτουργία O(log(N)) για κάθε ευρετήριο. Επιπλέον, η προσθήκη ευρετηρίων σημαίνει περισσότερο φόρτο εργασίας για διαχειριστής συναλλαγών (θα περιγραφεί στο τέλος του άρθρου).

Για περισσότερες λεπτομέρειες, μπορείτε να δείτε το άρθρο της Wikipedia B+Δέντρο. Εάν θέλετε ένα παράδειγμα εφαρμογής του B+Tree σε μια βάση δεδομένων, ρίξτε μια ματιά αυτο το αρθρο и αυτο το αρθρο από έναν κορυφαίο προγραμματιστή MySQL. Και οι δύο επικεντρώνονται στον τρόπο με τον οποίο το InnoDB (η μηχανή MySQL) χειρίζεται τα ευρετήρια.

Σημείωση: Ένας αναγνώστης μου είπε ότι, λόγω βελτιστοποιήσεων χαμηλού επιπέδου, το δέντρο B+ θα πρέπει να είναι πλήρως ισορροπημένο.

Hashtable

Η τελευταία σημαντική δομή δεδομένων μας είναι ο πίνακας κατακερματισμού. Αυτό είναι πολύ χρήσιμο όταν θέλετε να αναζητήσετε γρήγορα τιμές. Επιπλέον, η κατανόηση ενός πίνακα κατακερματισμού θα μας βοηθήσει αργότερα να κατανοήσουμε μια κοινή λειτουργία σύνδεσης βάσης δεδομένων που ονομάζεται σύνδεση κατακερματισμού ( hash join). Αυτή η δομή δεδομένων χρησιμοποιείται επίσης από τη βάση δεδομένων για την αποθήκευση ορισμένων εσωτερικών πραγμάτων (π. τραπεζάκι κλειδαριάς ή buffer pool, θα δούμε και τις δύο αυτές έννοιες αργότερα).

Ένας πίνακας κατακερματισμού είναι μια δομή δεδομένων που βρίσκει γρήγορα ένα στοιχείο με βάση το κλειδί του. Για να δημιουργήσετε έναν πίνακα κατακερματισμού πρέπει να ορίσετε:

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

Απλό παράδειγμα

Ας πάρουμε ένα ξεκάθαρο παράδειγμα:

Αυτός ο πίνακας κατακερματισμού έχει 10 τμήματα. Επειδή είμαι τεμπέλης, φωτογράφισα μόνο 5 τμήματα, αλλά ξέρω ότι είσαι έξυπνος, οπότε θα σε αφήσω να φανταστείς τα άλλα 5 μόνος σου. Χρησιμοποίησα μια συνάρτηση κατακερματισμού modulo 10 του κλειδιού. Με άλλα λόγια, αποθηκεύω μόνο το τελευταίο ψηφίο του κλειδιού του στοιχείου για να βρω το τμήμα του:

• εάν το τελευταίο ψηφίο είναι 0, το στοιχείο εμπίπτει στο τμήμα 0,
• εάν το τελευταίο ψηφίο είναι 1, το στοιχείο εμπίπτει στο τμήμα 1,
• αν το τελευταίο ψηφίο είναι 2, το στοιχείο εμπίπτει στην περιοχή 2,
• ...

Η συνάρτηση σύγκρισης που χρησιμοποίησα είναι απλώς η ισότητα μεταξύ δύο ακεραίων.

Ας υποθέσουμε ότι θέλετε να λάβετε το στοιχείο 78:

• Ο πίνακας κατακερματισμού υπολογίζει τον κωδικό κατακερματισμού για το 78, που είναι 8.
• Ο πίνακας κατακερματισμού κοιτάζει το τμήμα 8 και το πρώτο στοιχείο που βρίσκει είναι το 78.
• Σας επιστρέφει το αντικείμενο 78
• Η αναζήτηση κοστίζει μόνο 2 λειτουργίες (το ένα για τον υπολογισμό της τιμής κατακερματισμού και το άλλο για την αναζήτηση του στοιχείου μέσα στο τμήμα).

Τώρα ας υποθέσουμε ότι θέλετε να λάβετε το στοιχείο 59:

• Ο πίνακας κατακερματισμού υπολογίζει τον κωδικό κατακερματισμού για το 59, που είναι 9.
• Ο πίνακας κατακερματισμού αναζητά στο τμήμα 9, το πρώτο στοιχείο που βρέθηκε είναι 99. Από 99!=59, το στοιχείο 99 δεν είναι έγκυρο στοιχείο.
• Με την ίδια λογική λαμβάνονται το δεύτερο στοιχείο (9), το τρίτο (79), ..., το τελευταίο (29).
• Το στοιχείο δεν βρέθηκε.
• Η αναζήτηση κόστισε 7 επεμβάσεις.

Καλή λειτουργία κατακερματισμού

Όπως μπορείτε να δείτε, ανάλογα με την αξία που ψάχνετε, το κόστος δεν είναι το ίδιο!

Αν τώρα αλλάξω τη συνάρτηση κατακερματισμού modulo 1 του κλειδιού (δηλαδή, παίρνοντας τα τελευταία 000 ψηφία), η δεύτερη αναζήτηση κοστίζει μόνο 000 λειτουργία, καθώς δεν υπάρχουν στοιχεία στο τμήμα 6. Η πραγματική πρόκληση είναι να βρείτε μια καλή συνάρτηση κατακερματισμού που θα δημιουργεί κουβάδες που περιέχουν πολύ μικρό αριθμό στοιχείων.

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

• συμβολοσειρά (για παράδειγμα - επώνυμο)
• 2 γραμμές (για παράδειγμα - επώνυμο και όνομα)
• 2 γραμμές και ημερομηνία (για παράδειγμα - επίθετο, όνομα και ημερομηνία γέννησης)
• ...

Με μια καλή συνάρτηση κατακερματισμού, οι αναζητήσεις πίνακα κατακερματισμού κοστίζουν O(1).

Πίνακας πίνακα εναντίον κατακερματισμού

Γιατί να μην χρησιμοποιήσετε έναν πίνακα;

Χμ, καλή ερώτηση.

• Ο πίνακας κατακερματισμού μπορεί να είναι μερικώς φορτωμένο στη μνήμη, και τα υπόλοιπα τμήματα μπορούν να παραμείνουν στο δίσκο.
• Με έναν πίνακα πρέπει να χρησιμοποιείτε συνεχόμενο χώρο στη μνήμη. Εάν φορτώνετε ένα μεγάλο τραπέζι είναι πολύ δύσκολο να βρεθεί αρκετός συνεχής χώρος.
• Για έναν πίνακα κατακερματισμού, μπορείτε να επιλέξετε το κλειδί που θέλετε (για παράδειγμα, χώρα και επώνυμο ατόμου).

Για περισσότερες πληροφορίες, μπορείτε να διαβάσετε το άρθρο σχετικά JavaHashMap, που είναι μια αποτελεσματική υλοποίηση ενός πίνακα κατακερματισμού. δεν χρειάζεται να κατανοήσετε Java για να κατανοήσετε τις έννοιες που καλύπτονται σε αυτό το άρθρο.

Πηγή: www.habr.com