k Ary Search on Modern Processors 计算机科学

k-Ary Search on Modern ProcessorsBenjamin Schlegel Technische Universität Dresdenbenjamin.schlegel@tu- dresden.deRainer Gemulla IBM Almaden Research Centerrgemull@us.ibm.comWolfgang Lehner Technische Universität Dresdenwolfgang.lehner@tu- dresden.deABSTRACT This paper presents novel tree-based search algorithms that exploit the SIMD instructions found in virtually all mod- ern processors. The algorithms are a natural extension of binary search: While binary search performs one compar- ison at ea