Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

Is there any index type in PostgreSQL that gives O(1) complexity for lookups? on strings?

share|improve this question
    
At a guess I'd say you are looking for FTS and GIN indexes although they are not O(1). –  Jack Douglas Oct 31 '11 at 8:50

2 Answers 2

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.

share|improve this answer

I don't think anything, even hash indexes, are going to guarantee a O(1).

  • This would only be achievable when asking for specific entries where x = 'a' or sets where x in ('a','b')
  • Hash tables achieve O(1) by an array of "buckets" corresponding to a hash value each. On the other hand, if we're talking of only storing the values, and not the empty buckets, this is essentially the same lookup characteristics as a balanced b-tree.
  • I've read somewhere that (in pg) hash index lookups "perform [as/no better than] b-tree indexes" or something like that, which indicates it's not stored with empty buckets.
  • The penalty for a O(log(N)) over a O(1) lookup is easily dwarfed by the overhead of sending it to the db and waiting for the result in the first place.

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):

Caution

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.