Fully persistent B-trees

DOI10.1016/J.TCS.2020.06.027MaRDI QIDQ2202015zbMATH OpenOpenAlexFDO

Authors Gerth Stølting Brodal, Konstantinos Tsakalidis, Spyros Sioutas, Kostas Tsichlas

Publication date 17 September 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2020.06.027

zbMATH Keywords

big datarange searchingexternal memorypersistent data structuresversioned databases

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Data structures (68P05) Searching and sorting (68P10) Database theory (68P15)

Recommendations

• Fully persistent B-trees
• Partially persistent B-trees with constant worst case update time
• Query-optimal partially persistent B-trees with constant worst-case update time
• Making data structures persistent
• I/O-efficient point location using persistent B-trees

Cites work

• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 3716818 (Why is no real title available?)
• scientific article; zbMATH DE number 1947389 (Why is no real title available?)
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
• A balanced search tree O(1) worst-case update time
• A new data structure for representing sorted lists
• AVL-trees for localized search
• Algorithms and data structures for external memory
• Cache-oblivious persistence
• Compressed persistent index for efficient rank/select queries
• Dynamic indexability and the optimality of B-trees
• Fully persistent B-trees
• I/O-efficient point location using persistent B-trees
• ISB-tree: A new indexing scheme with efficient expected behaviour
• Maintaining order in a generalized linked list
• Making data structures persistent
• Organization and maintenance of large ordered indexes
• Symmetric binary B-trees: Data structure and maintenance algorithms

Cited in

(9)

• Partially persistent B-trees with constant worst case update time
• scientific article; zbMATH DE number 140460 (Why is no real title available?)
• External memory fully persistent search trees
• Fully persistent B-trees
• scientific article; zbMATH DE number 1375590 (Why is no real title available?)
• B-Treaps: A Uniquely Represented Alternative to B-Trees
• Dynamic indexability and the optimality of B-trees
• Query-optimal partially persistent B-trees with constant worst-case update time
• Making data structures persistent

This page was built for publication: Fully persistent B-trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2202015)