FB-Tree: A B+-Tree for Flash-Based SSDs

Martin V. Jørgensen, René B. Rasmussen, Simonas Saltenis, Carsten Schjønning

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

6 Citations (Scopus)

Abstract

Due to their many advantages, flash-based SSDs (Solid-State Drives) have become a mainstream alternative to magnetic disks for database servers. Nevertheless, database systems, designed and optimized for magnetic disks, still do not fully exploit all the benefits of the new technology.

We propose the FB-tree: a combination of an adapted B+-tree, a storage manager, and a buffer manager, all optimized for modern SSDs. Together the techniques enable writing to SSDs in relatively large blocks, thus achieving greater overall throughput. This is achieved by the out-of-place writing, whereby every time a modified index node is written, it is written to a new address, clustered with some other nodes that are written together. While this constantly frees index nodes, the FB-tree does not introduce any garbage-collection overhead, instead relying on naturally occurring free-space segments of sufficient size. As a consequence, the FB-tree outperforms a regular B+-tree in all scenarios tested. For instance, the throughput of a random workload of 75% updates increases by a factor of three using only two times the space of the B+-tree.
Original languageEnglish
Title of host publicationProceedings of the 15th Symposium on International Database Engineering & Applications
Number of pages9
PublisherAssociation for Computing Machinery
Publication date2011
Pages34-42
ISBN (Print)978-1-4503-0627-0
DOIs
Publication statusPublished - 2011
EventInternational Database Engineering & Applications Symposium - Lisbon, Portugal
Duration: 21 Sep 201123 Sep 2011
Conference number: 15

Conference

ConferenceInternational Database Engineering & Applications Symposium
Number15
CountryPortugal
CityLisbon
Period21/09/201123/09/2011

Fingerprint

Flash-based SSDs
Managers
Throughput
Servers

Cite this

Jørgensen, M. V., Rasmussen, R. B., Saltenis, S., & Schjønning, C. (2011). FB-Tree: A B+-Tree for Flash-Based SSDs. In Proceedings of the 15th Symposium on International Database Engineering & Applications (pp. 34-42). Association for Computing Machinery. https://doi.org/10.1145/2076623.2076629
Jørgensen, Martin V. ; Rasmussen, René B. ; Saltenis, Simonas ; Schjønning, Carsten. / FB-Tree: A B+-Tree for Flash-Based SSDs. Proceedings of the 15th Symposium on International Database Engineering & Applications. Association for Computing Machinery, 2011. pp. 34-42
@inproceedings{2153151ac1fc48c69279f5c1e0255d12,
title = "FB-Tree: A B+-Tree for Flash-Based SSDs",
abstract = "Due to their many advantages, flash-based SSDs (Solid-State Drives) have become a mainstream alternative to magnetic disks for database servers. Nevertheless, database systems, designed and optimized for magnetic disks, still do not fully exploit all the benefits of the new technology.We propose the FB-tree: a combination of an adapted B+-tree, a storage manager, and a buffer manager, all optimized for modern SSDs. Together the techniques enable writing to SSDs in relatively large blocks, thus achieving greater overall throughput. This is achieved by the out-of-place writing, whereby every time a modified index node is written, it is written to a new address, clustered with some other nodes that are written together. While this constantly frees index nodes, the FB-tree does not introduce any garbage-collection overhead, instead relying on naturally occurring free-space segments of sufficient size. As a consequence, the FB-tree outperforms a regular B+-tree in all scenarios tested. For instance, the throughput of a random workload of 75{\%} updates increases by a factor of three using only two times the space of the B+-tree.",
author = "J{\o}rgensen, {Martin V.} and Rasmussen, {Ren{\'e} B.} and Simonas Saltenis and Carsten Schj{\o}nning",
year = "2011",
doi = "10.1145/2076623.2076629",
language = "English",
isbn = "978-1-4503-0627-0",
pages = "34--42",
booktitle = "Proceedings of the 15th Symposium on International Database Engineering & Applications",
publisher = "Association for Computing Machinery",
address = "United States",

}

Jørgensen, MV, Rasmussen, RB, Saltenis, S & Schjønning, C 2011, FB-Tree: A B+-Tree for Flash-Based SSDs. in Proceedings of the 15th Symposium on International Database Engineering & Applications. Association for Computing Machinery, pp. 34-42, International Database Engineering & Applications Symposium, Lisbon, Portugal, 21/09/2011. https://doi.org/10.1145/2076623.2076629

FB-Tree: A B+-Tree for Flash-Based SSDs. / Jørgensen, Martin V.; Rasmussen, René B.; Saltenis, Simonas; Schjønning, Carsten.

Proceedings of the 15th Symposium on International Database Engineering & Applications. Association for Computing Machinery, 2011. p. 34-42.

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

TY - GEN

T1 - FB-Tree: A B+-Tree for Flash-Based SSDs

AU - Jørgensen, Martin V.

AU - Rasmussen, René B.

AU - Saltenis, Simonas

AU - Schjønning, Carsten

PY - 2011

Y1 - 2011

N2 - Due to their many advantages, flash-based SSDs (Solid-State Drives) have become a mainstream alternative to magnetic disks for database servers. Nevertheless, database systems, designed and optimized for magnetic disks, still do not fully exploit all the benefits of the new technology.We propose the FB-tree: a combination of an adapted B+-tree, a storage manager, and a buffer manager, all optimized for modern SSDs. Together the techniques enable writing to SSDs in relatively large blocks, thus achieving greater overall throughput. This is achieved by the out-of-place writing, whereby every time a modified index node is written, it is written to a new address, clustered with some other nodes that are written together. While this constantly frees index nodes, the FB-tree does not introduce any garbage-collection overhead, instead relying on naturally occurring free-space segments of sufficient size. As a consequence, the FB-tree outperforms a regular B+-tree in all scenarios tested. For instance, the throughput of a random workload of 75% updates increases by a factor of three using only two times the space of the B+-tree.

AB - Due to their many advantages, flash-based SSDs (Solid-State Drives) have become a mainstream alternative to magnetic disks for database servers. Nevertheless, database systems, designed and optimized for magnetic disks, still do not fully exploit all the benefits of the new technology.We propose the FB-tree: a combination of an adapted B+-tree, a storage manager, and a buffer manager, all optimized for modern SSDs. Together the techniques enable writing to SSDs in relatively large blocks, thus achieving greater overall throughput. This is achieved by the out-of-place writing, whereby every time a modified index node is written, it is written to a new address, clustered with some other nodes that are written together. While this constantly frees index nodes, the FB-tree does not introduce any garbage-collection overhead, instead relying on naturally occurring free-space segments of sufficient size. As a consequence, the FB-tree outperforms a regular B+-tree in all scenarios tested. For instance, the throughput of a random workload of 75% updates increases by a factor of three using only two times the space of the B+-tree.

U2 - 10.1145/2076623.2076629

DO - 10.1145/2076623.2076629

M3 - Article in proceeding

SN - 978-1-4503-0627-0

SP - 34

EP - 42

BT - Proceedings of the 15th Symposium on International Database Engineering & Applications

PB - Association for Computing Machinery

ER -

Jørgensen MV, Rasmussen RB, Saltenis S, Schjønning C. FB-Tree: A B+-Tree for Flash-Based SSDs. In Proceedings of the 15th Symposium on International Database Engineering & Applications. Association for Computing Machinery. 2011. p. 34-42 https://doi.org/10.1145/2076623.2076629