ISB-tree: A new indexing scheme with efficient expected behaviour

DOI10.1016/J.JDA.2010.08.001MaRDI QIDQ616991zbMATH OpenOpenAlexFDO

Authors Christos Makris, George Mavritsakis, Spyros Sioutas, Kostas Tsichlas, A. C. Kaporis, Athanasios K. Tsakalidis, Christos Zaroliagis

Publication date 20 January 2011

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2010.08.001

zbMATH Keywords

B-treedata indexingexternal memory data structureinterpolation search

Mathematics Subject Classification ID

Data structures (68P05)

Recommendations

• Algorithms and Computation
• scientific article; zbMATH DE number 3909753
• Dynamic interpolation search
• Cache-Oblivious B-Trees
• Dynamic indexability and the optimality of B-trees

Cites work

• scientific article; zbMATH DE number 3653523 (Why is no real title available?)
• scientific article; zbMATH DE number 1305387 (Why is no real title available?)
• scientific article; zbMATH DE number 1099195 (Why is no real title available?)
• scientific article; zbMATH DE number 1368469 (Why is no real title available?)
• scientific article; zbMATH DE number 1402212 (Why is no real title available?)
• A balanced search tree O(1) worst-case update time
• A constant update time finger search tree
• A simple bounded disorder file organization with good performance
• Algorithms and Computation
• Algorithms for parallel memory, I: Two-level memories
• Bounded disorder: The effect of the index
• Cache-oblivious algorithms
• Deletions That Preserve Randomness
• Dynamic interpolation search
• Dynamic interpolation search in \(o(\log\log n)\) time
• Efficient locking for concurrent operations on B-trees
• Improved bounds for finger search on a RAM
• Organization and maintenance of large ordered indexes
• Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
• The SB-tree: An index-sequential structure for high-performance sequential access
• The string B-tree
• Worst-case optimal insertion and deletion methods for decomposable searching problems

Cited in

(4)

• Algorithms and Computation
• Enhancing the \(B^{+}\)-tree by dynamic node popularity caching
• CF-HNLBI: a new B-tree indexing for flash-based databases
• Fully persistent B-trees

Describes a project that uses

Uses Software

• LEDA

This page was built for publication: ISB-tree: A new indexing scheme with efficient expected behaviour

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