11–20 of 62 posts
I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
EDIT: This is no longer true. Thanks latch!
I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
As of 14.1, they still don't support unique constraints:
select amname, pg_indexam_has_property(oid, 'can_unique') from pg_am
amname | pg_indexam_has_property
--------+-------------------------
heap | ¤
btree | t
hash | f
gist | f
gin | f
spgist | f
brin | fI had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
For sorting or adjacency queries, you want a btree index. A hash index can give you O(1) lookup with the drawback that you lose ordering completely (whereas getting a sorted selection of records with a tree is a O(1) operation). The trick here is having a hashing function which is both fast and avoids collisions (the worst case scenario is hash(x)=1 where everything hashes to the same value and you end up again with O(n) lookups).
I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
Indeed, they perform much better, but caveat emptor: hash index operations are not currently WAL-logged. That means that: 1) if you crash during a hash index update, all bets are off and you'll have to rebuild, and 2) they will just be wrong in a replicated configuration. EDIT: This is no longer true. Thanks latch!
Earlier quoted context omitted.
Indeed, they perform much better, but caveat emptor: hash index operations are not currently WAL-logged. That means that: 1) if you crash during a hash index update, all bets are off and you'll have to rebuild, and 2) they will just be wrong in a replicated configuration. EDIT: This is no longer true. Thanks latch!
This was fixed in PG 10 (Oct 2017). See https://rhaas.blogspot.com/2017/09/postgresqls-hash-indexes-...
And of course, Use the Index Luke is a great reference for the real world.
[0] https://notes.eatonphil.com/database-basics-indexes.html
His website "Use the Index, Luke!" [1] is also great.
I had assumed btree in Postgres was referring to a binary tree but that is definitely not the case. I also learned when to use a hash index, rather than a btree. (If I understand correctly if you’re only using the = operator rather than something that needs sorting with >, <, <=, etc. then a hash will perform better.)
A btree is a kind of binary tree, one which is self-balancing to keep O(log n) lookups from turning into O(n) lookups which is possible without the self-balancing. (Think about a naïve binary tree where you insert elements in sorted order—then everything will be in the right (or left if you start with the maximum value) branch and you need to traverse the whole structure to find the node you're looking for.) For sort…
By definition a binary tree means there are two children per node.
Binary is the one thing a b-tree is not.