Inserimento in un $B^+$-tree

Inizialmente la radice è l’unico nodo dell’albero: essendo quindi un nodo foglia conterrà anche i puntatori ai dati

Se si cerca di inserire un’entry in un nodo foglia pieno, il nodo va in overflow e deve essere scisso:

• le prime $j =\lceil \frac{(p_{leaf}+1)}{2} \rceil$ entry sono mantenute nel nodo, mentre le rimanenti sono spostate in un nuovo nodo foglia
• il j-mo valore di ricerca (quello mediano) è replicato nel nodo padre
• nel padre viene creato un puntatore al nuovo nodo

Se il nodo padre (interno) è pieno si ha un altro overflow:

• il nodo viene diviso, creando un nuovo nodo interno
• le entrate nel nodo interno fino a $P_j$ (con $j = \lfloor \frac{(p+1)}{2} \rfloor$) sono mantenute nel nodo originario, mentre il j-mo valore di ricerca è spostato al padre, non replicato
• il nuovo nodo interno conterrà le entrate dalla $P_{j+1}$ alla fine delle entrate del nodo originario

Tale scissione si può propagare verso l’alto fino a creare un nuovo livello per il $B^+$-tree

Esempio di inserimento

Cancellazione in un $B^+$-tree

Un’entry è cancellata sempre a livello foglie

Se essa ricorre anche in un nodo interno, allora è rimossa anche da quello e al suo posto si inserisce il valore immediatamente alla sinistra del valore rimosso nel nodo foglia

La cancellazione di valori può causare l’underflow di un nodo, riducendo il numero di entry in un nodo foglia per meno del minimo consentito: