Comment by dhosek | Hacker News Reader

Comment by dhosek | Hacker News Reader

Parent Full thread

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.

Reply on news.ycombinator.com