What are the types of data structure and the access time in the best / average / worst cases?
In a list is pretty simple, I need to run through all items until I find the specific one I wanted.
What happens with facts? How do they store?
Assume I have N facts:
color(red).
color(blue).
.
.
.
color(green).
Now I’m going to ask prolog of color(green).
It should return true.
How much time it take to prolog find that fact and return the right answer?
You should measure it for your use case I guess. There is quite a bit on the topic of how clauses are indexed here:
So in my example above, when I query for color(green), it does hash lookup?
If I remember correctly, for less than ten clauses it does a linear search. This is the second bullet point in the link I shared above, “Linear scan on first argument”. If there are more colors than it is a hash lookup.
You can also read the code I guess? I admit I haven’t done it myself. Maybe src/pl-index.c is the place to start reading? Not sure.
Thank you 
Was looking for something else and saw predicate_property/2. The property indexed(Indexes) might be of use. Not sure as I did not try it, but if this were my question I would be checking this out.
Use jiti_list/1 instead. The indexed(Indexes) property is specifically documented as might change. Of course, first call the relevant goals as they are Just In Time Indexes 
.