Is there any index type in PostgreSQL that gives O(1) complexity for lookups? on strings?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
You'll need to the read the PostgresSQL Index Types documentation for the version that you are using. I think you are looking for a Hash Index, but as as the documentation explains the real world performance and pros and cons depend on the implementation details and recommendations of the particular version that you are using.
I don't think anything, even hash indexes, are going to guarantee a O(1).
One way in which a hash index can improve performance over a b-tree index is by hashing it to a smaller, fixed-size piece of data.
However, from the docs for the newest version (9.1):
Hash index operations are not presently WAL-logged, so hash indexes might need to be rebuilt with REINDEX after a database crash. They are also not replicated over streaming or file-based replication. For these reasons, hash index use is presently discouraged.