Large flash disks, or solid state drives (SSDs), have become an attractive
\nalternative to magnetic hard disks, due to their high random
\nread performance, low energy consumption and other features.
\nHowever, writes, especially small random writes, on flash disks
\nare inherently much slower than reads because of the erase-beforewrite
\nmechanism.
\nTo address this asymmetry of read-write speeds in tree indexing
\non the flash disk, we propose FD-tree, a tree index designed with
\nthe logarithmic method and fractional cascading techniques. With
\nthe logarithmic method, an FD-tree consists of the head tree \u2013 a
\nsmall B+-tree on the top, and a few levels of sorted runs of increasing
\nsizes at the bottom. This design is write-optimized for the flash
\ndisk; in particular, an index search will potentially go through more
\nlevels or visit more nodes, but random writes are limited to a small
\narea \u2013 the head tree, and are subsequently transformed into sequential
\nones through merging into the lower runs. With the fractional
\ncascading technique, we store pointers, called fences, in lower level
\nruns to speed up the search. Given an FD-tree of n entries, we analytically
\nshow that it performs an update in O(logB n) sequential
\nI\/Os and completes a search in O(logB n) random I\/Os, where B
\nis the flash page size. We evaluate FD-tree in comparison with representative
\nB+-tree variants under a variety of workloads on three
\ncommodity flash SSDs. Our results show that FD-tree has a similar
\nsearch performance to the standard B+-tree, and a similar update
\nperformance to the write-optimized B+-tree variant. As a result,
\nFD-tree dominates the other B+-tree index variants on the overall
\nperformance on flash disks as well as on magnetic disks.<\/p>\n","protected":false},"excerpt":{"rendered":"
Large flash disks, or solid state drives (SSDs), have become an attractive alternative to magnetic hard disks, due to their high random read performance, low energy consumption and other features. However, writes, especially small random writes, on flash disks are inherently much slower than reads because of the erase-beforewrite mechanism. To address this asymmetry of […]<\/p>\n","protected":false},"featured_media":0,"template":"","meta":{"msr-url-field":"","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"footnotes":""},"msr-content-type":[3],"msr-research-highlight":[],"research-area":[13563],"msr-publication-type":[193716],"msr-product-type":[],"msr-focus-area":[],"msr-platform":[],"msr-download-source":[],"msr-locale":[268875],"msr-field-of-study":[],"msr-conference":[],"msr-journal":[],"msr-impact-theme":[],"msr-pillar":[],"class_list":["post-215053","msr-research-item","type-msr-research-item","status-publish","hentry","msr-research-area-data-platform-analytics","msr-locale-en_us"],"msr_publishername":"","msr_edition":"PVLDB","msr_affiliation":"","msr_published_date":"2010-09-01","msr_host":"","msr_duration":"","msr_version":"","msr_speaker":"","msr_other_contributors":"","msr_booktitle":"","msr_pages_string":"1195\u20131206","msr_chapter":"","msr_isbn":"","msr_journal":"","msr_volume":"3","msr_number":"1","msr_editors":"","msr_series":"","msr_issue":"1","msr_organization":"","msr_how_published":"","msr_notes":"","msr_highlight_text":"","msr_release_tracker_id":"","msr_original_fields_of_study":"","msr_download_urls":"","msr_external_url":"","msr_secondary_video_url":"","msr_longbiography":"","msr_microsoftintellectualproperty":1,"msr_main_download":"","msr_publicationurl":"http:\/\/www.comp.nus.edu.sg\/~vldb2010\/proceedings\/files\/papers\/R106.pdf","msr_doi":"","msr_publication_uploader":[{"type":"url","title":"http:\/\/www.comp.nus.edu.sg\/~vldb2010\/proceedings\/files\/papers\/R106.pdf","viewUrl":false,"id":false,"label_id":0}],"msr_related_uploader":"","msr_attachments":[{"id":0,"url":"http:\/\/www.comp.nus.edu.sg\/~vldb2010\/proceedings\/files\/papers\/R106.pdf"}],"msr-author-ordering":[{"type":"user_nicename","value":"yinali","user_id":35012,"rest_url":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/microsoft-research\/v1\/researchers?person=yinali"},{"type":"text","value":"Bingsheng He","user_id":0,"rest_url":false},{"type":"text","value":"Jun Yang","user_id":0,"rest_url":false},{"type":"text","value":"Qiong Luo","user_id":0,"rest_url":false},{"type":"text","value":"Ke Yi","user_id":0,"rest_url":false}],"msr_impact_theme":[],"msr_research_lab":[],"msr_event":[],"msr_group":[957177],"msr_project":[],"publication":[],"video":[],"download":[],"msr_publication_type":"inproceedings","_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/215053"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/msr-research-item"}],"version-history":[{"count":2,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/215053\/revisions"}],"predecessor-version":[{"id":534981,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-item\/215053\/revisions\/534981"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=215053"}],"wp:term":[{"taxonomy":"msr-content-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-content-type?post=215053"},{"taxonomy":"msr-research-highlight","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-research-highlight?post=215053"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=215053"},{"taxonomy":"msr-publication-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-publication-type?post=215053"},{"taxonomy":"msr-product-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-product-type?post=215053"},{"taxonomy":"msr-focus-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-focus-area?post=215053"},{"taxonomy":"msr-platform","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-platform?post=215053"},{"taxonomy":"msr-download-source","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-download-source?post=215053"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=215053"},{"taxonomy":"msr-field-of-study","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-field-of-study?post=215053"},{"taxonomy":"msr-conference","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-conference?post=215053"},{"taxonomy":"msr-journal","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-journal?post=215053"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=215053"},{"taxonomy":"msr-pillar","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-pillar?post=215053"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}