hello again, i have trouble understanding this text from the docs:
A B-Tree instead makes each node contain B-1 to 2B-1 elements in a contiguous array. By doing this, we reduce the number of allocations by a factor of B, and improve cache efficiency in searches. [...]
what's "element B-1" or "element 2B-1" referring to here?
could someone help?
Note that B-Trees are not binary trees, though still binary search trees. They are a different type of tree where each node can contain more than one element, and more than two children (as opposed to binary trees where each node can contain only one element and at most two children).B is the branching factor of the B-Tree, that is the starting number used to calculate how many elements and children one node can have at most. For the stdlib's BTreeMap it is undocumented, but it's currently 6. "B-1 to 2B-1 elements" means that each node contains at least B-1 elements and at most 2B-1 elements.
The standard library has chosen B = 6, so its saying that each node in the tree has between 5 and 11 elements.
thanks! i thought B stood for Binary, but i guess i was wrong...
thanks for the detailed answer! very helpful!
Note that the exact number of the B is not guaranteed and may be adjusted. It's been changed few times after Rust 1.0 release based on benchmarks.
oh so it's being optimized based on benchmarks? i guess that makes sense, thanks!
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.