Techniques for compressing leaf blocks of an index are provided. The decision whether (and/or how much) to compress leaf blocks of an index is performed on a per block basis. Thus, for example, some leaf blocks of the index may be compressed while other leaf blocks of the index may be uncompressed. As another example, different leaf blocks of an index may be compressed a different amount. In one technique, a set of index entries is identified for storage in a leaf block. Multiple estimates of potential space savings are calculated for compressing the set of index entries, one estimate for each different variation of a compression technique. The compression technique variation that is associated with the most space savings is selected and applied to the set of index entries. Thus, some techniques prevent negative compression altogether. Additionally, users require no knowledge of the underlying data to perform optimal compression.