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