Binary search with variable-length keys within an index page

摘要

Execution times of five strategies of binary search with variable-length keys are experimentally evaluated. For comparison, the experiments include also slide cubic search which has been recommended to be used in searching index pages of data base management systems. The results show that, in the environment of these experiments, it is possible to organize variable-length binary search clearly more efficiently than slide root search or slide binary search. The fastest version of variable-length binary search was only slightly slower than the usual fixed-length binary search implemented for keys padded to the maximum length of the range used.