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. https://github.com/rust-lang/rfcs/pull/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]

:+1:

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?

[benaryorg]

My plan is to wrap every object and have references (I will work with _Arc_s a lot) point to the preceding and succeeding wrapper. Kinda like a reference-counted Tree-Set.

Then I will have the main Tree pointing to the wrappers.

The removal would look like this:

1. head to the node recursively
2. clone the Arc
3. remove from tree
   • replace Wrapper with None
   • rebalance tree if needed
4. correct list-part
   1. dereference the Arc
   2. set predecessor's successor to successor
   3. set successor's predecessor to predecessor
5. pass key from the Arc back in the recursion

Is there anything I am missing?

[benaryorg]

Also, another question, should I close this issue and reopen it when I have finally made some progress (about next month when I have time after this endless time of having no time)?

[fhahn]

@benaryorg just for your information, I am working on a B+ tree implementation in Rust (https://github.com/fhahn/rust-bplustree). So far, I have only implemented insertand a leaf node lookup and the code isn't tuned for performance at all. Feel free to drop me a line if you want to collaborate.

[Gankra]

Yeah sure, let's just close this. Feel free to ping me via email/irc for general questions. @apasel422 and @gereeter are also good people to talk to.

[arthurprs]

@benaryorg I think so, Image a String key (which has a heap allocation underneath)

map = BPlusTreeMap::new()
// loads of inserts
let a = map.remove("I'm in a branch key also");
drop(a)
map.get("blahblah") // might segfault as a underlining data  won't be there

Using an (A)rc internally won't solve this since you can't track references outside of the BPlusTree, as I shown in my example.

What you could do is limit the K to Clone types, so you can .clone() the key before sticking it into the branch node. This might be a reasonable performance wise but it won't make to the stdlib.

[benaryorg]

I have difficulties to understand what you're trying to tell me. Sorry.

As far as I understand you think that if you call remove on a key that is not residing in a leaf, then the references might break. Is that right?

[SteveLauC]

I implemented a BPlusTreeSet based on the pseudocode given in Database System Concepts 7th Edition.

For duplicated keys (e.g., one in a leaf node and one in an internal node), Rc is used. Since a node can have multiple owners (internal parent node and previous leaf node), the Node is also powered by Rc...

This issue is pretty old, but if you guys are still interested in it, welcome to give my impl a look: https://github.com/SteveLauC/BPlusTreeSet