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

DOI10.1016/j.jda.2010.08.001zbMath1215.68085MaRDI QIDQ616991

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

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-tree; data indexing; external memory data structure; interpolation search

Mathematics Subject Classification ID

68P05: Data structures

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A balanced search tree O(1) worst-case update time
• Worst-case optimal insertion and deletion methods for decomposable searching problems
• Algorithms for parallel memory, I: Two-level memories
• A constant update time finger search tree
• Bounded disorder: The effect of the index
• The SB-tree: An index-sequential structure for high-performance sequential access
• Organization and maintenance of large ordered indexes
• Dynamic interpolation search
• The string B-tree
• Cache-Oblivious Algorithms
• Searching Unindexed and Nonuniformly Generated Files in $\log \log N$ Time
• A simple bounded disorder file organization with good performance
• Efficient locking for concurrent operations on B-trees
• Deletions That Preserve Randomness
• Dynamic interpolation search in o(log log n) time
• Algorithms - ESA 2003
• Algorithms and Computation