[dragontamer]

    We use some special tricks for searches that are executed 
    frequently, e.g. as part of a dashboard. (We’ll describe 
    this in a future article.) 

And...

    (You might wonder why we store log messages in this
     4K-paged, metadata-and-text format, rather than
     working with raw log files directly. There are many 
     reasons, which boil down to the fact that internally,
     the Scalyr log engine looks more like a distributed 
     database than a file system. Text searches are often 
     combined with database-style filters on parsed log 
     fields; we may be searching many thousands of logs at 
     once; and simple text files are not a good fit for our 
     transactional, replicated, distributed data 
     management.)

It sounds like they're doing more than just "appending to the end of the log". If you're going to make an index of any kind, the index will likely be fastest with some sort of B-Tree.