4 ms·
> 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.
by 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.
- getcrunk 5y agoUhh. A b tree is a self balancing binary (search) tree.
- coding123 5y agoNot binary, it can and generally has more than 2 children per node. That's the main difference.
- broken8ball 5y agoBinary 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.
- masklinn 5y ago> 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.
- 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.