Very rough sketch. Say you have a table with two rows. One is time, the other is temperature. Your table is sorted by time, but you want all the unique tempera

Very rough sketch. Say you have a table with two rows. One is time, the other is temperature. Your table is sorted by time, but you want all the unique temperatures. Given the temperatures are unordered, you can't perform a binary search. If you also create a proper index against the times, your temperatures will also live in leaves of a tree that you'll need to access to get the values. So trick 1 is to just index that column, like you said, a precomputed binary search if you will But since we're interested in distinct queries, we can optimize further by pointing to the next greatest value with the index tree too (hence skip scan.)