Bender MGoswami MMedjedovic DMontes PTsichlas K(2021)Batched Predecessor and Sorting with Size-Priced Information in External MemoryLATIN 2020: Theoretical Informatics10.1007/978-3-030-61792-9_13(155-167)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-61792-9_13
Bender MEbrahimi RHu HKuszmaul B(2016)B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic KeysACM Transactions on Database Systems10.1145/290794541:3(1-33)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2907945
Liu XFu XSun G(2016)Recovery of Deleted Record for SQLite3 Database2016 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)10.1109/IHMSC.2016.173(183-187)Online publication date: Aug-2016
https://doi.org/10.1109/IHMSC.2016.173
Show More Cited By

Index Terms

Optimal pagination of B-trees with variable-length items
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
  2. Information storage systems
    1. Record storage systems
      1. Directory structures
        B-trees
2. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Trees

Recommendations

Pagination of B*-trees with variable-length records

A strategy is presented for pagination of B^*-trees with variable-length records. If records of each length are uniformly distributed within the file, and if a wide distribution of record lengths exists within the file, then this strategy results in ...
The string B-tree: a new data structure for string search in external memory and its applications

We introduce a new text-indexing data structure, the String B-Tree, that can be seen as a link between some traditional external-memory and string-matching data structures. In a short phrase, it is a combination of B-trees and Patricia tries for ...
Two Access Methods Using Compact Binary Trees

It is shown how a highly compact representation of binary trees can be used as the basis of two access methods for dynamic files, called BDS-trees and S-trees, respectively. Both these methods preserve key-order and offer easy and efficient sequential ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 27, Issue 3

March 1984

92 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/357994

Editor:
Peter J. Denning
NASA Ames Research Center, Moffett Field, CA

Issue’s Table of Contents

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: 01 March 1984

Published in CACM Volume 27, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
1,086
Total Downloads

Downloads (Last 12 months)240
Downloads (Last 6 weeks)29

Reflects downloads up to 10 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bender MGoswami MMedjedovic DMontes PTsichlas K(2021)Batched Predecessor and Sorting with Size-Priced Information in External MemoryLATIN 2020: Theoretical Informatics10.1007/978-3-030-61792-9_13(155-167)Online publication date: 5-Jan-2021
https://dl.acm.org/doi/10.1007/978-3-030-61792-9_13
Bender MEbrahimi RHu HKuszmaul B(2016)B-Trees and Cache-Oblivious B-Trees with Different-Sized Atomic KeysACM Transactions on Database Systems10.1145/290794541:3(1-33)Online publication date: 18-Jul-2016
https://dl.acm.org/doi/10.1145/2907945
Liu XFu XSun G(2016)Recovery of Deleted Record for SQLite3 Database2016 8th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)10.1109/IHMSC.2016.173(183-187)Online publication date: Aug-2016
https://doi.org/10.1109/IHMSC.2016.173
Messeguer X(2011)Skip trees, an alternative data structure to skip lists in a concurrent approachRAIRO - Theoretical Informatics and Applications10.1051/ita/199731030251131:3(251-269)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1997310302511
Bender MHu HKuszmaul BParedaens JVan Gucht D(2010)Performance guarantees for B-trees with different-sized atomic keysProceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems10.1145/1807085.1807125(305-316)Online publication date: 6-Jun-2010
https://dl.acm.org/doi/10.1145/1807085.1807125
Buchsbaum ASundar RTarjan R(1995)Data-Structural Bootstrapping, Linear Path Compression, and Catenable Heap-Ordered Double-Ended QueuesSIAM Journal on Computing10.1137/S009753979224214424:6(1190-1206)Online publication date: 1-Dec-1995
https://dl.acm.org/doi/10.1137/S0097539792242144
Buchsbaum ASundar RTarjan R(1992)Data structural bootstrapping, linear path compression, and catenable heap ordered double ended queuesProceedings of the 33rd Annual Symposium on Foundations of Computer Science10.1109/SFCS.1992.267820(40-49)Online publication date: 24-Oct-1992
https://dl.acm.org/doi/10.1109/SFCS.1992.267820
Hirschberg DLarmore L(1992)The traveler's problemJournal of Algorithms10.1016/0196-6774(92)90011-Z13:1(148-160)Online publication date: 1-Jan-1992
https://dl.acm.org/doi/10.1016/0196-6774%2892%2990011-Z
Manolopoulos YFistas N(1992)Algorithms for a hashed file with variable-length recordsInformation Sciences: an International Journal10.1016/0020-0255(92)90071-F63:3(229-243)Online publication date: 15-Sep-1992
https://dl.acm.org/doi/10.1016/0020-0255%2892%2990071-F
Gagliardi IMerelli D(1991)Minimum boundary-length problem in B∗-trees: A case studyInformation Systems10.1016/0306-4379(91)90041-716:5(559-564)Online publication date: Jan-1991
https://doi.org/10.1016/0306-4379(91)90041-7
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

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

References

Cited By

Index Terms

Recommendations

Pagination of B*-trees with variable-length records

The string B-tree: a new data structure for string search in external memory and its applications

Two Access Methods Using Compact Binary Trees

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations