Hacker News Reader

Comment by programmarchy | Hacker News Reader

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

View on HN

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

> 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.

Right, I think you could say a binary tree is a kind of B-tree, though.

It'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.

Uhh. A b tree is a self balancing binary (search) tree.

Not binary, it can and generally has more than 2 children per node. That's the main difference.

Binary implies two. Both B-trees and BSTs exist in the universe of m-ary trees. A BST and a B-tree would be equivalent only if the branching factor of the B-tree was set to 2, but practically this is rarely the case with indexes, given that a higher branching factor is generally more favorable to lookup times (“block accesses”) since the hight of the B-tree is reduced as m increases.

> practically this is rarely the case with indexes

Seems like it would be extremely odd to have a 2-2 btree, you’d just get a significantly more complicated BST no?

I’d figure you’d want to fill a cacheline with something typical-ish, so probably at least 4 (this way if you have 4 children and 3 keys, the keys are 8 bytes and the child links are straight pointers your node is 56 bytes and you can add some metadata e.g. a bitmap).

Apparently Rust’s BTreeMap is a 6-11 btree but I don’t know how they picked the branching factor.

Unless 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.

That'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.

Less 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

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-...

Oh, that's great news! (I last used evaluated them in August 2017)

theoretically 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

Reply on news.ycombinator.com