  In this paper we propose an index key compression scheme based on the notion
of distinction bits by proving that the distinction bits of index keys are
sufficient information to determine the sorted order of the index keys
correctly. While the actual compression ratio may vary depending on the
characteristics of datasets (an average of 2.76 to one compression ratio was
observed in our experiments), the index key compression scheme leads to
significant performance improvements during the reconstruction of large-scale
indexes. Our index key compression can be effectively used in database
replication and index recovery of modern main-memory database systems.
