research-article

FB-tree: a B⁺-tree for flash-based SSDs

Authors:

Martin V. Jørgensen,

René B. Rasmussen,

Simonas Šaltenis,

Carsten SchjønningAuthors Info & Claims

IDEAS '11: Proceedings of the 15th Symposium on International Database Engineering & Applications

Pages 34 - 42

https://doi.org/10.1145/2076623.2076629

Published: 21 September 2011 Publication History

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.

References

[1]

D. Agrawal, D. Ganesan, R. Sitaraman, Y. Diao, and S. Singh. Lazy-Adaptive Tree: An Optimized Index Structure for Flash Devices. PVLDB, 2(1):361--372, 2009.

Digital Library

[2]

K. Bennett. Ask an Intel Solid State Drive Engineer, Jan 2009. www.hardocp.com/article/2009/01/13/ask_intel_solid_state_drive_engineer.

[3]

M. Dunn and A. L. N. Reddy. A New I/O Scheduler for Solid State Devices. Technical report, 2009.

[4]

G. Graefe. Write-Optimized B-Trees. In proc. of VLDB, pp. 672--683, 2004.

Digital Library

[5]

G. Graefe. The Five-Minute Rule 20 Years Later (and How Flash Memory Changes the Rules). Communications of the ACM, 52(7):48--59, 2009.

Digital Library

[6]

G. Graefe. Modern B-Tree Techniques. Foundations and Trends in Databases, 3(4):203--402, 2011.

Digital Library

[7]

T. Johnson and D. Shasha. B-Trees with Inserts and Deletes: Why Free-at-Empty Is Better Than Merge-at-Half. J. Comput. Syst. Sci., 47(1):45--76, 1993.

Digital Library

[8]

S.-W. Lee and B. Moon. Design of Flash-Based DBMS: An In-Page Logging Approach. In proc. of SIGMOD Conference, pp. 55--66, 2007.

Digital Library

[9]

Y. Li, B. He, R. J. Yang, Q. Luo, and K. Yi. Tree Indexing on Solid State Drives. PVLDB, 3:1195--1206, 2010.

Digital Library

[10]

M. Moshayedi and P. Wilkison. Enterprise SSDs. Queue, 6, July 2008.

Digital Library

[11]

G.-J. Na, S.-W. Lee, and B. Moon. Dynamic In-Page Logging for Flash-Aware B-Tree Index. In proc of CIKM, pp. 1485--1488, 2009.

Digital Library

[12]

P. E. O'Neil, E. Cheng, D. Gawlick, and E. J. O'Neil. The Log-Structured Merge-Tree (LSM-Tree). Acta Inf., 33(4):351--385, 1996.

Digital Library

[13]

Y. Ou, T. Härder, and P. Jin. CFDC: A Flash-Aware Replacement Policy for Database Buffer Management. In proc. of DaMoN, pp. 15--20, 2009.

Digital Library

[14]

S.-Y. Park, D. Jung, J.-U. Kang, J. Kim, and J. Lee. CFLRU: A Replacement Algorithm for Flash Memory. In proc. of CASES, pp. 234--241, 2006.

Digital Library

[15]

RethinkDB. www.rethinkdb.com, April 2010.

[16]

M. Rosenblum and J. K. Ousterhout. The Design and Implementation of a Log-Structured File System. ACM Trans. Comput. Syst., 10(1):26--52, 1992.

Digital Library

[17]

A. S. Tanenbaum. Modern Operating Systems. Prentice-Hall, 3. edition, 2008.

Digital Library

[18]

Y. Wang, K. Goda, and M. Kitsuregawa. Evaluating Non-In-Place Update Techniques for Flash-Based Transaction Processing Systems. In Proceedings of DEXA Conf., pp. 777--791, 2009.

Digital Library

[19]

C.-H. Wu, T.-W. Kuo, and L.-P. Chang. An Efficient B-tree Layer Implementation for Flash-Memory Storage Systems. ACM Trans. Embedded Comput. Syst., 6(3), 2007.

Digital Library

[20]

S. Yin, P. Pucheral, and X. Meng. A Sequential Indexing Scheme for Flash-Based Embedded Systems. In proc. of EDBT, pp. 588--599, 2009.

Digital Library

Cited By

Wu JZhang YChen SWang JChen YXing C(2021)Updatable learned index with precise positionsProceedings of the VLDB Endowment10.14778/3457390.345739314:8(1276-1288)Online publication date: 21-Oct-2021
https://dl.acm.org/doi/10.14778/3457390.3457393
Fevgas AAkritidis LBozanis PManolopoulos Y(2019)Indexing in flash storage devices: a survey on challenges, current approaches, and future trendsThe VLDB Journal10.1007/s00778-019-00559-8Online publication date: 3-Aug-2019
https://doi.org/10.1007/s00778-019-00559-8
Lustiber GCheung AElmore A(2017)E-TreeProceedings of the 2017 ACM International Conference on Management of Data10.1145/3055167.3055178(13-15)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1145/3055167.3055178
Show More Cited By

Index Terms

FB-tree: a B⁺-tree for flash-based SSDs
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods

Recommendations

Optimizing B+-tree for hybrid storage systems

Flash-memory-based solid state drives (SSD) have been widely used in computer systems. Due to the high price and some specific features of SSD such as asymmetric read/write speeds and limited erasure endurance, it has been a very common solution, e.g., ...
ACS: an alternate coding scheme to improve degrade read performance for SSD-based RAID5 systems

To guarantee high performance and reliability, storage systems require better devices and data redundancy schemes, e.g., SSD-based RAID5. However, failures in the large-scale storage systems are common. In order to serve requests on a failed node, the SSD-...
Read/write-optimized tree indexing for solid-state drives

Flash-memory-based solid-state drives (SSDs) are used widely for secondary storage. To be effective for SSDs, traditional indices have to be redesigned to cope with the special properties of flash memory, such as asymmetric read/write latencies (fast ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

IDEAS '11: Proceedings of the 15th Symposium on International Database Engineering & Applications

September 2011

274 pages

ISBN:9781450306270

DOI:10.1145/2076623

General Chair:
Bipin C. Desai
Concordia University
,
Program Chairs:
Isabel Cruz
University of Illinois at Chicago
,
Jorge Bernardino
Instituto Politecnico de Coimbra

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 September 2011

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

IDEAS '11

IDEAS '11: 15th International Database Engineering & Applications Symposium

September 21 - 23, 2011

Lisboa, Portugal

Acceptance Rates

Overall Acceptance Rate 74 of 210 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

21
Total Citations
View Citations
471
Total Downloads

Downloads (Last 12 months)11
Downloads (Last 6 weeks)1

Reflects downloads up to 01 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wu JZhang YChen SWang JChen YXing C(2021)Updatable learned index with precise positionsProceedings of the VLDB Endowment10.14778/3457390.345739314:8(1276-1288)Online publication date: 21-Oct-2021
https://dl.acm.org/doi/10.14778/3457390.3457393
Fevgas AAkritidis LBozanis PManolopoulos Y(2019)Indexing in flash storage devices: a survey on challenges, current approaches, and future trendsThe VLDB Journal10.1007/s00778-019-00559-8Online publication date: 3-Aug-2019
https://doi.org/10.1007/s00778-019-00559-8
Lustiber GCheung AElmore A(2017)E-TreeProceedings of the 2017 ACM International Conference on Management of Data10.1145/3055167.3055178(13-15)Online publication date: 14-May-2017
https://dl.acm.org/doi/10.1145/3055167.3055178
Wang SQin XBao ZLi B(2017)Tide-treeWorld Wide Web10.1007/s11280-016-0426-920:5(1017-1045)Online publication date: 1-Sep-2017
https://dl.acm.org/doi/10.1007/s11280-016-0426-9
Jin RCho HChung TKim DKim SLee SHanzo KIsmail R(2014)A group round robin based b-tree index storage scheme for flash memory devicesProceedings of the 8th International Conference on Ubiquitous Information Management and Communication10.1145/2557977.2558067(1-6)Online publication date: 9-Jan-2014
https://dl.acm.org/doi/10.1145/2557977.2558067
Sippu SSoisalon-Soininen ESippu SSoisalon-Soininen E(2014)Advanced Locking ProtocolsTransaction Processing10.1007/978-3-319-12292-2_9(221-236)Online publication date: 16-Nov-2014
https://doi.org/10.1007/978-3-319-12292-2_9
Sippu SSoisalon-Soininen ESippu SSoisalon-Soininen E(2014)B-Tree Structure ModificationsTransaction Processing10.1007/978-3-319-12292-2_8(185-219)Online publication date: 17-Nov-2014
https://doi.org/10.1007/978-3-319-12292-2_8
Sippu SSoisalon-Soininen ESippu SSoisalon-Soininen E(2014)B-Tree TraversalsTransaction Processing10.1007/978-3-319-12292-2_7(159-183)Online publication date: 17-Nov-2014
https://doi.org/10.1007/978-3-319-12292-2_7
Sippu SSoisalon-Soininen ESippu SSoisalon-Soininen E(2014)Lock-Based Concurrency ControlTransaction Processing10.1007/978-3-319-12292-2_6(125-158)Online publication date: 17-Nov-2014
https://doi.org/10.1007/978-3-319-12292-2_6
Sippu SSoisalon-Soininen ESippu SSoisalon-Soininen E(2014)Transactional IsolationTransaction Processing10.1007/978-3-319-12292-2_5(101-124)Online publication date: 17-Nov-2014
https://doi.org/10.1007/978-3-319-12292-2_5
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents