Shedal

Так и не понял, чем вам не подходит монга. У нее же простая и действенная масштабируемость — ключевая фича.

С оверхедом на хранение данных это вы зря. Во-первых, он есть практически везде, а во-вторых, storage сейчас очень дешевый.
По поводу фрагментации — разве BSON-документ может делиться на фрагменты? Насколько я помню, в дефолтной конфигурации монга этого не допускает.

SELECT *
FROM myTable t1
JOIN myTable t2
    ON t1.Id < t2.Id
    AND t1.Value > t2.Value
WHERE t2.Id = 100
ORDER BY t1.Id DESC
LIMIT 1;

Это так, к слову :)
Если нужно сделать такую выборку для всех Id, то можно сделать подзапрос, или GROUP BY.