Fully persistent B-trees

DOI10.1016/J.TCS.2020.06.027zbMATH Open1455.68046OpenAlexW3040250498MaRDI QIDQ2202015FDOQ2202015

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

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

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)

Cites Work

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

Cited In (9)

• B-Treaps: A Uniquely Represented Alternative to B-Trees
• Partially persistent B-trees with constant worst case update time
• Dynamic indexability and the optimality of B-trees
• Title not available (Why is that?)
• Making data structures persistent
• Query-optimal partially persistent B-trees with constant worst-case update time
• External memory fully persistent search trees
• Title not available (Why is that?)
• Fully persistent B-trees

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)