B+ Tree in BTreeMap

[benaryorg]

Based on my knowledge regarding BTrees (I know how they are built, how they work and I also know what a B+ tree is), which I know is by far not the best, I think you might really want to use a B+ Tree](https://en.wikipedia.org/wiki/B%2B_tree) if you do not already.
That would make the predecessor and successor methods currently discussed here quite fast with considerable memory-overhead, also it would make implementing iterators (and cursors) and therefore the range API a lot easier and probably faster.

If I am missing something, please tell me.

[Gankra]

I think the main change we want is to add child pointers so that no operation (including iterator construction) requires allocating a search stack. This is the approach taken in Google's BTree implementation, which to my knowledge is the state of the art: https://code.google.com/p/cpp-btree/

Note that in-memory and on-disk BTrees have different performance constraints. Though the similarity between CPU cache and file system block access certainly makes them similar, the order of magnitude means disk BTrees can basically do anything to avoid touching different blocks of disk, while an in-memory BTree may prefer touching more cache lines to avoid other expensive actions like allocating memory.

[Gankra]

Sorry Accidentally hit submit to soon:

However if you're willing to implement a B+ tree from scratch to prove a point, I encourage you to give it a shot! I am willing to provide mentorship on any issues that you face. Although it may make more sense to implement it as a seperate crate as a proof of concept.

Note that @bluss is currently implementing their own BTree, though I believe they do no intend to submit it to std.

[benaryorg]

Thanks for your support.

I want to improve my Rust skills anyway, so that's a challenge.

We'll see how far I get and if the performance can keep up with other implementations.

[Gankra]

Oh actually I just remembered the key problem that B+-Trees have which probably makes them completely inappropriate for Rust: they require you to duplicate keys. This is a non-starter in Rust because of ownership. If your keys are Vec's or, like, Files, you can't just indiscriminately duplicate them. Especially if you have internal mutability, because then it's possible for a user of your collection to "desynchronize" the different copies of the keys.

Most languages can do B+ Trees because everything is garbage collected and therefore it's "fine" to have several copies of the same value because they're all just pointers to the same value at some location in the heap.

To get a workable solution in Rust you will have to choose one of the following tradeoffs, I believe:

• Require that keys are Clone (or even Copy -- Copy should prevent internal mutability iirc)
• Store all keys Rc's to get proper shared ownership.
• Store all keys in Boxes and have unsafe raw pointers to the boxes in the internal nodes
• Store all keys in the leaves and have unsafe raw pointers to the leaves in the internal nodes

[benaryorg]

After finally understanding slices, I now know what you mean.

error: the trait `core::marker::Copy` is not implemented for the type `T` [E0277]

I ended up using something like this:

pub struct Node<'a,T:'a+Sized+PartialOrd>
{
    pub data:Rc<Box<[Option<&'a T>]>>,
}

Are there any drawbacks of using _Rc_s except that they are another layer wrapping the actual object which does some work and has a bit of an overhead?
Of course I am assuming that I am not that.… irresponsible to not clean up all _Rc_s when deleting some data.

Edit: of course there are missing references to the underlying leaves and so on, I am just trying to save the data at the moment.

[Gankra]

Rc is just like Box in that it heap allocates, and can contain unsized data like [T]. So Rc<Box<X>> can usually be reduced to Rc<X>. The only overhead of Rc over Box is that every time you Drop or Clone them they frob an internal reference count (also they consume more memory for that reference count).

I don't think you can use safe references for a BTree though. Lifetimes ('a) are scopes( { .. }) in the program somewhere. The internal data of a collection does not exist for any particular scope; rather they exist as long as the collection does. You will likely need to use raw pointers (*const T). Note that unlike references these are nullable, so the Option is not needed (and will impose overhead if used, because the None case cannot be optimized to a null pointer).

[benaryorg]

I have already planned ahead enough to know how to implement the references, although I am not sure if I cannot use the Rc to do that. I just need to wrap every Node into an Rc which's new() takes the parameter by-value, therefore I would not have a reference anymore. The problem arises when I have to pass the value back to the calling program.

I just read the sourcecode of the BTreeMap/BTreeSet implementation:

• BTreeSet does not have a method to access a specific index and can only be iterated over.
• The BTreeSet uses a BTreeMap internally.

The BTreeSet would therefore be better implemented as a B+TreeSet.…

Please, as always, correct me if something is wrong.

Also, if I do not have to pass a value back, but an iterator, everything gets a bit complicated, for me, as I have no idea how to write that. But I'm trying.

[Gankra]

Sets are strongly limited by the APIs that maps expose today. rust-lang/rfcs#1194 hopes to resolve this.

[benaryorg]

So I would have to implement that in near future? Good thing I like doing things right from the start.

[Gankra]

I would suggest implementing it now, or at least writing your implementation so it's trivial to "turn on", since this is Very Likely to be accepted in one form or another.

[benaryorg]

That's what I meant with "doing this right from the start".

I think I should have said "doing this right, right from the start".

[Gankra]

👍

Good luck!

[benaryorg]

Thanks.

You can find the (rather minimalistic) results here.

Edit: I think I've learned quite a lot right now. Also that might be why the results are like they are.

[arthurprs]

This isn't really possible for non-copy keys, what happens if you remove a key that's also being used in a branch node?