Вспомогательная таблица с полями "баланс", "user_id". Уникальный индекс по user_id, кластерный индекс(это важно!) по полю "баланс"
Триггер на изменение баланса в основной таблице исправляет значение во вспомогательной.
In cases where you are accessing single rows randomly within a table, the actual order of the data in the table is unimportant. However, if you tend to access some data more than others, and there is an index that groups them together, you will benefit from using CLUSTER. If you are requesting a range of indexed values from a table, or a single indexed value that has multiple rows that match, CLUSTER will help because once the index identifies the table page for the first row that matches, all other rows that match are probably already on the same table page, and so you save disk accesses and speed up the query.
https://www.postgresql.org/docs/9.1/sql-cluster.htmlUPD
Я придумал другое решение.
1) разберитесь с размером основной таблицы, скорее всего её раздуло
https://www.youtube.com/watch?v=-GNHIHEHDmQ
2) сделайте индекс по полю Balance с опцией Include Columns и добавьте в него user_id. Тогда при запросе
select balance, user_id from your_table_name order by balance
все данные будут вычитаны из индекса, а это значительно сократит вам нагрузку