5 ms·
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
by programmarchy 5y ago
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.)
- latch 5y agoLess important now, but they're unsafe to use prior to PG 10. 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 | f
- efficax 5y agotheoretically a hash lookup is O(1) so should perform better if the key is unique, but you give up a lot of other features (like partial matches, searching, and range queries). Binary trees are the ideal in a world of a pure von Neumann model. In practice data structures perform better when data is grouped together and this is what the b-tree gets you. It's both more disk and cache efficient in real world workflows
- dikei 5y agoUnless your own benchmarks prove hash indexes to have major benefits for your queries, stick with the default B-tree index: you never know what queries you'll need in the future.
- latch 5y agoThat's a bit too YAGNI for me. You have a `users` table with an `tenant_id uuid not null` column. You aren't going to need uniqueness on it and you aren't going to need range operations on it it. And..even if you did, you could re-index it.
- settrans 5y agoIndeed, 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!
- dhosek 5y agoA 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 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).
- masklinn 5y ago> A btree is a kind of binary tree By definition a binary tree means there are two children per node. Binary is the one thing a b-tree is not.
- programmarchy 5y agoRight, I think you could say a binary tree is a kind of B-tree, though.
- jlokier 5y agoIt's not, because in a standard B-tree all the leaf nodes are at exactly the same depth, whereas in a binary tree they are not in general, unless the binary tree is balanced with exactly 2N leaves. This difference occurs because a B-tree can have interior nodes that aren't completely full, whereas a binary tree's interior nodes have exactly 2 children.
- getcrunk 5y agoUhh. A b tree is a self balancing binary (search) tree.
- 5y ago