research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Article
Entered by:
TitleISB-tree: A new indexing scheme with efficient expected behaviour
Bibtex cite IDRACTI-RU1-2010-71
Journal Elsevier
Year published 2010
Volume 8
Pages 373-387
DOI 10.1016/j.jda.2010.08.001
Keywords B-tree,External memory data structure,Interpolation search,Data indexing
We present the interpolation search B-tree (ISB-tree), a new cache-aware indexing scheme that supports update operations (insertions and deletions) in O(1) worst-case block transfers and search operations in O(logB logn) expected block transfers, where B represents the disk block size and n denotes the number of stored elements. The expected search bound holds with high probability for a large class of (unknown) input distributions. The worst-case search bound of our indexing scheme is O(logB n) block transfers. Our update and expected search bounds constitute a considerable improvement over the O(logB n) worst-case block transfer bounds for search and update operations achieved by the B-tree and its numerous variants. This is also verified by an accompanying experimental study.
Kaporis, Alexis
Makris, Christos
Mavritsakis, George
Sioutas, Spyros
Tsakalidis, Athanasios
Tsichlas, Kostas
Zaroliagis, Christos
isb tree.pdf (main file)
Publication ID854