I have come across the term O(log* N) in a book I'm reading on data structures. What does log* mean? I cannot find it on Google, and WolframAlpha doesn't understand it either.
It's iterated logarithm. See here for a description of lots of different time complexities, and here for more details on the iterated logarithm itself.
The iterated logarithm is the number of times the logarithm has to be applied before the result becomes one or less.