When is the index actually created? I have noticed that even on huge tables with millions of records when I do a CREATE INDEX the index is created immediately (I get the console back in nsecs).
Why is this? Doesn't it create the B-Tree with the table data at that point? I can only assume not due to the immediate return of the CREATE INDEX.
But then how is the index created? On each access?
Secondary index creation on innodb has been much faster since MySQL 5.1 + InnoDB plugin or MySQL 5.5. In fact, we refer to this feature as "fast index creation". If we don't touch the primary key, it only creates an additional structure and it only has to read the current values, without modifying the table data. Assuming you have enough memory, if the data pages are in memory and the index also fits into memory- this will be a memory-only operation, so potentially very fast. But the index will be ready to be used as soon as the process ends. In the background (after you get control back to the console), it will write the new pages to disk whenever it can. It is also dependent on how much data fragmentation you have in that particular tablespace. None of this can lead to losing data due to the transaction log (which is on disk).

But you are completely right by saying that some changes on secondary indexes are done in the background: it is called Change buffer, but it is used when modifying data records.

I must say that in my experience, InnoDB index creation is not as fast as it could :-), specially on very busy servers. However, starting with 5.6, creating secondary indexes is completely online (writers to that table are not blocked), which is a very nice improvement indeed.