3 ms·

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

by dhosek 5y ago

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

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 ago
  Uhh. A b tree is a self balancing binary (search) tree.
  - coding123 5y ago
    Not binary, it can and generally has more than 2 children per node. That's the main difference.
  - broken8ball 5y ago
    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.
    - 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 ago
  Right, I think you could say a binary tree is a kind of B-tree, though.
  - jlokier 5y ago
    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.

by dhosek 5y ago

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 ago
Uhh. A b tree is a self balancing binary (search) tree.
- coding123 5y ago
  Not binary, it can and generally has more than 2 children per node. That's the main difference.
- broken8ball 5y ago
  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.
  - 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 ago
Right, I think you could say a binary tree is a kind of B-tree, though.
- jlokier 5y ago
  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.