Change search
ReferencesLink to record
Permanent link

Direct link
Improving RRB-Tree Performance through Transience
Norwegian University of Science and Technology, Faculty of Information Technology, Mathematics and Electrical Engineering, Department of Computer and Information Science.
2014 (English)MasteroppgaveStudent thesis
Abstract [en]

The RRB-tree is a confluently persistent data structure based on the persistent vector, with efficient concatenation and slicing, and effectively constant time indexing, updates and iteration. Although efficient appends have been discussed, they have not been properly studied. This thesis formally describes the persistent vector and the RRB-tree, and presents three optimisations for the RRB-tree which have been successfully used in the persistent vector. The differences between the implementations are discussed, and the performance is measured. To measure the performance, the C library librrb is implemented with the proposed optimisations. Results shows that the optimisations improves the append performance of the RRB-tree considerably, and suggests that its performance is comparable to mutable array lists in certain situations.

Place, publisher, year, edition, pages
Institutt for datateknikk og informasjonsvitenskap , 2014. , 143 p.
Keyword [no]
ntnudaim:10264, MTDT Datateknologi, Komplekse datasystemer
URN: urn:nbn:no:ntnu:diva-27336Local ID: ntnudaim:10264OAI: diva2:769310
Available from: 2014-12-07 Created: 2014-12-07

Open Access in DiVA

fulltext(1294 kB)285 downloads
File information
File name FULLTEXT01.pdfFile size 1294 kBChecksum SHA-512
Type fulltextMimetype application/pdf
cover(394 kB)0 downloads
File information
File name COVER01.pdfFile size 394 kBChecksum SHA-512
Type coverMimetype application/pdf
attachment(14801 kB)15 downloads
File information
File name ATTACHMENT01.zipFile size 14801 kBChecksum SHA-512
Type attachmentMimetype application/zip

By organisation
Department of Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 285 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 14 hits
ReferencesLink to record
Permanent link

Direct link