کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
431066 | 688265 | 2010 | 15 صفحه PDF | دانلود رایگان |
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)O(1) worst-case block transfers and search operations in O(logBlogn) 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(logBn)O(logBn) block transfers. Our update and expected search bounds constitute a considerable improvement over the O(logBn)O(logBn) 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.
Journal: Journal of Discrete Algorithms - Volume 8, Issue 4, December 2010, Pages 373–387