Predictive B+ tree: differenze tra le versioni

Versione delle 16:56, 24 ott 2015

Versione delle 22:07, 8 gen 2016

Riga 1:

Il '''Predictive B+ Tree''' (abbreviato '''BP Tree''' o '''<math>B^P</math> Tree''') è una variante del [[B-Albero#B.2BTree|B+ Tree]] studiata appositamente per operare con [[Memoria_a_cambiamento_di_faseMemoria a cambiamento di fase|memorie a cambiamento di fase]] (o PCM, Phase Change Memory).

Il BP Tree è stato presentato nel ''IEEE transaction on knowledge and data engineering, vol.26, N°10 di Ottobre 2014'' ed ancora in fase di sperimentazione<ref>{{cita web |url=http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6702416

|titolo=IEEE transaction on knowledge and data engineering, vol.26, N°10, OCT 2014 |lingua=en |sito=IEEE}}</ref>. Gli autori principali di questo albero binario sono Weiwei Hu, Dalie Sun, Guoliang Li, Kian-Lee Tan e Jiacai Ni. La prima presentazione del progetto è stata fatta presso l'[[Università_TsinghuaUniversità Tsinghua|Università di Tsinghua]] come tesi di laurea di Weiwei Hu dal titolo ''Redesign of database algorithms for next generation non-volatile memory technology''.<ref>{{cita web |url=http://www.scholarbank.nus.edu.sg/bitstream/handle/10635/36540/HuWW.pdf

|titolo=Redesign of database algorithms for next generation non-volatile memory technology |lingua=en |sito=scholarbank.nus.edu.sg}}</ref>.

Riga 20:

!

! [[DRAM]]

! [[Memoria_a_cambiamento_di_faseMemoria a cambiamento di fase|PCM]]

! [[Memoria_flashMemoria flash#NAND_FlashNAND Flash|NAND]]

! [[Disco_rigidoDisco rigido|HDD]]

|-

! Densità

Riga 81:

Come anticipato, sulla PCM viene memorizzato il vero e proprio BP Tree (altezza h e branching factor 2M), ossia un albero binario del tutto uguale al B+ Tree ad eccezione di alcune caratteristiche:

* La struttura ed i nodi possono essere pre-allocati.

* Dato il branching factor 2M del BP Tree, il numero di nodi figlio di un nodo interno può essere minore di M (comunque compreso tra 0 e 2M).

* Differente gestione degli inserimenti e delle cancellazione rispetto ai B+ Tree.

Riga 88 ⟶ 87:

=== Fase di Warm-Up ===

[[File:BPTree-WarmUp.png|thumb|Esempio di fase di Warm-Up. Il B+ Tree è pieno e viene trasferito nella PCM. Nell’istogramma la parte blu rappresenta l’effettiva distribuzione delle chiavi, la parte rossa la predizione ottenuta con il modello matematico. Il nodo C del B+ Tree viene scisso nel BP Tree nei nodi C e C’ a causa della predizione futura.]]

Con questo termine si identifica la prima fase di creazione di un BP Tree. Inizialmente il BP Tree è vuoto e utilizziamo il B+ Tree presente nella DRAM per la creazione del primo albero binario. Ad ogni nodo inserito aggiorniamo l’istogramma delle distribuzioni. Quando il buffer sarà pieno lo svuoteremo sulla PCM, creando così lo scheletro del BP Tree. Durante la fase di trascrittura del B+ Tree nella PCM sarà utilizzato il modello predittivo in funzione dei dati presenti nell’istogramma per scindere o concatenare i nodi che saranno parte del BP Tree.

Riga 111 ⟶ 109:

== Voci correlate ==

* [[B-Tree]]

* [[Memoria_a_cambiamento_di_faseMemoria a cambiamento di fase|PCM]]

* [[DRAM]]

== Collegamenti esterni ==

* [{{cita web|url=http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=6702416 |titolo=IEEE transaction on knowledge and data engineering, vol.26, N°10, OCT 2014]}}

* [{{cita web|http://www.scholarbank.nus.edu.sg/bitstream/handle/10635/36540/HuWW.pdf |Redesign of database algorithms for next generation non-volatile memory technology]}}

{{Portale|informatica}}