Immediately. The approach used is to have a separate "long-term" data structure and a smaller short term one. The long-term structure is only batch updated periodically, while the short-term logs changes since last batch. Every access queries both.
And this doesn't even get in to the questions such as at what point is a record eligible to be in my query. When I ran my query, or when I iterated to where that record would be? Is this controllable?
And seriously, just answering "immediately" is very close to saying "by magic." Too close, for this old timer's preference. I have a ton of respect for the stack. More so for those making it.
The transaction log also goes into a tree, but that tree is structured rather differently (for performance reasons). For example, it maintains a "linked-list" (in storage!) of the latest N transactions, which it then rolls up into one tree node once that list gets to a certain size.
The missing part about how transactions are available "immediately" (which is a word that doesn't make sense for a distributed database ;), is that the transactor (which is a separate process/system from those that answer questions), streams new transactions (as they happen) to the query boxes (known as "peers"). A peer is just your usual client process: for example your Java frontend webserver process (at this time only JVM clients are properly supported in this model)
Indexing is done in the background every ~33mb of transaction data (in the transactor) (and it allows that to build up during new indexing jobs, applying back pressure if it gets too much in memory data). Indexing isn't append only at all - it creates a new tree (that very often shares a lot of data with the old tree, however).
To answer queries, the "peers" merge the new transactions they've received (that are in memory), with the durable index. That's how new transactions get seen quickly - the peers have recent data in memory, and other data in long term durable storage.
Transactions are visible as soon as the transactor's streaming sends them to peers. There is also a mechanism to say "wait until this transaction has arrived at this peer" before querying.
Because the data in the indexes is immutable, it's trivial to cache in the client processes. Many smaller databases can fit entirely in memory, in which case querying only hits main memory, not the network on the peer process, which makes them (potentially) many orders of magnitude faster than querying a traditional RDBMS).
I am curious on why you have "potentially" in parens. Is this just not panning out in measurements? Are these not techniques that older products could have already subsumed into their repertoire?
A lot of this reads like RISC versus CISC debates. There are virtually no techniques that one side can claim monopoly on. So it is not surprising to see that picking the acceptable tradeoffs and combining solutions appropriately is often very effective.