[galeaspablo]

That's correct. And keep in mind that you might have new consumers starting from the beginning come into play, so you have to permanently retain the indexes.

And yes, O(n log n ) is not bad at all. Sorted database indexes (whether SQL, NoSQL, or AcmeVendorSQL, etc.) already take O(n log n) to insert n elements into data storage or to read n elements from data storage.