Re:How does database indexing work? (2008)
by masklinn on Tuesday March 08, 2022 @11:20AM
(#30601654)
> 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.
Re:How does database indexing work? (2008)
by programmarchy on Tuesday March 08, 2022 @12:07PM
(#30602370)
Right, I think you could say a binary tree is a kind of B-tree, though.
Re:How does database indexing work? (2008)
by jlokier on Tuesday March 08, 2022 @02:42PM
(#30605496)
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.
Re:How does database indexing work? (2008)
by getcrunk on Tuesday March 08, 2022 @12:10PM
(#30602411)
Uhh. A b tree is a self balancing binary (search) tree.
Re:How does database indexing work? (2008)
by broken8ball on Tuesday March 08, 2022 @12:25PM
(#30602645)
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.
Re:How does database indexing work? (2008)
by masklinn on Tuesday March 08, 2022 @01:12PM
(#30603448)
> 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.
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).