Ερώτηση στα b-trees

[kaktos7]

Καλησπέρα παιδιά, θα ήθελα να ρωτήσω μια απορία στα b-trees, έχω το παρακάτω b-tree και κάνω εισαγωγή το στοιχείο 17:

                                   5            9              13      

                            /              /             \                 \

               2 3 4              6 7 8         10 11 12         14 15 16

 

Εισαγωγή του 17:

                                   5            9              13       

                            /              /             \                 \

               2 3 4              6 7 8         10 11 12         14 15 16 17

επειδή το παραπάνω δεν είναι b-tree το φτίαχνω και προκύπτει το:

 

               5           9              13             15

      /               /               /               \                 \

2 3 4           6 7 8     10 11 12       14              16 17 

το παραπάνω είναι ένα 5αδικό δέντρο, εγώ νομίζω πως σε αυτό το σημείο είμαστε όκ. Ο καθηγητής μου το προχωράει και άλλο και δίνει αυτό το b-tree τελικά;

                                                  9

                                           /                     \

                                       5                  13            15 

                                    /      \          /              /            \

                           2 3 4     6 7 8  10 11 12   14     16 17

Γιατί αυτό, γιατί φτίαχνει αυτό το δέντρο εφόσον το παραπάνω 5αδικο είναι σωστό και έγινε η εισαγωγή;

Ευχαριστώ!

           

[cyberrobot]

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

[Χάρι Πότερ]

Καλησπέρα παιδιά, θα ήθελα να ρωτήσω μια απορία στα b-trees, έχω το παρακάτω b-tree και κάνω εισαγωγή το στοιχείο 17:

                                   5            9              13      

                            /              /             \                 \

               2 3 4              6 7 8         10 11 12         14 15 16

 

Εισαγωγή του 17:

                                   5            9              13       

                            /              /             \                 \

               2 3 4              6 7 8         10 11 12         14 15 16 17

επειδή το παραπάνω δεν είναι b-tree το φτίαχνω και προκύπτει το:

 

               5           9              13             15

      /               /               /               \                 \

2 3 4           6 7 8     10 11 12       14              16 17 

το παραπάνω είναι ένα 5αδικό δέντρο, εγώ νομίζω πως σε αυτό το σημείο είμαστε όκ. Ο καθηγητής μου το προχωράει και άλλο και δίνει αυτό το b-tree τελικά;

                                                  9

                                           /                     \

                                       5                  13            15 

                                    /      \          /              /            \

                           2 3 4     6 7 8  10 11 12   14     16 17

Γιατί αυτό, γιατί φτίαχνει αυτό το δέντρο εφόσον το παραπάνω 5αδικο είναι σωστό και έγινε η εισαγωγή;

Ευχαριστώ!

Εφοσον οταν εισηγαγες το 17 ο κομβος που περιειχε τα 14,15,16 έκανε overflow, φανταζομαι οτι το μεγιστο πλήθος κλειδιων που μπορει να κρατίσει ενας κόμβος ειναι 3. Για τον ίδιο λόγο ο κόμβος ριζα που περιεχει 5,9,13,15 κάνει overflow και πρεπει να "ανεβασεις" ένα κλειδι στον πατερα(που σε αυτη την περιπτωση δεν υπαρχει - αρα δημιουργειται και γίνεται η νεα ρίζα). Σε αυτη την περιπτωση ανεβασε το 9

[epir21]

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

Α ρε Τσακαλίδη θεε ;p

 

Εφοσον οταν εισηγαγες το 17 ο κομβος που περιειχε τα 14,15,16 έκανε overflow, φανταζομαι οτι το μεγιστο πλήθος κλειδιων που μπορει να κρατίσει ενας κόμβος ειναι 3. Για τον ίδιο λόγο ο κόμβος ριζα που περιεχει 5,9,13,15 κάνει overflow και πρεπει να "ανεβασεις" ένα κλειδι στον πατερα(που σε αυτη την περιπτωση δεν υπαρχει - αρα δημιουργειται και γίνεται η νεα ρίζα). Σε αυτη την περιπτωση ανεβασε το 9

Θα συμφωνήσω με τον φίλο..

Έχεις μέχρι 4 παιδιά, αρα 3 κλειδιά.

Οπότε πρέπει να κανεις τις αλλαγές που φαίνονται στην τελευταία κατάσταση.