[Teoria] Numero massimo chiavi in un B-albero
Buongiorno a tutti 
Stavo cercando di dare una risposta ad un esercizio che mi chiede di determinare il numero massimo di chiavi memorizzabili in un B-albero di altezza $h$ esprimendo tale valore in funzione del grado minimo $t$.
Ho ragionato nel modo seguente. Nel caso di un B-albero pieno abbiamo che ciascun nodo ospita il numero massimo di chiavi, ossia $2t - 1$. Pertanto ciascun nodo avrà un numero di figli pari a $2t$. Ora, facendo i dovuti calcoli ed indicando con $n$ il numero di chiavi, risulterà che:
$$n \le (2t - 1)\sum_{i = 0}^{h} (2t)^i = (2t - 1) \frac{(2t)^h - 1}{2t - 1} = (2t)^h -1.$$
Chiedo perché poi cercando in rete ho trovato diverse informazioni contrastanti, in particolare qui.
Colgo l'occasione per porre anche un'altra domanda che è comunque in parte attinente al mio quesito: il valore corretto risultante dallo sviluppo della serie geometrica $\sum_{k = 0}^{n} x^k$ è $\frac{1 - x^n}{1 - x}$ oppure $\frac{x^n - 1}{x - 1}$
Anche qui sul mio libro di algoritmi e sul web ho trovato scritture diverse.
Ringrazio per le risposte.
Stavo cercando di dare una risposta ad un esercizio che mi chiede di determinare il numero massimo di chiavi memorizzabili in un B-albero di altezza $h$ esprimendo tale valore in funzione del grado minimo $t$.
Ho ragionato nel modo seguente. Nel caso di un B-albero pieno abbiamo che ciascun nodo ospita il numero massimo di chiavi, ossia $2t - 1$. Pertanto ciascun nodo avrà un numero di figli pari a $2t$. Ora, facendo i dovuti calcoli ed indicando con $n$ il numero di chiavi, risulterà che:
$$n \le (2t - 1)\sum_{i = 0}^{h} (2t)^i = (2t - 1) \frac{(2t)^h - 1}{2t - 1} = (2t)^h -1.$$
Chiedo perché poi cercando in rete ho trovato diverse informazioni contrastanti, in particolare qui.
Colgo l'occasione per porre anche un'altra domanda che è comunque in parte attinente al mio quesito: il valore corretto risultante dallo sviluppo della serie geometrica $\sum_{k = 0}^{n} x^k$ è $\frac{1 - x^n}{1 - x}$ oppure $\frac{x^n - 1}{x - 1}$
Anche qui sul mio libro di algoritmi e sul web ho trovato scritture diverse.Ringrazio per le risposte.
Risposte
Ciao, onlyReferee.
Rispondo al secondo quesito (per il primo non mi ritengo sufficientemente competente): le due relazioni per il calcolo del valore della sommatoria geometrica (non serie, costituita da infiniti addendi) sono equivalenti: infatti puoi passare da una relazione all'altra semplicemente moltiplicando numeratore e denominatore per lo stesso fattore $-1$.
Per trattare, invece, la serie geometrica vera e propria, devi supporre che il modulo della ragione della progressione geometrica sia inferiore ad 1 e devi far tendere $n$ (numero di addendi della sommatoria) all'infinito.
Saluti.
Rispondo al secondo quesito (per il primo non mi ritengo sufficientemente competente): le due relazioni per il calcolo del valore della sommatoria geometrica (non serie, costituita da infiniti addendi) sono equivalenti: infatti puoi passare da una relazione all'altra semplicemente moltiplicando numeratore e denominatore per lo stesso fattore $-1$.
Per trattare, invece, la serie geometrica vera e propria, devi supporre che il modulo della ragione della progressione geometrica sia inferiore ad 1 e devi far tendere $n$ (numero di addendi della sommatoria) all'infinito.
Saluti.
Ok, grazie molte alessandro8.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo